Hùng được cho ~2 \times N~ điểm trên một cung tròn. Các điểm này cách đều nhau và được đánh số thứ tự từ ~1~ đến ~2 \times N~ theo chiều kim đồng hồ. Hùng thử nối ~N~ cặp điểm ~L_i~ và ~R_i~ với nhau sao cho mỗi điểm chỉ được nối với đúng một điểm khác, các đoạn nối này là các dây cung trong đường tròn và không có đoạn nối nào nằm ở ngoài đường tròn.

Sau khi nối xong, Hùng nhận thấy một số đoạn ~(L_i, R_i)~ và ~(L_j, R_j)~ cắt nhau. Hùng muốn biết có cặp đoạn ~(i, j)~ nào cắt nhau hay không, bạn hãy giúp Hùng nhé!

Input

• Dòng đầu tiên chứa một số nguyên dương ~N \ (1 \leq N \leq 10^6)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L_i, R_i \ (L_i, R_i \leq 2 \times N)~ biểu thị có cạnh nối giữa ~L_i~ và ~R_i~.

Output

• In ra Yes nếu tồn tại hai cặp đoạn cắt nhau, ngược lại in ra No.

Sample Input 1

3
1 6
2 5
3 4

Sample Output 1

No

Sample Input 2

3
4 1
3 5
6 2

Sample Output 2

Yes

Cho một số nguyên dương ~N~, tìm một cặp số nguyên dương ~(x, y)~ bất kì thỏa mãn ~x^3 - y^3 = N~. Nếu không có cặp thỏa mãn in ra ~-1~.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \le N \le 10^{18})~.

Output

In ra trên một dòng hai số nguyên dương ~x~, ~y~ thỏa mãn, nếu có nhiều cặp thỏa mãn thì in ra một cặp bất kì. Nếu không tồn tại in ra ~-1~.

Sample

Sample Input 1

999

Sample Output 1

12 9

Sample Input 2

888

Sample Output 2

-1

Cho một dãy ~N~ số nguyên ~A_1, A_2, \ldots, A_N~, hãy tìm cách tách dãy ~A~ thành hai dãy con liên tiếp, sao cho tổng số lượng các số phân biệt của mỗi dãy là lớn nhất. Nói cách khác, hãy tìm giá trị lớn nhất của ~(~số các số phân biệt trong ~A_1, A_2, \ldots, A_i)~ ~+~ ~(~số các số phân biệt trong ~A_{i + 1}, A_{i + 2}, \ldots, A_N)~ với ~1 \le i \le N - 1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(2 \le N \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le N)~.

Output

In ra một số nguyên duy nhất là đáp án tìm được.

Scoring

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

Sample Input

6
2 1 2 3 3 1

Sample Output

5

Giải thích: Ta có thể tách ở vị trí ~4~, khi đó thu được hai dãy ~[2, 1, 2, 3]~ và ~[3, 1]~, có tổng số lượng các số phân biệt của mỗi dãy là ~3 + 2 = 5~.

Cho một dãy ~N~ số nguyên ~A_1, A_2, \ldots, A_N~, hãy tìm cách tách dãy ~A~ thành ba dãy con liên tiếp, sao cho tổng số lượng các số phân biệt của mỗi dãy là lớn nhất. Nói cách khác, hãy tìm giá trị lớn nhất của ~(~số các số phân biệt trong ~A_1, A_2, \ldots, A_i)~ ~+~ ~(~số các số phân biệt trong ~A_{i + 1}, A_{i + 2}, \ldots, A_j)~ ~+~ ~(~số các số phân biệt trong ~A_{j + 1}, A_{j + 2}, \ldots, A_N)~ với ~1 \le i \lt j \le N - 1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(3 \le N \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le N)~.

Output

In ra một số nguyên duy nhất là đáp án tìm được.

Scoring

• Subtask 1 ~(30\%)~: ~N \le 200~
• Subtask 2 ~(30\%)~: ~N \le 2000~
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

8
3 3 1 2 3 1 2 2

Sample Output

7

Giải thích: Ta có thể tách ở vị trí ~1~ và ~4~, khi đó thu được ba dãy ~[3]~, ~[3, 1, 2]~ và ~[3, 1, 2, 2]~, có tổng số lượng các số phân biệt của mỗi dãy là ~1 + 3 + 3 = 7~.

