Sau buổi học môn toán ở trường, anh được biết đến dãy số Fibonacci. Nếu gọi ~f(x)~ là hàm số trả về số Fibonacci thứ ~x^{\text{th}}~, thì hàm số được xây dựng như sau:

$$ \begin{cases} f(0) = 1 \\ f(1) = 1 \\ f(n) = f(n - 1) + f(n - 2) & , n > 1 \end{cases} $$

Cảm thấy dãy số rất thú vị, anh muốn thay đổi dãy số một chút. Anh muốn thay vì sử dụng phép toán cộng sẽ xử dụng phép toán ~\text{xor}~. Cụ thể, anh sẽ chọn ra hai số nguyên dương ~a~ và ~b~ để xây dựng một dãy Fibonacci riêng của mình như sau:

$$ \begin{cases} f(0) = a \\ f(1) = b \\ f(n) = f(n - 1) \oplus f(n - 2) & , n > 1 \end{cases} $$

Anh nghĩ, với một số nguyên dương ~n~ bất kỳ, anh có thể biết kết quả chính xác của ~f(n)~ là bao nhiêu hay không?

Input Specification

• Bộ ba số nguyên ~a~, ~b~ và ~n~ ~(1 \le a, b, n \le 10^9)~.

Output Specification

• Giá trị ~f(n)~ theo hàm mà anh thay đổi.

Sample Cases

Input #1:

1 2 2

Output #1:

3

Input #2:

325 265 1231232

Output #2:

76

Input #3:

4 5 1

Output #3:

5

Trong vườn trái cây FreeContest có một hàng gồm ~n~ cây cam. Mỗi cây cam có độ "dẻo dai" là ~a_i~ nhất định.

Hôm nay, bạn được giao một nhiệm vụ gồm nhiều câu hỏi. Mỗi câu hỏi bao gồm các số ~u_i~, ~k_i~. Bạn cần tính toán xem tích độ "dẻo dai " của ~k_i~ cây liên tiếp, bắt đầu từ cây thứ ~u_i~ là bao nhiêu?

Đáp án cuối cùng sẽ được chia lấy dư cho ~10^9 + 7~.

Input Specification

• Dòng thứ nhất chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~ - Độ "dẻo dai" của cây cam thứ ~i~.
• Dòng thứ ba gồm một số ~t~ - Số câu hỏi của nhiệm vụ.
• ~t~ dòng tiếp theo, mỗi dòng gồm hai số ~u_i~, ~k_i~ ~(1 \le u_i, k_i \le n)~. Dữ liệu đảm bảo ~u_i + k_i - 1 \le n~.

Output Specification

• In ra ~t~ dòng, mỗi dòng là đáp án cho từng câu hỏi được ~\bmod 10^9 + 7~.

Subtasks

• Subtask 1 [50%]: ~n, t \le 10^3~.
• Subtask 2 [50%]: Không có giới hạn gì thêm.

Sample Cases

Input #1:

6
5 2 7 1 10 3
3
1 2
3 3
2 4

Output #1:

0
70
140

Explanation #1:

• Ba dãy cây cần tính lần lượt là ~[5, 2]~, ~[7, 1, 10]~, ~[2, 7, 1, 10]~.

Cho dãy ~a~ gồm ~n~ số nguyên.

Hãy xác định xem dãy ~a~ có bao gồm bất kỳ dãy con có ít nhất ~3~ phần tử lập thành dãy Palindrome.

Notes

• Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu từ dãy ~a~ ta có thể xóa đi một vài phần tử (hoặc không xóa phần tử nào) để có được dãy ~b~ (và không mất tính thứ tự).
  • Ví dụ: Cho dãy ~a = [1, 2, 1, 3]~:
    • ~[2]~, ~[1, 2, 1, 3]~, ~[2, 3]~ là các dãy con của dãy ~a~.
    • ~[1, 1, 2]~, ~[4]~ không phải là các dãy con của dãy ~a~.
