Các con gà trong trang trại Bedao đang ra sức phát triển và sinh nở. Mỗi con gà sẽ đẻ quả trứng đầu tiên vào thời điểm ~t~. Cứ sau ~k~ đơn vị thời gian con gà ấy sẽ tiếp tục đẻ trứng. Lihwy là chủ trang trại và anh ấy đang rất muốn quan tâm đến số lượng trứng thu được tại thời điểm ~n~. Hãy giúp Lihwy giải quyết bài toán trên nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~m~ ~(m \le 200)~ - số lượng con gà trong trang trại Bedao.

Mỗi dòng trong ~m~ dòng tiếp theo chứa ba số nguyên không âm ~t~, ~k~, ~n~ ~(0 \le t, n \le 10^{18}, 1 \le k \le 10^{18})~.

Output

Với mỗi con gà, hãy in ra số lượng quả trứng mà Lihwy thu được.

Scoring

Sample Input 1

5
0 1 1
1 1 1
1 1 0
0 1 0
0 2 2

Sample Output 1

2
1
0
1
2

Notes

Con gà thứ nhất đẻ trứng vào các thời điểm ~0~, ~1~, ~2~, ~3~, ... Tại thời điểm ~1~ ta sẽ thu được hai quả trứng.

Lihwy đang bận rộn chuẩn bị cho Bedao contest mới nhất. Lihwy có một danh sách các bài tập, được đánh dấu từ ~1~ đến ~n~. Ban đầu, các bài tập có độ khó là ~A_i = 0~. Tại ~q~ thời điểm sẽ có một trong hai việc sau xảy ra:

~1~ ~l~ ~r~ ~x~ ~(1 \le x \le 10^9)~: Với những bài tập ~i~ thoả mãn ~l \le i \le r~, Lihwy đã thêm thắt dữ kiện để bài tập đó trở nên khó hơn. Độ khó mới của bài tập thứ ~i~ luôn là ~A_i = A_i \oplus x~ với ~\oplus~ là phép toán xor.

~2~ ~l~ ~r~: Anh ấy muốn biết tổng xor độ khó của các bài tập trong đoạn ~[l, r]~. Nói cách khác, hãy tính giá trị ~A_l \oplus A_{l + 1} \oplus ... \oplus A_r~. Sau đó, do không hài lòng về kết quả, Lihwy sẽ xoá toàn bộ những dữ kiện thêm thắt của ~n~ bài tập. Lúc này độ khó tất cả các bài tập trở thành ~0~.

Hãy giúp Lihwy tính toán để Lihwy có thể chuẩn bị một contest Bedao chất lượng nhất nhé!

Input

Dòng đầu chứa hai số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 2 \times 10^5)~.

~q~ dòng tiếp theo chứa một trong hai sự việc.

Output

Với mỗi sự việc loại ~2~, in ra tổng độ khó cần tìm.

Scoring

Sample Input 1

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

Sample Output 1

1
2

Notes

Sau sự việc thứ nhất, độ khó các bài là ~[1, 1, 1]~. Do đó tổng xor độ khó đoạn ~[1, 3]~ là ~1~.

Sau sự việc thứ hai, độ khó tất cả các bài tập trở thành ~0~.

Sau sự việc thứ ba, độ khó các bài là ~[2, 2, 0]~. Tổng xor độ khó đoạn ~[2, 2]~ là ~2~.

Lihwy có một dãy độ dài số ~a~ gồm ~n~ số nguyên không âm ~a_1, a_2, ..., a_n~.

FireGhost là bạn thân của Lihwy, cậu rất ham học và sự yêu thích đặc biệt với các số nguyên. Tuy nhiên, vì gia cảnh khó khăn, cậu không mua lấy nổi cho mình một số nguyên nào cả. Chính vì vậy, cậu quyết định sẽ mượn Lihwy các số nguyên để về nhà chơi.

Lihwy khá kĩ tính và ít khi cho ai động vào dãy số của mình. Nhưng vì tình cảm bạn bè, cậu đồng ý cho FireGhost mượn một vài con số, với điều kiện là không có chữ số nào trong những số FireGhost mượn xuất hiện nhiều hơn một lần. FireGhost muốn mượn các con số thỏa mãn điều kiện Lihwy đề ra, sao cho tổng các số mượn được có giá trị lớn nhất.