Hùng có một dãy số nguyên ~A~ gồm ~N~ số nguyên không âm và một số nguyên ~M~. Trong một thao tác, Hùng có thể:

• Chọn một vị trí ~i~ ~(1 \le i \le N)~, sau đó thay ~A_i~ bằng ~A_i - 1~ hoặc ~A_i + 1~.

Hùng sau đó nhờ Hiếu chọn một số nguyên ~x~. Với số ~x~ mà Hiếu đã chọn, Hùng sẽ thực hiện các thao tác sao cho ~(A_i - x)~ chia hết cho ~M~ với mọi ~1 \le i \le N~. Với hai số ~x~ khác nhau mà Hiếu chọn thì số thao tác tối thiểu Hùng phải dùng có thể khác nhau.

Nhiệm vụ của bạn là tìm xem Hùng sẽ phải dùng ít nhất bao nhiêu thao tác, trong tất cả các cách chọn ~x~ của Hiếu, biết rằng Hùng rất khôn và luôn dùng số thao tác đúng bằng số thao tác tối thiểu cậu phải dùng với số ~x~ đó.

Input

• Dòng đầu tiên chứa một số nguyên ~T~ ~(1 \le T \le 10)~ - số lượng bộ test cần giải.
• Dòng đầu tiên của mỗi bộ test chứa hai số nguyên ~N~ và ~M~ ~(1 \le N \le 2 \times 10^5, 1 \le M \le 10^9)~, cách nhau bởi dấu cách.
• Dòng thứ hai của mỗi bộ test chứa ~N~ số nguyên ~A_1, A_2, \ldots, A_N~ ~(0 \le A_i \le 10^9)~.

Tổng của tất cả các giá trị ~N~ trong các bộ test không vượt quá ~5 \times 10^5~.

Output

Với mỗi bộ test, in ra một số nguyên duy nhất là số thao tác ít nhất Hùng phải dùng trong tất cả các cách chọn ~x~ của Hiếu.

Scoring

• Test 2: ~N \le 1000~ và ~M \le 1000~.
• Test 3: ~N \le 1000~.
• Test 4-5: ~M \le 10^5~.
• Test 6-16: Không có giới hạn gì thêm.

Sample Input

1
6 9
15 12 18 3 7 8

Sample Output

12

Giải thích: Với ~x = 6~, Hùng có thể:

• Dùng ~3~ thao tác để ~A_2 = 15~
• Dùng ~3~ thao tác để ~A_3 = 15~
• Dùng ~3~ thao tác để ~A_4 = 6~
• Dùng ~1~ thao tác để ~A_5 = 6~
• Dùng ~2~ thao tác để ~A_6 = 6~

Mất tổng cộng là ~12~ thao tác để ~A = [15, 15, 6, 6, 6]~ và thỏa mãn điều kiện ~(A_i - x)~ chia hết cho ~M~. Có thể chứng minh Hiếu không thể chọn ~x~ sao cho Hùng chỉ cần dùng ít hơn ~12~ thao tác. Ngoài ra, với cả ~x = 0~ hoặc ~x = 7~ thì Hùng cũng chỉ cần dùng ~12~ thao tác.

Cho ~N~ quả bóng và ~N~ hộp, các quả bóng được đánh số lần lượt từ ~1~ đến ~N~ và các hộp cũng được đánh số lần lượt từ ~1~ đến ~N~. Hùng sẽ lần lượt thực hiện ~Q~ bước, mỗi bước có thể là một trong ba thao tác như sau:

1. Chọn ra quả bóng mang số hiệu ~X~ và lấy nó ra khỏi hộp hiện tại, sau đó cho vào hộp ~Y~.
2. Đổi các quả bóng trong hai hộp ~X~ và ~Y~ cho nhau, tức quả bóng nào đang trong hộp ~X~ sẽ được đưa sang hộp ~Y~ và ngược lại.
3. Đố Hiếu xem quả bóng thứ ~X~ hiện tại đang nằm ở hộp có số hiệu bao nhiêu.

Nhiệm vụ của bạn là thiết kế một chương trình có thể thực hiện các thao tác và trả lời các câu hỏi của Hùng.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~Q~ ~(1 \le N \le 10^6, 1 \le Q \le 3 \times 10^5)~.
• ~Q~ dòng sau, mỗi dòng có định dạng như sau:
  • ~1 \ X \ Y~, nếu Hùng muốn thực hiện thao tác số 1.
  • ~2 \ X \ Y~, nếu Hùng muốn thực hiện thao tác số 2.
  • ~3 \ X~, nếu đó là một câu hỏi mà Hùng dành cho Hiếu.