• Một dãy là dãy Palindrome khi dãy đó đọc xuôi hay đọc ngược đều như nhau. Hay nói cách khác, một dãy ~a_1, a_2, \dots, a_n~ là một dãy Palindrome nếu ~a_i = a_{n - i + 1}~ với mọi ~i~ từ ~1~ đến ~n~.
  • Ví dụ:
    • ~[1234]~, ~[1, 2, 1]~, ~[1, 3, 2, 2, 3, 1]~ và ~[10, 100, 10]~ là các dãy Palindrome.
    • ~[1, 2]~ và ~[1, 2, 3, 1]~ không phải là các dãy Palindrome.

Input Specification

• Dòng đầu tiên gồm một số nguyên ~t~ ~(1 \le t \le 100)~ - Số lượng truy vấn mà bạn phải trả lời.
• ~2 \times t~ dòng tiếp theo, mỗi cặp ~2~ dòng mô tả một truy vấn như sau:
  • Dòng thứ nhất của truy vấn gồm một số nguyên ~n~ ~(3 \le n \le 10^5)~ - Độ dài của dãy ~a~.
  • Dòng thứ hai của truy vấn gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n)~, với ~a_i~ là phần tử thứ ~i~ của dãy ~a~.
• Dữ liệu đầu vào đảm bảo tổng của ~n~ trên tất cả các truy vấn không vượt quá ~10^5~, tức ~\displaystyle \sum_{i = 0}^{t - 1} n_i \le 10^5~.

Output Specification

• Với mỗi truy vấn, in YES nếu ~a~ có ít nhất một dãy con có ít nhất ~3~ phần tử lập thành dãy Palindrome và NO nếu ngược lại.

Subtasks

• Subtask 1 [30%]: ~\displaystyle \sum_{i = 0}^{t - 1} n_i \le 5000~.
• Subtask 2 [70%]: Không có giới hạn gì thêm.

Sample Cases

Input #1:

5
3
1 2 1
5
1 2 2 3 2
3
1 1 2
4
1 2 2 1
10
1 1 2 2 3 3 4 4 5 5

Output #1:

YES
YES
NO
YES
NO

Ma thuật thực sự rất đơn giản, bạn chỉ cần muốn điều gì bạn sẽ có được nó.

Rex và người bạn pháp sư Zatara của mình đang khám phá khu rừng phù thủy vào đêm Halloween. Khi Rex vô tình phát hiện một mảng các số kỳ diệu ~a~ có độ dài ~n~, nó đưa anh ta vào một thế giới khác.

Rex nhớ rằng Zatara đã đưa cho anh ta hai số nguyên ~p~ và ~q~ để sử dụng trong tình huống như này. Khi sử dụng các số nguyên này, Rex có thể sửa đổi mảng ~a~ như sau:

• Tối đa ~p~ lần, thực hiện thao tác sau:
  1. Chọn hai phần tử ~x~ và ~y~ từ ~a~, xóa cả hai phần tử này khỏi ~a~, và chèn ~x + y~ vào ~a~.
  2. Thao tác này chỉ có thể thực hiện nếu ~a~ có ít nhất hai phần tử.
• Tối đa ~q~ lần, thực hiện thao tác sau:
  1. Chọn hai phần tử ~x~ và ~y~ từ ~a~, xóa cả hai phần tử này khỏi ~a~, và chèn ~x - y~ vào ~a~.
  2. Thao tác này chỉ có thể thực hiện nếu ~a~ có ít nhất hai phần tử.

Lưu ý rằng mỗi thao tác làm giảm kích thước của ~a~ đi một.

Hai loại thao tác (cộng và trừ) có thể thực hiện theo bất kỳ thứ tự nào, miễn là tối đa ~p~ thao tác cộng và ~q~ thao tác trừ được thực hiện.

Gọi ~b~ là mảng số kỳ diệu sau khi thực hiện một số lượng thao tác. Để trở lại thế giới ban đầu của mình, Rẽ phải tìm giá trị lớn nhất có thể của:

$$\max{(b)} - \min{(b)}$$

trên tất cả các trường hợp khả thi của ~b~. Bạn có thể giúp Rex tìm giá trị này không?

Input Specification