Các bạn hãy giúp cậu học trò nghèo FireGhost tính xem tổng lớn nhất của các số cậu mượn được là bao nhiêu nhé.

Input

Dòng đầu tiên chứa số nguyên ~t~ là số bộ test ~(1 \leq t \leq 3)~.

Mô tả của mỗi bộ test trong ~t~ bộ test như sau:

• Dòng đầu tiên chứa số nguyên dương ~n~ — độ dài dãy ~a~ ~(1 \leq n \leq 10^3)~.

• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~ ~(0 \leq a_i \leq 10^{15})~.

Output

• Gồm ~t~ dòng, dòng thứ ~i~ là tổng lớn nhất các số mà FireGhost mượn được trong bộ test thứ ~i~.

Scoring

Sample Input 1

1
5
34 23 12 45 66

Sample Output 1

68

Sample Input 2

1
5
1 31 23 13 10

Sample Output 2

33

Notes

Trong ví dụ thứ nhất, FireGhost sẽ mượn hai số nguyên giá trị ~23~ và ~45~. Cậu không thể mượn cặp số ~34~ và ~45~ vì chữ số ~4~ xuất hiện ~2~ lần. Số ~66~ không được chọn vì nó có hai chữ số giống nhau.

Trong ví dụ thứ hai, FireGhost sẽ mượn hai số nguyên giá trị ~23~ và ~10~.

Trung và FireGhost đã bị phù thủy xấu xa Lihwy nhốt vào mê cung!

Mê cung là một đồ thị gồm ~n~ phòng, các phòng được nối với nhau bởi các mật đạo; biết giữa hai căn phòng chỉ có tối đa một mật đạo, và không tồn tại mật đạo nối một căn phòng với chính nó. Hiện tại, Trung và FireGhost đang ở phòng ~1~, và để thoát ra ngoài, họ cần phải đi đến phòng ~n~. Tuy nhiên, mỗi căn phòng đều có một con quái vật đáng sợ đang chờ họ sẵn, biết con quái vật trong phòng thứ ~i~ có sức mạnh ~a_i~.

Giữa lúc đang đau khổ, thần đèn Alànhddin xuất hiện và ban cho Trung và FireGhost một thanh kiếm với sức mạnh tuỳ ý để đánh bại đám quái vật! Nếu 2 người chọn thanh kiếm có sức mạnh ~x~, họ có thể đánh bại toàn bộ quái vật có sức mạnh không vượt quá ~x~; ngược lại, họ sẽ bị con quái vật đó nuốt chửng.

Tuy nhiên, Alànhddin là một kẻ tư bản: nếu Trung và FireGhost sử dụng thanh kiếm có sức mạnh là ~x~ và số quái vật mà Trung và FireGhost cần phải tiêu diệt ít nhất để đến căn phòng ~n~ là ~y~, họ sẽ phải trả cho Alànhddin số tiền là ~|x - y|~. Hãy giúp Trung và FireGhost chọn thanh kiếm có sức mạnh phù hợp để số tiền phải trả là ít nhất có thể nhé!

Input

Dòng đầu tiên chứa số nguyên dương ~n~ và ~m~ (~1 \le n \le 10^5, 0 \le m \le 2 \cdot 10^5~) — lần lượt là số phòng và số mật đạo trong mê cung.

Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le n~) — sức mạnh của con quái vật trong căn phòng thứ ~i~.

~m~ dòng tiếp theo, dòng thứ ~j~ gồm ~2~ số nguyên dương ~u_j, v_j~ (~1 \le u_j, v_j \le n~) thể hiện một mật đạo nối ~2~ căn phòng ~u_j~ và ~v_j~.

Output

Một số nguyên duy nhất là đáp án của bài toán: số tiền ít nhất mà Trung và FireGhost phải trả. Nếu Trung và FireGhost không thể đến được căn phòng ~n~, in ra đáp án ~-1~.

Scoring

Sample Input 1

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

Sample Output 1

1

Sample Input 2

2 0
1 2

Sample Output 2

-1

Notes