Mọi thao tác đều đảm bảo ~1 \le X, Y \le N~, ngoài ra với thao tác 2 thì luôn thỏa mãn ~X \neq Y~.

Output

Lần lượt với mỗi câu hỏi của Hùng, hãy in ra trên một dòng một số nguyên dương duy nhất đáp án cho câu hỏi đó.

Sample Input

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

Sample Output

1
4

Giải thích:

• Thao tác đầu tiên lấy quả bóng ~3~ ra khỏi hộp ~3~ và cho vào hộp ~4~.
• Thao tác thứ hai đổi các quả bóng của hai hộp ~4~ và ~1~ cho nhau, khi này quả bóng số ~3~ đang ở hộp ~4~ sẽ chuyển sang ở hộp ~1~.
• Thao tác thứ ba chuyển quả bóng ~2~ sang hộp ~4~.

Cho một dãy số nguyên dương ~A_1, A_2, \ldots, A_N~. Với mỗi cặp ~L, R~ ~(1 \le L \le R \le N)~, định nghĩa ~f(L, R)~ như sau:

• Viết lên bảng lần lượt các số ~A_L, A_{L + 1}, \ldots, A_R~.
• Ta thực hiện các thao tác sau cho đến khi bảng không còn số nào:
  • Chọn ra hai số nguyên ~X, Y~ thỏa mãn lần lượt từng số ~X, X + 1, \ldots, Y~ vẫn còn trên bảng ít nhất một lần. Sau đó ta xóa mọi số có giá trị từ ~X~ đến ~Y~ trên bảng.
• ~f(L, R)~ được định nghĩa là số thao tác tối thiểu ta cần để xóa toàn bộ các số trên bảng.

Nhiệm vụ của bạn là tính tổng ~\sum_{L = 1}^N \sum_{R = L}^N f(L, R)~.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le N)~.

Output

In ra trên một dòng một số nguyên duy nhất là kết quả bài toán.

Scoring

• Subtask 1 ~(30\%)~: ~N \le 200~
• Subtask 2 ~(30\%)~: ~N \le 2000~
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

4
2 1 1 3

Sample Output

12

Giải thích:

• ~f(1, 1) = f(2, 2) = f(3, 3) = f(4, 4) = 1~,
• ~f(1, 2) = 1~, ~f(2, 3) = 1~, ~f(3, 4) = 2~,
• ~f(1, 3) = 1~, ~f(2, 4) = 2~,
• ~f(1, 4) = 1~.

Với một số nguyên dương ~x~, ta định nghĩa ~f(x)~ như sau: $$ f(x)= \begin{cases} f(\frac{x}{2}), & \text{nếu}\ x \equiv 0 \pmod{2} \\ x, & \text{nếu}\ x \equiv 1 \pmod{2} \end{cases} $$

Cho một dãy số nguyên ~A_1, A_2, \ldots, A_N~. Hãy tính tổng $$ \sum_{i = 1}^N \sum_{j = i}^N f(A_i + A_j) $$

Input

• Dòng đầu chứa một số nguyên dương ~N~ ~(1 \le N \le 2 \times 10^5)~.
• Dòng sau chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^7)~.

Output

In ra một số nguyên duy nhất là đáp án bài toán.

Scoring

• Subtask 1 ~(30\%)~: ~N \le 2000~.
• Subtask 2 ~(30\%)~: ~A_i \le 100~.
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

3
2 1 4

Sample Output

14

Với một số nguyên không âm ~X~, ta định nghĩa ~f(X)~ là tổng các chữ số của ~X~. Ví dụ: ~f(123) = 1 + 2 + 3 = 6~, ~f(99) = 9 + 9 = 18~, ~\dots~

Cho ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~. Hãy tính

$$ \sum_{i = 1}^{N} \sum_{j = 1}^{N} f(A_i + A_j) $$

Input

• Dòng đầu chứa một số nguyên dương ~N~ ~(1 \le N \le 2 \times 10^5)~.
• Dòng sau chứa ~N~ số nguyên dương ~A_1, A_2, \ldots, A_N~ ~(1 \le A_i \le 10^{12})~.

