Cho ~t~ truy vấn, mỗi truy vấn có dạng như sau:

• ~1~ ~x~: Đếm số lượng ~bit~ ~1~ trong biểu diễn nhị phân của ~x~.
• ~2~ ~x~: In ra ~bit~ ~1~ lớn nhất trong biểu diễn nhị phân của ~x~. Nếu không có in ra ~-1~.
• ~3~ ~x~: In ra ~bit~ ~1~ bé nhất trong biểu diễn nhị phân của ~x~. Nếu không có in ra ~-1~.

Input

• Dòng thứ nhất chứa số nguyên dương ~t~ miêu tả số truy vấn.
• ~t~ dòng sau, mỗi dòng miêu tả một truy vấn.

Output

• Gồm ~t~ dòng miêu tả kết quả của từng truy vấn.

Constraints

• ~1 \le t \le 2*10^5~.
• ~0 \le x \le 10^9~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

4
1 5 
2 16
3 7
2 0

Sample Output 1:

2
4
0
-1

Explaination 1:

• ~5 = 101~, có ~2~ ~bit~ ~1~.
• ~16 = 10000~, ~bit~ ~1~ lớn nhất là ~bit~ thứ ~4~.
• ~7 = 111~, ~bit~ ~1~ bé nhất là ~bit~ thứ ~0~.
• ~0~ không có ~bit~ ~1~ nào, vậy nên kết quả là ~-1~.

Cho một dãy hoán vị ~p~ gồm ~n~ phần tử từ ~0~ đến ~n-1~ (mỗi số chỉ xuất hiện đúng một lần). Dãy này ban đầu chưa được sắp xếp.

Dãy ~p~ được gọi là có độ mạnh ~X~ nếu như với một số nguyên không âm ~X~ nào đó, ta có thể ~sort~ dãy lại theo thứ tự tăng dần bằng cách sử dụng vô số thao tác sau:

• Chọn hai phần tử ~i~ và ~j~ ~(1 \le i < j \le n)~ mà ~p_i \& p_j = X~, ở đây ~\&~ là toán tử AND.
• Đổi chỗ ~p_i~ và ~p_j~.

Hãy tìm số ~X~ lớn nhất sao cho dãy ~p~ có độ mạnh ~X~.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả độ dài của dãy ~p~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả hoán vị ~p~.

Output

• In ra số ~X~ lớn nhất thỏa mãn.

Constraints

• ~1 \le n \le 2*10^5~.

Subtasks

• Subtask ~1~: ~n \le 400~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

2
1 0

Sample Output 1:

0

Sample Input 2:

7
0 1 2 3 5 6 4

Sample Output 2:

4

Cho dãy hai dãy số nguyên không âm ~a_1, a_2, ..., a_n~ và ~b_1, b_2, ..., b_m~.

Với mỗi ~i~ ~(1 \le i \le n)~, bạn cần chọn ra một giá trị ~j~ ~(1 \le j \le m)~, gán ~c_i = a_i \& b_j~, ở đây ~\&~ là toán tử ~AND~. Bạn có thể chọn các giá trị ~j~ giống nhau cho các giá trị ~i~ khác nhau.

Hãy tìm giá trị nhỏ nhất của ~c_1 | c_2 | ... | c_n~, ở đây ~|~ là toán tử ~OR~.

Input

• Dòng thứ nhất chứa hai số nguyên dương ~n~ và ~m~.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.
• Dòng thứ ba gồm ~m~ phần tử miêu tả dãy ~b~.

Output

• Gồm một số nguyên không âm miêu tả kết quả bài toán.

Constraints

• ~1 \le n,m \le 200~
• ~0 \le a_i < 2^9~.

Subtasks

• Subtask ~1~: ~n \le 10, m = 2~ ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

4 2
2 6 4 0
2 4

Sample Output 1:

2

Explanation 1:

Ta có ~c_1 = a_1\&b_2 = 0~; ~c_2 = a_2\&b_1 = 2~; ~c_3 = a_3\&b_1 = 0~; ~c_4 = a_4\&b_1 = 0~.