Trong test ví dụ thứ nhất, khi đi từ ~1~ đến ~4~, bạn phải lần lượt đánh bại ~3~ con quái vật có sức mạnh ~1~, ~4~, ~2~. Nếu thanh kiếm có sức mạnh là ~4~, Trung và FireGhost sẽ có thể đến được căn phòng ~4~ với chi phí là ~|4-3| = 1~. Vậy đáp án là ~1~.

Cho hai dãy ~a~ và ~b~ cùng có ~n~ phần tử nguyên. Ta định nghĩa hàm ~sum(x,y)~ ~(1 \le x,y \le n)~ như sau:

• Nếu ~x \le y~ thì ~sum(x,y) = a_x + a_{x+1} + a_{x+2} + ... + a_y~.

• Nếu ~x > y~ thì ~sum(x,y) = b_x + b_{x-1} + b_{x-2} + ... + b_y~.

Nhiệm vụ mà Lihwy đặt ra cho bạn là, hãy chọn ra hai đoạn ~[x,y]~ ~(1 \le x \le y \le n)~ và ~[c,d]~ ~(1 \le c \le d \le n)~ sao cho ~S = \sum sum(i,j)~ với mọi ~x \le i \le y~ và ~c \le j \le d~ là lớn nhất.

Input

• Dòng đầu gồm số nguyên dương ~n~ (~1 \le n \le 400~).

• Dòng thứ hai gồm ~n~ số nguyên miêu tả dãy ~a~ ~(-10^6 \le a_i \le 10^6)~.

• Dòng thứ ba gồm ~n~ số nguyên miêu tả dãy ~b~ ~(-10^6 \le b_i \le 10^6)~.

Output

• In ra ~S~ lớn nhất tìm được.

Scoring

Sample Input 1

5
1 4 2 -1 -2
-2 -1 1 2 -1

Sample Output 1

45

Notes

Chọn đoạn ~[1,5]~ và ~[2,5]~.

Lihwy tuy là một Master Codeforces, Coordinator Bedao, Admin Vloy nhưng lại gặp khó khăn ở một bài toán sau, các bạn hãy giúp Lihwy nhé!

Cho hai số nguyên dương ~n~ và ~q~. Bạn cần thực hiện ~q~ truy vấn sau trên ba dãy số nguyên dương ~A~, ~B~ và ~C~ có ~n~ phần tử:

~1~ ~x~ ~y~ ~k~: Với mọi ~0 \le i < k~, ta thực hiện thao tác ~B_{y + i} = A_{x + i}~.

~2~ ~x~ ~y~ ~k~: Với mọi ~0 \le i < k~, ta thực hiện thao tác ~C_{y + i} = B_{x + i}~.

~3~ ~x~: In ra giá trị phần tử ~C_x~.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(1 \le n, q \le 5 \times 10^5)~ - độ dài của dãy số nguyên dương và số lượng truy vấn.

Dòng thứ hai gồm ~n~ số nguyên dương ~A_1, A_2, ..., A_n~ ~(1 \le A_i \le 5 \times 10^5)~.

Dòng thứ ba gồm ~n~ số nguyên dương ~B_1, B_2, ..., B_n~ ~(1 \le B_i \le 5 \times 10^5)~.

Dòng thứ tư gồm ~n~ số nguyên dương ~C_1, C_2, ..., C_n~ ~(1 \le C_i \le 5 \times 10^5)~.

~q~ dòng tiếp theo chứa một trong ba loại truy vấn. Với các truy vấn loại ~1~ và ~2~, dữ liệu đảm bảo ~max(x, y) + k \le n + 1~. Với các truy vấn loại ~3~, ta luôn có ~1 \le x \le n~.

Output

Với mỗi truy vấn loại ~3~, in ra đáp án.

Scoring

Sample Input 1

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

Sample Output 1

3
4

Notes

Tại trước thời điểm truy vấn ~3~ đầu tiên, dãy ~C~ là ~[2, 4, 3, 5, 1]~. Do đó ~C_3 = 3~.

Tại trước thời điểm truy vấn ~3~ thứ hai, dãy ~C~ là ~[3, 5, 4, 5, 1]~. Do đó ~C_3 = 4~.