Output

In ra một số nguyên duy nhất là đáp án bài toán.

Scoring

• Subtask 1 ~(30\%)~: ~N \le 2000~.
• Subtask 2 ~(30\%)~: ~A_i \le 9~.
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

1
1

Sample Output

2

Thầy Tùng có ~N~ học sinh rất tài năng, và sau kì thi phân loại vừa rồi thầy đã gán cho mỗi học sinh một số nguyên không âm ~A_i~ - biểu diễn cho khả năng của học sinh đó (level càng pro thì ~A_i~ càng cao). Để make Ams great again, thầy Tùng đã setup các buổi học để các học sinh level cao hơn sẽ dạy cho các học sinh gà hơn. Sau mỗi buổi học, thầy nhận ra level của các học sinh đã thay đổi như sau:

• Mỗi học sinh sẽ học từ các học sinh có level cao hơn họ. Nếu có nhiều học sinh có cùng level và cùng cao hơn học sinh ~i~ thì học sinh ~i~ chỉ học từ một người trong số đó.
• Sau mỗi buổi học, level của học sinh ~i~ sẽ tăng lên một lượng đúng bằng số lần mà học sinh ~i~ học hỏi từ các học sinh khác trong buổi học đó.

Ví dụ: ~A = [2, 4, 2, 5, 5, 1]~, thì học sinh ~1~ sẽ học từ một học sinh có level ~4~ (học sinh ~2~) và một học sinh có level ~5~ (học sinh ~4~ hoặc ~5~), nên sau buổi học ~A_1 = 2 + 2 = 4~. Tổng thể thì sau buổi học đó ~A = [4, 5, 4, 5, 5, 4]~.

Để đưa ra các dự định cho tương lai, thầy Tùng có ~Q~ thắc mắc như sau:

