Bạn An có một dãy số gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~.

An rất thích thú với những công thức tính tổng, An liền nghĩ ra một công thức biến dãy ~a~ thành dãy ~b~ cũng có ~n~ phần tử: ~b_i = a_{i+1} + a_i~ với ~1 \le i < n~ (với ~i = n~ thì ~b_n = a_n + a_1~). Sau đó, An đổi dãy ~b~ thành dãy ~a~ và lại tính lại lần nữa. Vũ rất hứng thú với dãy số của bạn An, sau khi làm vô hạn lần, Vũ hỏi An liệu An có nhớ số thứ ~y~ ở trước lần biến đổi thứ ~x~ hay không.

Do kết quả có thể rất lớn nên Vũ muốn An lấy dư kết quả cho ~10^9 + 9~.

Yêu cầu: Hãy xác định giá trị của phần tử thứ ~y~ trong dãy số sau ~x~ lần biến đổi.

Input

• Dòng đầu chứa số nguyên dương ~n~ và số nguyên dương ~Q~ là số bộ test.
• Dòng thứ 2 chứa ~n~ số nguyên là dãy ~a~ (~|a_i| \le 10^5~).
• ~Q~ dòng sau chứa bộ số ~x, y~.

Output

• ~Q~ dòng, mỗi dòng gồm 1 số nguyên là số thứ ~y~ ở trước lần biến đổi thứ ~x~.

Sample Input 1

5 5
8 1 2 4 3 
1 2
1 3
2 4
6 3
5 5

Sample Output 1

1
2
7
139
53