Cho 1 mảng ~A~ gồm ~N~ số nguyên dương. Xét biểu diễn nhị phân của các phần tử trong ~A~ và tần suất được bật của từng vị trí bit.

Ví dụ: Xét mảng ~A = \{5, 6\} = \{101_2, 110_2\}~.

Bit vị trí ~0~ được bật ~1~ lần, bit vị trí ~1~ được bật ~1~ lần, bit vị trí ~2~ được bật ~2~ lần.

Yêu cầu: Đếm xem có bao nhiêu vị trí bit được bật lẻ lần.

Input:

• Dòng đầu chứa số nguyên dương ~N (N \leq 10^5).~
• Dòng thứ hai chứa N số nguyên dương của mảng ~A (A_i \leq 10^9).~

Output:

• In ra ~1~ số nguyên duy nhất là số vị trí bit được bật lẻ lần trong mảng ~A~.

Sample

Sample Input 1

3
1 3 7

Sample Output 1

2

Giải thích: ~{1, 3, 7} = {001_2, 011_2, 111_2}.~ Bit ở vị trí ~0~ được bật ~3~ lần (lẻ), vị trí ~1~ bật ~2~ lần (chẵn), vị trí ~2~ bật ~1~ lần (lẻ). Vì có ~2~ bit được bật lẻ lần nên đáp án là ~2~.

Kệ sách ~A~ có ~N~ cuốn sách được xếp thành một hàng vào ~N~ vị trí trên kệ: ~A_1, A_2,\ldots, A_N~. Biết cuốn sách thứ ~i~ trong ~N~ cuốn này là của bộ môn ~A_i~. Có ~M~ cuốn sách nằm trên bàn: ~B_1, B_2, \ldots, B_M~. Biết cuốn sách thứ ~j~ trong ~M~ cuốn này là của bộ môn ~B_j~.

Bạn được phép chọn ~1~ cuốn sách trên kệ sách và ~1~ cuốn sách trên bàn và hoán đổi vị trí chúng cho nhau. Bạn được thực hiện hành động trên vô số lần nhưng không được đặt lên kệ những cuốn sách đã lấy xuống trước đó.

Yêu cầu: Tìm số bộ môn ít nhất có thể đặt trên kệ sách sau khi thực hiện các thao tác trên.

Input

• Dòng đầu chứa 2 số nguyên dương ~N, M\ (N, M \leq 2 \times 10^5)~.
• Dòng tiếp theo chứa ~N~ số nguyên không âm: ~A_1, A_2, \ldots, A_N\ (A_i \leq 10^9)~.
• Dòng tiếp theo chứa ~M~ số nguyên không âm: ~B_1, B_2, \ldots, B_M\ (B_i \leq 10^9)~.

Output

• In ra một số nguyên duy nhất là số bộ môn ít nhất có thể đặt lên kệ sách sau khi thực hiện các thao tác theo yêu cầu đề bài.

Sample

Sample Input 1

9 4
1 2 5 4 8 9 3 5 5
2 5 5 5

Sample Output 1

3

Giải thích: Kệ sách trở thành ~\{1, 2, 5, 5, 2, 5, 5, 5, 5\}~. Số bộ môn trên kệ sách là ~3~.

Sample Input 2

3 5
4 2 3
1 2 3 4 5

Sample Output 2

2

Giải thích: Kệ sách trở thành ~\{3, 2, 3\}~. Số bộ môn trên kệ sách là ~2~.

Cho ~n~ cây xanh liên tiếp nhau có chiều cao lần lượt là ~h_1, h_2, \ldots, h_n~.

Độ xấu của hàng cây là chênh lệch độ cao lớn nhất giữa ~2~ cây liên tiếp. Chi phí khi cắt tỉa ~1~ đơn vị độ cao của cây là ~P~ đồng.

Yêu cầu: Với tối đa ~Q~ đồng, hãy tìm độ xấu nhỏ nhất có thể của hàng cây sau khi cắt tỉa.

Input