1. Sau ~k~ buổi học, có bao nhiêu level khác nhau trong số các học sinh?
2. Sau ~k~ buổi học, tổng số level mà từng học sinh đã tăng lên là bao nhiêu?
3. Sau ~k~ buổi học, level của học sinh thứ ~i~ là bao nhiêu?

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ ~(1 \le N, Q \le 3 \times 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~.
• ~Q~ dòng sau, dòng thứ ~i~ bắt đầu bằng số nguyên ~t~ ~(t \in \{1, 2, 3\})~ là chỉ số của câu hỏi đó.
  • Nếu ~t = 1~, sau đó sẽ có một số nguyên ~k~ ~(0 \le k \le 10^{12})~.
  • Nếu ~t = 2~, sau đó sẽ có một số nguyên ~k~ ~(0 \le k \le 10^{12})~.
  • Nếu ~t = 3~, sau đó sẽ có hai số nguyên ~k~ và ~i~ ~(0 \le k \le 10^{12}, 1 \le i \le N)~.
• Nếu ~k = 0~ thì tức là thầy Tùng muốn hỏi thông tin về các học sinh trước khi buổi học đầu tiên diễn ra.

Output

• Với mỗi câu hỏi, in ra trên một dòng một số nguyên duy nhất là đáp án cho câu hỏi đó.

Scoring

• Subtask 1 ~(18\%)~: ~N, Q \le 5000~; ~A_i, k \le 10 000~.
• Subtask 2 ~(16\%)~ ~N, Q \le 5000~; ~A_i, k \le 10^7~.
• Subtask 3 ~(14\%)~: ~N, Q \le 5000~; ~A_i, k \le 10^{12}~.
• Subtask 4 ~(7\%)~: ~A_i, k \le 10^7~.
• Subtask 5 ~(12\%)~: ~N \le 5000~.
• Subtask 6 ~(14\%)~: Trong mọi truy vấn ~t = 1~.
• Subtask 7 ~(10\%)~: Trong mọi truy vấn ~t \in \{1, 2\}~.
• Subtask 8 ~(9\%)~: Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

3
2
1
8
11
4

Sample Input 2

5 4
0 3 5 4 2
1 0
1 1
2 1
3 1 1

Sample Output 2

5
2
10
4

Có ~N~ người đàn ông và ~N~ người phụ nữ đều được đánh số ~1,2,...,N~.

Với mỗi cặp số ~i,j~ ~(1 \le i,j \le N)~, độ hợp nhau của người đàn ông ~i~ và người phụ nữ ~j~ là ~a_{i,j}~. Nếu ~a_{i,j} = 1~ thì ông ~i~ và bà ~j~ hợp nhau, nếu ~a_{i,j} = 0 ~ thì ngược lại.

Taro tìm cách chia ~N~ người đàn ông và ~N~ người phụ nữ thành ~N~ cặp, trong đó mỗi cặp gồm một người đàn ông và một người phụ nữ hợp nhau.

Hãy tìm số cách khác nhau mà Taro có thể chia, modulo ~10^9+7~.

Input

• Dòng đầu tiên gồm số ~N~ ~(1 \le N \le 21)~.
• ~N~ dòng sau, mỗi dòng gồm ~N~ số nguyên ~0~ hoặc ~1~. Trong đó số thứ ~j~ ở hàng thứ ~i~ là giá trị của ~a_{i,j}~.

Output

In ra số cách chia cặp thỏa mãn, modulo ~10^9+7~

Sample Test 1

Input:

3
0 1 1
1 0 1
1 1 1

Output:

3

Có 3 cách thỏa mãn như sau (~(i,j)~ ký hiệu cho cặp giữa ông ~i~ và bà ~j~)

• ~(1,2),(2,1),(3,3)~
• ~(1,2),(2,3),(3,1)~
• ~(1,3),(2,1),(3,2)~

Sample Test 2

Input:

4
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

Output:

1

Có 1 cách thỏa mãn như sau: ~(1,2),(2,4),(3,1),(4,3)~

Sample Test 3

Input:

1
0

Output:

0

Sample Test 4

Input:

21
0 0 0 0 0 0 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1
1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 0
0 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 0 1 1
0 1 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0
1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0
0 1 1 0 1 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 1
0 1 0 0 0 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0
0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1
0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1
0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 1 0
0 0 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 0 0 1
0 1 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1
1 1 1 1 1 0 0 0 0 1 0 0 1 1 0 1 1 1 0 0 1
0 0 0 1 1 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1
1 0 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 1 1 0
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1
0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1
0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0
1 1 0 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 1 0
1 0 0 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 0 0 0

Output:

102515160

Lưu ý kết quả cần phải được in ra theo modulo ~10^9+7~.

Có ~N~ chú thỏ được đánh số ~1, 2, 3,..., N~.

Sự hoà đồng giữa hai chú thỏ ~i~ và ~j~ ~(1 \le i, j \le N)~ được biểu diễn bởi số nguyên ~a_{i,j}~. Trong đó, ~a_{i, i} = 0~ ~(1 \le i \le N)~, và ~a_{i, j} = a_{j, i}~ ~(1 \le i, j \le N)~.

Taro đang tìm cách chia ~N~ chú thỏ này vào một số nhóm, sao cho mỗi chú thỏ thuộc chính xác một nhóm. Nếu hai chú thỏ ~i~ và ~j~ ~(1 \le i < j \le N)~ thuộc cùng một nhóm, Taro được ~a_{i, j}~ điểm.

Bạn hãy tìm tổng số điểm lớn nhất mà Taro có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 16)~.
• ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên, số thứ ~j~ của dòng thứ ~i~ là số nguyên ~a_{i, j}~ ~(|a_{i, j}| \le 10^9, a_{i, i} = 0, a_{i, j} = a_{j, i})~.

Output

• In ra tổng số điểm lớn nhất mà Taro có thể đạt được

Sample Test 1

Input:

3
0 10 20
10 0 -100
20 -100 0

Output:

20

Sample Test 2

Input:

2
0 -10
-10 0

Output:

0

Sample Test 3

Input:

4
0 1000000000 1000000000 1000000000
1000000000 0 1000000000 1000000000
1000000000 1000000000 0 -1
1000000000 1000000000 -1 0

Output:

4999999999

Sample Test 4

Input:

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

Output:

132

Note

Các cách chia ở từng test ví dụ:

• Ví dụ ~1~: ~\{1, 3\},\{2\}~.
• Ví dụ ~2~: ~\{1\},\{2\}~.
• Ví dụ ~3~: ~\{1,2,3,4\}~.

Lưu ý rằng đáp án có thể vượt quá phạm vi giá trị của kiểu số nguyên 32-bit.

