Cho dãy số ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~. Cho ~q~ truy vấn gồm hai loại:

• ~1 \; l \; r~: Tính tổng ~a_l + a_{l+1} + ... + a_r~.
• ~2 \; l \; r \; x~: Thực hiện phép xor với ~x~ với các phần tử trong đoạn ~[l, r]~, tức ~a_l=a_l \oplus x, a_{l+1}=a_{l+1} \oplus x, ..., a_r=a_r \oplus x~.

Với mỗi truy vấn ~1~, bạn cần in ra kết quả của truy vấn đó.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ - số phần tử của mảng ~a~.
• Dòng thứ hai gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~ là giá trị ban đầu của các phần tử dãy ~a~.
• Dòng thứ ba gồm số nguyên dương ~q~ - số truy vấn.
• ~q~ dòng tiếp theo, mỗi dòng gồm một trong hai loại truy vấn đã nêu ở trên.

Output

Với mỗi truy vấn ~1~, bạn cần in ra kết quả của truy vấn đó. Kết quả của các truy vấn được in ra trên ~1~ dòng duy nhất.

Constraints

• ~1 \le n \le 10^5~.
• ~0 \le a_i \le 10^6~.
• ~1 \le q \le 5 \times 10^4~.
• ~1 \le l, r \le n~.
• ~1 \le x \le 10^6~.

Subtasks

• Subtask ~1~ ~(30 \%)~: ~a_i \le 1, x \le 1~.
• Subtask ~2~ ~(70 \%)~: Không có điều kiện gì thêm.

Sample Input 1

5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3

Sample Output 1

26
22
0
34
11

Cho một cây vô hướng gồm ~n~ đỉnh. Đỉnh thứ ~i~ ~(1 \le i \le n)~ có trọng số là ~a_i~, cạnh thứ ~i~ ~(1 \le i \le n-1)~ có trọng số là ~w_i~.

Định nghĩa hàm ~dist(u,v)~ là tổng trọng số của các cạnh trên đường đi đơn từ đỉnh ~u~ tới đỉnh ~v~.

Hãy tìm ~max(dist(u,v) \times gcd(a_u,a_v)) \forall u,v \in [1,n]~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên, số thứ ~i~ là ~a_i~ miêu tả trọng số của đỉnh thứ ~i~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số nguyên dương ~u_i,v_i,w_i~ miêu tả cạnh thứ ~i~ của cây.

Constraint

• ~1 \le n \le 10^5~
• ~1 \le a_i \le 10^5~
• ~1 \le w_i \le 10^5~

Subtask

• Subtask ~1~ ~(30\%)~: ~n \le 2000~.
• Subtask ~2~ ~(20\%)~: ~a_i = 1; \forall i \in [1,n]~
• Subtask ~3~ ~(30\%)~: ~n,a_i \le 4 \times 10^4~
• Subtask ~4~ ~(20\%)~: Không có ràng buộc gì thêm.

Output

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

Sample Input 1:

2
10 10
1 2 10

Sample Output 1:

100

Trên trục tọa độ ~OX~ có ~n~ chuồng cừu. Chuồng thứ ~i~ ở vị trí ~x_i~ và có ~w_i~ con cừu ở đó.

Màn đêm sắp buông xuống, để tiện canh gác, bác nông dân ~ABC~ muốn dồn các con cừu vào đúng ~k~ chuồng phân biệt. Tuy nhiên, việc này cần được thực hiện sớm trước khi đêm về, vậy nên bác cần tìm cách dồn cừu sao cho mất ít thời gian nhất.

Biết thời gian để dồn các con cừu ở chuồng thứ ~i~ về chuồng thứ ~j~ là ~|x_i-x_j|\times w_i~, hãy xem nếu dồn tối ưu, thời gian ngắn nhất để các con cừu đều nằm ở trong đúng ~k~ chuồng là bao nhiêu,

Input

• Dòng đầu ghi hai số nguyên dương ~n,k~.
• ~n~ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương ~x_i~ và ~w_i~ miêu tả tọa độ và số cừu của chuồng thứ ~i~.

Giới hạn

• ~k \le n \le 5000~.
• ~1 \le x_i \le 10^9~.
• ~1 \le w_i \le 10^6~.

Subtask

• ~20\%~ số test thỏa mãn: ~k=1~.
• ~30\%~ số test thỏa mãn: ~n \le 400~.
• ~30\%~ số test thỏa mãn: ~n \le 2000~.
• ~20\%~ số test không có ràng buộc gì thêm.

Output

In ra thời gian tối ưu để dồn các con cừu về đúng ~k~ chuồng.

Sample Input 1

6 2
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 1

182

Sample Input 2

3 1
20 1
30 1
40 1

Sample Output 2

20