• Dòng thứ nhất chứa số nguyên ~t~ ~(t \le t \le 10^5)~ - Số lượng truy vấn.
• Mỗi truy vấn:
  • Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~ - Kích thước mảng.
  • Dòng thứ hai chứa hai số nguyên ~p~, ~q~ ~(0 \le p, q \le n - 1)~ - Số lượng thao tác cộng và trừ tối đa Rex có thể thực hiện.
  • Dòng thứ ba chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9 \ \forall \ 1 \le i \le n)~.

Tổng của ~n~ trong tất cả các trường hợp thử sẽ không vượt quá ~3 \times 10^5~, tức ~\displaystyle \sum_{k = 1}^{t} n_k \le 3 \times 10^5~.

Output Specification

• Gồm ~t~ dòng tương ứng với ~t~ truy vấn. Với mỗi truy vấn, in ra duy nhất một số nguyên là số có thể đưa Rex trở lại thế giới ban đầu.

Sample Cases

Input #1:

3 2
0 0
5 1
6
1 2
8 -1 -4 2 6 -3
7
6 6
-2 -4 2 -2 -3 -1 -1

Output #1:

4
23
15

Explanation #1:

• Mảng ~a = [8; -1; -4; 2; 6; -3]~. Dãy thao tác sau có thể được thực hiện:
  1. Chọn ~2~ và ~-3~, loại bỏ chúng và chèn ~2 - (-3) = 5~ vào mảng. Khi đó mảng là: ~[8; -1; -4; 6; 5]~.
  2. Chọn ~8~ và ~5~, loại bỏ chúng và chèn ~8 + 5 = 13~ vào mảng. Khi đó mảng là: ~[13; -1; -4; 6]~.
  3. Chọn ~-4~ và ~6~, loại bỏ chúng và chèn ~(-4) - 6 = -10~ vào mảng. Khi đó mảng là: ~[13; -1; -10]~.
• Hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất trong mảng này là ~13 - (-10) = 23~.

Peter kể rằng cậu ấy có một mô hình cây đặc biệt, từ một nút chỉ có thể đi xuống nút thấp hơn nó. Tuy nhiên trong lúc chuyển chỗ mô hình này, Peter đã vô tình vấp cỏ làm thay đổi hình dạng của cây.

Peter chỉ nhớ một vài đặc điểm của mô hình, đặc điểm thứ ~i~ cho biết từ nút ~u_i~ có thể đi đến nút ~v_i~. Peter không cần xác định hình dạng ban đầu của cây, chỉ cần biết được nút nào là gốc của cây. Hãy giúp Peter xác định xem có bao nhiêu nút có khả năng làm gốc của cây.

Input Specification

• Dòng thứ nhất chứa hai số nguyên dương ~n~, ~m~ ~(1 \le n, m \le 10^5)~ - Lần lượt là số lượng nút của cây và số đặc điểm mà Peter nhớ.
• ~n - 1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i~ và ~b_i~ ~(1 \le a_i, b_i \le n)~ - Cho biết có một cạnh nối giữa ~a_i~ và ~b_i~.
• ~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i~ và ~v_i~ ~(1 \le u_i, v_i \le n)~ - Cho biết đường đi từ nút ~u_i~ đến nút ~v_i~.

Output Specification

• In ra một số duy nhất là số nút có khả năng làm gốc của cây.

*Dữ liệu đảm bảo rằng có ít nhất một nút có thể làm gốc.

Subtasks

• Subtask 1 [50%]: ~n, m \le 1000~.
• Subtask 2 [50%]: Không có giới hạn gì thêm.

Sample Cases

Input #1:

7 2
2 3
3 5
4 6
1 2
4 7
2 4
2 5
2 6

Output #1:

2

Input #2:

7 1
1 2
3 6
2 5
3 7
2 4
1 3
2 3

Output #2:

3

Explanation #1, #2:

• Ở ví dụ thứ nhất, có thể chọn các nút ~1~, ~2~.
• Ở ví dụ thứ hai, có thể chọn các nút ~2~, ~4~, ~5~.