Binary Sudoku là một biến thể của trò chơi Sudoku thông thường mà Tuấn vừa mới nghĩ ra. Ở biến thể này, ta vẫn có một bảng ~9 \times 9~, nhưng sẽ chỉ gồm các số ~0~ và ~1~, và mục tiêu bây giờ của trò chơi là lật số ô ít nhất sao cho ở tổng mỗi hàng, mỗi cột và mỗi ô ~3 \times 3~ sẽ là số chẵn (tức có chẵn số ~1~). Chú ý là chỉ có ~9~ ô ~3 \times 3~ mà bạn cần phải làm thỏa mãn điều kiện, giống như trò chơi Sudoku thông thường.

Sau khi nghĩ ra biến thể mới, việc của Tuấn bây giờ là đi đánh đố mọi người. Cho bảng ~9 \times 9~ ban đầu, bạn hãy tìm ra số bước ít nhất để giải được bài Binary Sudoku đó.

Input

• Input gồm ~9~ dòng, mỗi dòng có ~9~ kí tự 0 hoặc 1 tương ứng với số ở vị trí đó trên bảng.

Output

• In ra một số nguyên duy nhất là số bước ít nhất để giải được bài Binary Sudoku tương ứng.

Sample Input

000000000
001000100
000000000
000110000
000111000
000000000
000000000
000000000
000000000

Sample Output

3

Giải thích: Có thể lật ~3~ ô để tạo được bảng như sau:

000000000
001000100
001000100
000110000
000110000
000000000
000000000
000000000
000000000

Cho một dãy số gồm ~n~ phần tử, nhiệm vụ của bạn là tính toán với mỗi phần tử ~x~:

1. Số phần tử ~y~ sao cho ~x \ | \ y = x~
2. Số phần tử ~y~ sao cho ~x \ \& \ y = x~
3. Số phần tử ~y~ sao cho ~x \ \& \ y \neq 0~

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~ là kích thước của dãy số.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^6)~.

Output

• In ra ~n~ dòng, mỗi dòng là đáp án của các thao tác với phần tử đang xét.

Sample Input

5
3 7 2 9 2

Sample Output

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

Cho ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~. Đếm số cặp ~(i, j)~ thỏa mãn ~1 \le i \lt j \le N~ và ~A_i \ | \ A_j \le max(A_i, A_j)~ (~|~ là phép OR nhị phân).

Input

• Dòng đầu chứa số nguyên dương ~N~ ~(1 \le N \le 10^6)~.
• Dòng sau chứa ~N~ số nguyên không âm ~A_1, A_2, \ldots, A_N~ ~(0 \le A_i \le 10^6)~

Output

• In ra một số nguyên duy nhất là đáp án bài toán.

Scoring

• Subtask 1 ~(40\%)~: ~N \le 2000~.
• Subtask 1 ~(60\%)~: Không có giới hạn gì thêm.

Sample Input

5
1 2 3 4 5

Sample Output

4

Cho một tập có ~N~ phần tử, đánh số từ ~0~ đến ~N - 1~. Với mỗi tập con ~S~ của ~N~, chi phí để tô tập con này bằng màu xanh là ~B_S~, và màu đỏ là ~R_S~. Tìm cách tô màu từng tập con của ~N~ bằng màu xanh hoặc đỏ (kể cả tập rỗng), sao cho thỏa mãn điều kiện: Với hai tập ~U~, ~V~ được tô cùng màu, tập ~U \cup V~ (~U~ hợp ~V~) cũng được tô bằng màu đó.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 20)~.
• Dòng thứ hai chứa ~2^N~ số nguyên ~B_0, B_1, \ldots, B_{2^N - 1}~ ~(-10^9 \le B_x \le 10^9)~, với ~B_x~ là chi phí để tô tập ~x~ bằng màu xanh.
• Dòng thứ ba chứa ~2^N~ số nguyên ~R_0, R_1, \ldots, R_{2^N - 1}~ ~(-10^9 \le R_x \le 10^9)~, với ~R_x~ là chi phí để tô tập ~x~ bằng màu đỏ.

Với một số nguyên ~x~ ~(0 \le x \lt 2^N)~, tập con tương ứng với số nguyên đó là tập gồm mọi số nguyên ~j~ sao cho bit thứ ~j~ trong ~x~ là ~1~. Phép hợp hai tập ~x~ và ~y~ có thể hiểu là ~x \ OR \ y~.