• Dòng đầu chứa ~3~ số nguyên dương ~N, P, Q\ (N, P, Q \leq 2 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên không âm ngăn cách bởi dấu cách: ~h_1, h_2, \ldots, h_n~ (~h_i \leq 10^9)~.

Output

• In ra ~1~ số nguyên duy nhất là độ xấu bé nhất của hàng cây nếu như chỉ dùng nhiều nhất ~Q~ đồng.

Sample

Sample Input 1

6 3 33
1 5 6 7 10 2

Sample Output 1

2

Giải thích: Sau khi chặt, độ cao các cây trở thành ~[1,\ 3,\ 5,\ 6,\ 4,\ 2]~, chi phí tổng cộng là: ~{(0+2+1+1+6+0) \times 3 = 30\ (30 \leq 33)}~.

Cho mảng ~A~ gồm ~N~ phần tử và ~Q~ truy vấn có dạng sau:

• ~l\ r\ x~: Gọi ~u_1 = a_l, u_2 = a_{l+1},\ldots, u_{r-l+1} = a_r~. Kiểm tra dãy u có phải hoán vị của một dãy cấp số cộng có công sai là ~x~ hay không. Nói cách khác:
  • Sort mảng ~u~ theo thứ tự tăng dần, kiểm tra xem điều kiện sau có thỏa mãn hay không: ~u_i = u_{i-1} + x\ (\forall i: 1 < i \leq r-l+1)~.

Yêu cầu: Trả lời ~Q~ truy vấn trên. Với mỗi truy vấn, nếu truy vấn thỏa điều kiện trên thì xuất ra ~\text{YES}~, ngược lại xuất ra ~\text{NO}~.

LƯU Ý: Bài này sẽ được chấm theo thể thức IOI, tức chỉ khi bạn đúng hết các test trong subtask đó thì mới nhận được điểm của cả subtask đó.

Input

• Dòng đầu chứa 2 số nguyên dương ~N, Q~ (~N,Q \leq 4 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên không âm cách nhau bởi dấu cách: ~a_1, a_2, \ldots, a_N\ (a_i \leq 10^9)~.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ~3~ số nguyên không âm ~l, r, x\ (1 \leq l \leq r \leq n,\ 0 \leq x \leq 10^9)~ là các truy vấn.

Output

• Xuất ra ~Q~ dòng, dòng thứ ~i~ xuất ra YES/ NO tương ứng với câu trả lời cho truy vấn thứ ~i\ (1 \leq i \leq Q)~.

Subtask:

• Subtask 1 ~(20\%~): ~n \leq 1000,\ q \leq 1000~.
• Subtask 2 ~(20\%)~: ~x \leq 1~ với tất cả truy vấn.
• Subtask 3 ~(60\%)~: Không có ràng buộc gì thêm.

Sample

Sample Input 1

7 3
3 7 5 11 8 14 3
1 3 2
1 3 3
3 6 3

Sample Output 1

YES
NO
YES

Giải thích: Xét mảng ~u~ ở truy vấn 1 sau khi đã sort lại, ta có ~u = \{3, 5, 7\}~. Dễ thấy ~5 = 3 + 2, \ 7 = 5 + 2~.

Bạn được cho một đơn đồ thị vô hướng có ~n~ đỉnh - được đánh số từ ~1~ tới ~n~, và ~m~ cạnh.

Yêu cầu: In ra một đồ thị con của đồ thị đã cho sao cho:

• Mọi đỉnh của đồ thị con này có bậc là lẻ.
• Hoặc xác định không tồn tại đồ thị con thỏa mãn yêu cầu.
  • Trong bài tập này, đồ thị ~A = (V_A, E_A)~ là đồ thị con của đồ thị ~B = (V_B, E_B)~ nếu và chỉ nếu ~V_A = V_B~ và ~E_A \subseteq E_B~. Nếu có nhiều đáp án, in đáp án bất kỳ.

Input

• Dòng đầu chứa số nguyên dương ~t~ là số bộ test (~t \leq 20~).
• ~t~ nhóm dòng sau, mỗi nhóm dòng có định dạng:
  • Dòng đầu chứa 2 số nguyên dương ~n, m\ (1 \leq n, m \leq 4 \times 10^5)~.
  • ~m~ dòng tiếp theo, mỗi dòng chứa 2 số nguyên dương ~u,v~ biểu diễn ~1~ cạnh vô hướng ~(u, v)\ \newline (1 \leq u, v \leq n)~. Đảm bảo đơn đồ thị.

Đảm bảo tổng giá trị của ~n,m~ qua tất cả ~t~ bộ test không vượt quá ~4 \times 10^5~.

Output

• Nếu không tồn tại, xuất 1 dòng duy nhất in NO.
• Nếu tồn tại, dòng đầu in YES. Dòng tiếp in ~k\ (0 \leq k \leq m)~ là số lượng cạnh của đồ thị con. ~k~ dòng tiếp theo mỗi dòng in 2 số "~u\ v~" là cạnh của đồ thị con này.

Sample

Sample Input 1

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

Sample Output 1

NO
YES
3
1 5
3 2
4 6

Cho mảng ~a~ gồm ~n~ phần tử phân biệt và ~2~ số nguyên dương ~k, c~ (~k \leq a_i < 2^c~). Thao tác sau sẽ được thực hiện đúng ~k~ lần:

• Chọn một phần tử bất kỳ trong mảng ~a~ với xác suất bằng nhau. Giảm phần tử đó đi ~\textbf{1}~ đơn vị.

Yêu cầu: Với mỗi ~i~ từ ~0~ đến ~2^c -1~ hãy cho biết xác suất tổng ~XOR~ của mảng ~a = i~ sau khi thực hiện ~k~ thao tác. Có thể chứng minh được các giá trị xác suất trên đều có thể được viết dưới dạng ~\frac{p}{q}~, nên bạn hãy in ra giá trị ~p \cdot q^{-1}\ modulo\ 998244353~ của nó, hay, giá trị nguyên ~x~ (~0 \leq x < 998244353~) sao cho ~x \cdot q \equiv p~ (~mod\ 998244353~).

LƯU Ý: Bài này sẽ được chấm theo thể thức IOI, tức chỉ khi bạn đúng hết các test trong subtask đó thì mới nhận được điểm của cả subtask đó.

Input

• Dòng đầu nhập ~3~ số nguyên dương ~n,k,c~ (~1 \leq n \leq (2^c - k), \ 1 \leq k,\ c \leq 16~).
• Dòng thứ hai nhập vào ~n~ số nguyên dương của mảng ~a~ (~k \leq a_i < 2^c~).

Output

• In ra ~2^c~ số nguyên dương như yêu cầu đề bài.

Subtask

• Subtask 1 ~(15\%)~: ~n \leq 15,\ k \leq 5~.
• Subtask 2 ~(35\%)~: ~c \leq 9~.
• Subtask 3 ~(50\%)~: Không có ràng buộc gì thêm.

Sample

Sample Input 1

3 1 3
4 5 7

Sample Output 1

0 332748118 0 0 0 0 0 665496236

Giải thích: Có ~3~ cách thực hiện thao tác:

• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{3, 5, 7\}~, tổng ~XOR~ là ~1~
• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{4, 4, 7\}~, tổng ~XOR~ là ~7~
• ~\{4, 5, 7\}~ ~\rightarrow~ ~\{4, 5, 6\}~, tổng ~XOR~ là ~7~

Như vậy:

• Xác suất để tổng ~\text{XOR} = 1~ là ~\frac{1}{3}~ nên đáp án là ~332748118~. ~(332748118 \cdot 3 \equiv 1\ (mod\ 998244353))~
• Xác suất để tổng ~\text{XOR} = 7~ là ~\frac{2}{3}~ nên đáp án là ~665496236~. ~{(665496236 \cdot 3 \equiv 2\ (mod\ 998244353))}~
• Các trường hợp khác đều có xác suất là ~0~ nên đáp án là ~0~.