Do đó ~c_1 | c_2 | c_3 | c_4 = 2~. Đây là kết quả nhỏ nhất ta có thể thu được.

Cho một dãy ~a_i~ gồm ~n~ phần tử nguyên không âm, hãy tính ~xor~ của tất cả các tập con không rỗng của dãy ~a~. Ở đây một tập con được định nghĩa là một dãy con không nhất thiết liên tiếp của các phần tử thuộc dãy ~a~.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả độ dài của dãy ~a~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.

Output

• In ra kết quả của bài toán.

Constraints

• ~1 \le n \le 100~.
• ~0 \le a_i \le 2*10^5~.

Subtasks

• Subtask ~1~: ~n \le 20~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

3
1 2 3

Sample Output 1:

0

Explaination 1:

Ta có: ~(1) \oplus (2) \oplus (3) \oplus (1 \oplus 2) \oplus(1 \oplus 3) \oplus (2 \oplus 3) \oplus (1 \oplus 2 \oplus 3) = 0~. Ở đây ~\oplus~ là phép ~xor~.

Sample Input 2:

1
5

Sample Output 2:

5

Explaination 2:

Chỉ có một tập con không rỗng là ~(5)~, vậy nên kết quả là ~5~.

Cây là một đồ thị vô hướng liên thông gồm ~n~ đỉnh và ~n-1~ cạnh. Cho một cây gồm ~n~ đỉnh và ~n-1~ cạnh ~(u,v)~ có trọng số là ~w~.

Gọi ~f(u,v)~ là tổng ~xor~ của trọng số các cạnh trên đường đi ngắn nhất từ đỉnh ~u~ tới đỉnh ~v~.

Hãy tính ~\sum f(u,v)~ ,~ \forall 1 \le u,v\le n~.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số đỉnh của cây.
• ~n-1~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ miêu tả cạnh nối ~2~ đỉnh ~(u,v)~ có trọng số là ~w~.

Output

• Gồm một số nguyên dương miêu tả kết quả bài toán.

Constraints

• ~1 \le n \le 10^5~
• ~0 \le w \le 10^6~.

Subtasks

• Subtask ~1~: ~n \le 1000~ ~(50\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(50\%)~

Sample Input 1:

4
1 2 3
1 3 4
2 4 1

Sample Output 1:

46

Cho dãy ~a~ gồm ~n~ phần tử nguyên không âm. Hai dãy con ~a_{i1}, a_{i2}, ..., a_{ik}~ và ~a_{j1}, a_{j2}, ..., a_{jq}~ được gọi là ăn nhập nếu:

• ~k,q > 0~;
• ~i_u \neq j_v \forall u,v~;
• ~a_{i1} \oplus a_{i2} \oplus ... \oplus a_{ik} = a_{j1} \oplus a_{j2} \oplus ... \oplus a_{jq}~; ở đây ~\oplus~ là phép toán ~xor~.
• ~max (i_1, i_2, ..., i_k, j_1, j_2, ..., j_q) - min (i_1, i_2, ..., i_k, j_1, j_2, ..., j_q) = k + q - 1~

Hãy đếm số cặp dãy con ăn nhập. Lưu ý là cặp dãy con ~x,y~ và ~y,x~ được xem là một cặp.

Input

• Dòng thứ nhất chứa số nguyên dương ~n~ miêu tả số phần tử trong dãy.
• Dòng thứ hai gồm ~n~ phần tử miêu tả dãy ~a~.

Output

• Gồm một số nguyên dương miêu tả kết quả bài toán, sau khi chia lấy dư cho ~10^9+7~.

Constraints

• ~1 \le n \le 10^5~
• ~0 < a_i \le 10^9~.

Subtasks

• Subtask ~1~: ~n \le 20~ ~(30\%)~
• Subtask ~2~: ~n \le 1000~ ~(40\%)~
• Subtask ~3~: Không có ràng buộc gì thêm ~(30\%)~

Sample Input 1:

6
3 1 5 3 2 6

Sample Output 1:

31