Output

• In ra một số nguyên duy nhất là chi phí nhỏ nhất tìm được.

Sample Input

2
2 4 1 5
2 3 4 1

Sample Output

7

Giải thích: Ta có thể tô các tập ~0, 2~ màu xanh và các tập ~1, 3~ màu đỏ. Tổng chi phí là ~2 + 3 + 1 + 1 = 7~.

Sample Input 2

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

Sample Output 2

16

Giải thích: Ta có thể tô tập ~0, 2, 4, 6~ màu xanh và tập ~1, 3, 5, 7~ màu đỏ. Tổng chi phí là ~2 + 2 + 1 + 1 + 2 + 2 + 1 + 5 = 16~.

Cho một dãy số ban đầu rỗng. Lần lượt thực hiện ~Q~ thao tác, mỗi thao tác có thể có dạng như sau:

1. + x, thêm số ~x~ vào dãy.
2. - x, xóa một số có giá trị bằng ~x~ khỏi dãy. Trước thao tác này đảm bào trong dãy có ít nhất một số ~x~.
3. ? x, đếm số lượng số ~y~ trong dãy thỏa mãn ~y \ AND \ x = y~.

Trong mọi thao tác ~x~ luôn là một số nguyên không âm. Nhiệm vụ của bạn là lần lượt thực hiện các thao tác trên, và trả lời đáp án chính xác với mỗi thao tác loại 3.

Input

• Dòng đầu chứa một số nguyên dương ~Q~ ~(1 \le Q \le 2 \times 10^5)~
• ~Q~ dòng sau, mỗi dòng có một trong ba dạng + x, - x, ? x ~(0 \le x \lt 2^{14})~, tương ứng với các truy vấn 1, 2, và 3.

Output

Với mỗi thao tác loại 3, lần lượt theo thứ tự nhập vào, in ra một số nguyên duy nhất là đáp án cho truy vấn đó.

Scoring

• Subtask 1 ~(30\%)~: ~N \le 2000~.
• Subtask 2 ~(30\%)~: ~0 \le x \lt 2^7~.
• Subtask 3 ~(40\%)~: Không có giới hạn gì thêm.

Sample Input

7
+ 2
+ 4
+ 3
? 5
+ 6
- 2
? 6

Sample Output

1
2

Huy và Châu trong công cuộc tìm lại cảm hứng đã quyết định đào sâu về toán học, đặc biệt là phần số học. Để tìm kiếm tài liệu, hai cậu quyết định đi tới tuyển Tin Ams, và vô tình thấy được một bài toán khó như sau được viết trên bảng:

Cho mảng ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta đều biết các số nguyên dương đều có thể phân tích dưới dạng thừa số nguyên tố, vậy nên đỡ mất thời gian phân tích gây tổn hại máy chấm, bạn sẽ nhận được số nguyên dương ~k~ dưới dạng phân tích thừa số nguyên tố của nó. Nói cách khác, bạn sẽ nhận được hai dãy nguyên dương ~p~ và ~x~ gồm ~m~ phần tử, thỏa mãn ~p~ gồm các số nguyên tố phân biệt. Lúc này ~k = p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \times ... \times p_m^{x_m}~.

Giả sử ~S~ là một dãy con của dãy ~a~ (bao gồm cả dãy rỗng), ta có định nghĩa sau:

• Gọi ~LCM(S)~ là bội chung nhỏ nhất của mọi phần tử thuộc ~S~. Đối với ~S = \emptyset~, giá trị này được coi là ~1~.
• Gọi ~G(S)~ là trọng số của dãy con ~S~, giá trị ~G(S) = x~ với ~x~ là số nguyên dương nhỏ nhất thỏa mãn: ~k | LCM(S) \times x~, hay ~LCM(S) \times x~ chia hết cho ~k~.

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Sau khi đọc xong, hai cậu mới biết rằng hóa ra đây là một đề bài được dự định sẽ cho vào ~AMSOI~ ~Round~ ~4~. Vốn đều là những người có ước mơ được thi ~VMO~ cháy bỏng, hai cậu đã nhanh chóng tìm ra lời giải của bài toán, thậm chí còn có thể giải một yêu cầu tổng quát hơn như sau:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Tuy nhiên, Huy lại muốn đưa nó vào đề bài chính thức, Châu lại bảo như vậy là quá khó với các bạn học sinh. Vậy nên, hai cậu quyết định thuyết phục thầy ... đưa cả hai dạng yêu cầu này vào bài. Và đó là lý do tại sao bạn lại đọc được đề của nó vào ngày hôm nay.

Để hiện thực hóa thỉnh cầu của học trò, ~mrtee~ sẽ cho bạn một tham số ~t~.

Với ~t = 1~, bạn hãy in ra kết quả của yêu cầu thứ nhất:

Hãy tính tổng trọng số của các dãy con ~S~ thoả mãn ~G(S) = 1~, hay nói cách khác đếm số dãy con sao cho bội chung nhỏ nhất của nó chia hết cho ~k~.

Với ~t = 2~, bạn hãy in ra kết quả của yêu cầu thứ hai:

Thay vì chỉ tính các dãy con ~S~ có ~G(S) = 1~, nhiệm vụ của bạn là hãy tính tổng trọng số của toàn bộ dãy con trong ~S~.

Với cả hai yêu cầu, tổng bạn cần tính đều có giá trị rất lớn, vậy nên hãy in nó ra sau khi lấy phần dư cho ~10^9+7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu tiên gồm ba số nguyên dương ~n,m,t~ (~1 \le n \le 10^5; 1 \le m \le 16; 1 \le t \le 2~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~p~, dữ liệu đảm bảo rằng đây đều là các số nguyên tố và chúng đôi một khác nhau (~2 \le p_i \le 10^6~).
• Dòng thứ hai gồm ~m~ số nguyên dương miêu tả dãy ~x~ ~(1 \le \sum_{i=1}^{m} x_i \le 20)~.
• Dòng cuối cùng gồm ~n~ số nguyên dương miêu tả dãy nguyên dương ~a~ (~1 \le a_i \le 10^{9}~).

Output:

• Với ~t = 1~, hãy in ra kết quả của yêu cầu thứ nhất, ngược lại với ~t = 2~ in ra kết quả của yêu cầu thứ hai. Vì kết quả có thể rất lớn nên hãy in nó ra sau khi lấy phần dư với ~10^9+7~.

Subtask:

• Subtask ~1~ (~10\%~ số điểm): ~t = 1; n \le 20; a_i \le 15; k \le 10^9~.
• Subtask ~2~ (~15\%~ số điểm): ~t = 1; n \le 50; a_i \le 15; k \le 10^9~.
• Subtask ~3~ (~20\%~ số điểm): ~t = 2; m \le 6; x_i = 1 \forall i \in [1,m]~.
• Subtask ~4~ (~25\%~ số điểm): ~t = 2; x_i = 1 \forall i \in [1,m]~.
• Subtask ~5~ (~15\%~ số điểm): ~t = 1~.
• Subtask ~6~ (~15\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

3 2 1
2 3
1 1
4 9 5

Sample Output 1

2

Sample Input 2

5 2 1
3 2
2 1
4 24 17 18 3

Sample Output 2

16

Sample Input 3

3 2 2
2 3
1 1
4 9 5

Sample Output 3

24

Sample Input 4

7 2 2
3 2
2 2
4 24 17 18 3 9 6

Sample Output 4

332

Explanation

Trong ví dụ thứ nhất, có hai dãy con ~S~ có ~G(S) = 1~ là dãy ~\{1;2\}~ và dãy ~\{1;2;3\}~.

Trong ví dụ thứ hai, có ~16~ dãy thỏa mãn chia hết cho ~k = 18~.

Ở ví dụ thứ ba với ~t = 2~ ta cần trả lời câu hỏi dạng thứ hai. Do ~k = 6~, ta sẽ xét các dãy con sau:

• ~\{\emptyset\}~: Dãy rỗng có ~LCM(\emptyset) = 1~, như vậy ~G(S) = 6~
• Ba dãy con độ dài ~1~: ~\{1\}~; ~\{2\}~; ~\{3\}~ lần lượt có ~G(S)~ là ~3;2;6~.
• Ba dãy con có độ dài ~2~: ~\{1;2\}~; ~\{2;3\}~; ~\{1;3\}~ lần lượt có ~G(S)~ là ~1;2;6~.
• Dãy con ~\{1;2;3\}~ có ~G(S) = 1~.
• Tổng lại ta thu được đáp án cho toàn bộ dãy con là ~24~.