Có một đàn kiến gồm ~n~ con xếp thành một hàng ngang. Con thứ ~i~ có sức mạnh ~s_i~.

Một trò chơi thường niên được tổ chức, kiến chúa sẽ chọn ra đoạn các con kiến ~[l,r]~ bất kì, sau đó cho chúng đấu với nhau. Tuy nhiên, theo luật của loài kiến, nếu con kiến ~i~ đấu với con kiến ~j~, ~i~ sẽ thắng nếu ~s_i~ là ước của ~s_j~ và ngược lại ~j~ sẽ thắng nếu ~s_j~ là ước của ~s_i~. Nếu ~s_i = s_j~ thì cả hai sẽ hòa và đều được ~1~ điểm, ngược lại nếu con nào thắng sẽ được ~1~ điểm. Nếu ~s_i~ và ~s_j~ không có số nào là ước của nhau thì không con nào được điểm. Một con được coi là vô địch nếu nó có thể kiếm được ~r-l~ điểm từ các con còn lại. Ngược lại, nó sẽ thua.

Để chọn ra đoạn con tốt nhất, kiến chúa muốn thử thực hiện trò chơi ~q~ lần, mỗi lần chọn ra một đoạn ~[l,r]~, xem rằng liệu có bao nhiêu con kiến sẽ bị thua nếu thực hiện trò chơi trên đoạn này.

Input

• Dòng đầu ghi số nguyên dương ~n~.
• Dòng sau gồm ~n~ số nguyên dương ~s_1,s_2, ..., s_n~.
• Dòng sau gồm số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~l,r~ miêu tả thử nghiệm của kiến chúa.

Constraints

• ~1 \le n \le 10^5~
• ~1 \le s_1,s_2, ..., s_n \le 10^{18}~
• ~1 \le q \le 10^5~
• ~1 \le l \le r \le n~

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Input 1

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

Sample Output 1

4
4
1
1

Có ~n~ bông hoa được xếp thành một hàng trong vườn hoa của Taro. Với mỗi ~i~ ~(1 \le i \le n)~, chiều cao và vẻ đẹp của bông hoa thứ ~i~ từ trái sang phải lần lượt là ~h_i~ và ~a_i~. Trong vườn hoa, chiều cao của các bông hoa ~h_1,h_2,...,h_n~ phân biệt và đôi một với nhau.

Taro đang nhổ một số bông hoa đi để những bông hoa còn lại trong vườn thỏa mãn điều kiện sau đây:

• Chiều cao của các bông hoa còn lại tăng dần từ trái sang phải.

Taro muốn vườn hoa của mình là đẹp nhất có thể, vậy nên Taro muốn bỏ đi các bông hoa sao cho tổng vẻ đẹp của những bông hoa còn lại là lớn nhất. Tuy nhiên, Taro đang bận làm bài tập nên đã nhờ bạn giúp việc này. Hãy giúp Taro in ra tổng vẻ đẹp lớn nhất có thể của các bông hoa còn lại.

Input

• Dòng đầu gồm số nguyên dương ~n~ ~(1 \le n \le 2 \times 10^5)~.
• Dòng sau gồm ~n~ số nguyên ~h_i~ ~(1 \le h_i \le N)~ phân biệt đôi một.
• Dòng thứ ba chứa ~n~ số nguyên ~a_i~ ~(1 \le a_i \le 10^9)~

Output

• In ra tổng vẻ đẹp của những bông hoa còn lại.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

4
3 1 4 2
10 20 30 40

Sample Output 1

60

Sample Input 2

9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5

Sample Output 2

31

Cho dãy ~a~ gồm ~n~ phần tử.

Ta thực hiện ~q~ truy vấn có dạng là một trong các dạng như sau:

• Cho đoạn ~[l,r]~, in ra tổng của đoạn ~[l,r]~.
• Cho đoạn ~[l,r]~ và một số ~x~, với mỗi phần tử ~i \in [l,r]~, gán ~a_i = a_i \mod x~.
• Cho số ~k~ và ~x~, gán ~a_k = x~.

Input

• Dòng đầu ghi ~2~ số nguyên dương ~n~ và ~q~.
• Dòng sau gồm ~n~ số nguyên dương ~a_1,a_2, ..., a_n~.
• ~q~ dòng sau, mỗi dòng gồm:
  • Số nguyên dương ~t~ là loại của truy vấn.
  • Nếu ~t=1~, nhận thêm hai số nguyên dương ~l,r~.
  • Nếu ~t=2~, nhận thêm ba số nguyên dương ~l,r,x~.
  • Nếu ~t=3~, nhận thêm hai số nguyên dương ~k,x~.

Constraints

• ~1 \le n,q \le 10^5~
• ~1 \le a_1,a_2, ..., a_n \le 10^{9}~
• ~1 \le x \le 10^9~.
• ~1 \le l \le r \le n~

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Input 1

10 10
6 9 6 7 6 1 10 10 9 5
1 3 9
2 7 10 9
2 5 10 8
1 4 7
3 3 7
2 7 9 9
1 2 4
1 6 6
1 5 9
3 1 10

Sample Output 1

49
15
23
1
9

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một số nguyên dương ~k~. Hãy in ra đoạn con liên tiếp có tổng lớn thứ ~k~. (Có ~n*(n+1)/2~ đoạn con liên tiếp trong dãy).

Input

• Dòng đầu gồm 2 số nguyên dương ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(1 \le k \le n*(n+1)/2)~.
• Dòng thứ 2 gồm ~n~ số nguyên miêu tả dãy ~a~. ~(-10^9 \le a_i \le 10^9)~.

Ouput

• In ra giá trị của đoạn con liên tiếp có tổng lớn thứ ~k~.

Sample Test

Input

4 3
1 -1 2 -2

Output

1

Giải thích: đoạn con ~[1,3], [3,3]~ là hai đoạn con có giá trị lớn nhất với tổng bằng ~2~. Tiếp đến là hai đoạn con ~[1,1], [2,3]~ có tổng bằng ~1~ có giá trị lớn thứ ~3~ và ~4~. Vậy đoạn con có giá trị lớn thứ ~k~ sẽ có giá trị bằng ~1~.

Các nghiện thủ đang bị nhốt trong căn phòng có 1 mật mã được mã hóa trong mảng ~A~ có độ dài ~n~. Bởi muốn nghiện Liên Quân, thần đồng đã sai người tìm và giải mã nó. Ta biết được mảng ~A~ có thể chia thành nhiều dãy con liên tiếp (và có ~2^{n-1}~ cách chia ). Với mỗi dãy con được chia, giá trị của dãy con đấy nếu gồm các số từ vị trí ~l~ đến ~r~ là :

• ~r \;– \; l + 1 ~ nếu tổng các số từ ~l~ đến ~r~ lớn hơn hẳn 0.
• 0 nếu tổng các số từ ~l~ đến ~r~ bằng 0.
• ~–(r \;– \; l + 1)~ nếu tổng các số từ ~l~ đến ~r~ nhỏ hơn hẳn 0.

Gọi ~S~ là tổng các giá trị của dãy con trong 1 cách chia. Mã hóa của căn phòng là ~S~ lớn nhất trong tất cả các cách chia. Biết rằng tin Ams 21-24 toàn những feeder liên quân và best tin học, thần đồng muốn nhờ các bạn tìm mật mã trên.

Input

• Dòng đầu tiên gồm số ~n~
• Dòng tiếp theo gồm ~n~ số của mảng ~A~

Output

• In ra một số là giá trị ~S~ lớn nhất tìm được.

Sample Test

Input:

5
-1 -2 3 -1 -1

Output

1

Sample Test 2

Input:

6
-1 2 -3 4 -5 6

Output

6

Sample Test 3

7
1 -1 -1 1 -1 -1 1

Output

-1

Giải thích:

• Test 1 chia thành (-1 -2 ) (3 -1 -1)
• Test 2 chia thành (-1 2 -3 4 -5 6)
• Test 3 chia thành (1 -1 -1 1 -1) (-1 1)

Ràng buộc:

• ~A_i \le 10^9~
• Subtask 1: ~n \le 20~ (30%)
• Subtask 2: ~n \le 5000~ (40%)
• Subtask 3: ~n \le 5*10^5~ (30%)

Cho một xâu nhị phân S độ dài ~n~ (các chỉ số được đánh số từ ~1~) và ~q~ truy vấn thuộc một trong hai loại:

• ~1 \; u \; x~: Gán ~S_u = x~, trong đó ~x \in \{0, 1\}~.
• ~2 \; u \; v \;x~: Kiểm tra xem hai xâu ~S[u..u+x-1]~ và ~S[v..v+x-1]~ có bằng nhau không. Nói cách khác, kiểm tra xem hai xâu con liên tiếp độ dài ~x~ bắt đầu từ ~u~ và ~v~ có bằng nhau không?

Với mỗi truy vấn ~2~, hãy in ra ~1~ nếu hai xâu bằng nhau, ~0~ là ngược lại.

Input

• Dòng đầu tiên gồm xâu ~S~ có độ dài ~n~.
• Dòng thứ hai gồm số nguyên ~q~ - số truy vấn.
• ~q~ dòng sau, mỗi dòng là ba hoặc bốn số nguyên dương thuộc một trong hai loại như miêu tả trên.

Constraints

• ~1 \le n, q \le 2 \times 10^5~
• ~1 \le u + x - 1, v + x - 1 \le n~

Subtasks

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

Output

• Gồm một xâu nhị phân gồm ~q~ kí tự ~0~ và ~1~.

Sample Input 1:

1000100
3
2 1 5 3
1 3 1
2 1 3 3

Sample Output 1:

11

Explanation 1:

Truy vấn đầu tiên có ~S[1..3] = 100~, ~S[5..7] = 100~. Truy vấn thứ hai xâu ~S~ trở thành ~1010100~ Truy vấn thứ ba có ~S[1..3] = 101~, ~S[3..5] = 101~.

Một dãy số ~(b_1, b_2, ..., b_m)~ được gọi là có thể tối giản nếu tồn tại một phần tử *~x~ thỏa mãn:*

• ~x~ là duy nhất trong dãy.

• Mọi phần tử ~b_1, b_2, ..., b_m~ đều chia hết cho ~x~.

Cho dãy ~a~ gồm ~n~ phần tử ~a_1, a_2, ..., a_n~, hãy đếm số cặp chỉ số ~(l, r)~ sao cho dãy ~a_l, a_{l+1}, ..., a_r~ là dãy có thể tối giản. ~(1 \le l < r \le 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 dương ~a_1, a_2, ..., a_n~ .

Constraints

• ~1 \le n \le 3 * 10^5~.
• ~1 \le a_i \le 10^9~.

Subtask

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

Output

• Gồm một dòng duy nhất là số dãy tìm được.

Sample Input 1

5
4 3 6 4 2

Sample Output 1

3

Notes

• Các đoạn thỏa mãn là ~[2, 3], [4, 5], [3, 5]~.

Marmot có ~n~ cột trụ xếp trên một hàng. Cột thứ ~i~ có độ dài ~h_i~. Bắt đầu từ cột trụ ~i_1~, Marmot muốn nhảy tới cột trụ ~i_2,i_3,...,i_k~ ~(1 \le i_1 < i_2 < ... < i_k \le n)~. Từ cột trụ ~i~, Marmot chỉ có thể nhảy tới cột trụ ~j~ khi và chỉ khi ~i < j~ và ~|h_i - h_j| \ge d~, ở đây ~|x|~ là giá trị tuyệt đối của ~x~.

Marmot muốn nhờ bạn tìm một cách nhảy sao cho có thể nhảy qua được nhiều cột trụ nhất.

Input

• Dòng đầu ghi hai số nguyên dương ~n~ và ~d~ ~(1 \le n \le 10^5, 0 \le d \le 10^9)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~h_1,h_2,...,h_n~.

Output

• Dòng đầu tiên in ra số ~k~, số cột tối đa có thể nhảy.
• Dòng thứ hai gồm ~k~ số nguyên dương, ~i_1,i_2,...,i_k~ ~(1 \le i_1 < i_2 < ... < i_k)~, là chỉ số của các cột nhảy qua.

Subtasks

• Subtask 1: ~n \leq 5000~. (50%)
• Subtask 2: Không giới hạn gì thêm.

Sample Input 1

5 2
1 3 6 7 4

Sample Output 1

4
1 2 3 5 

Sample Input 2

10 3
2 1 3 6 9 11 7 3 20 18

Sample Output 2

6
1 4 6 7 8 9 

Cho dãy ~a~ gồm ~n~ phần tử nguyên và một hoán vị ~p~ độ dài ~n~.

Ta thực hiện một trò chơi gồm ~n~ bước như sau: ở bước thứ ~i~, ta xóa đi phần tử ~p_i~.

Yêu cầu: Trước khi thực hiện mỗi bước, hãy in ra tổng lớn nhất của đoạn con gồm các phần tử liên tiếp chưa có phần tử nào bị xóa trên dãy ~a~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ miêu tả độ dài dãy ~a~ và hoán vị ~p~ ~(1 \le n \le 5*10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a_1,a_2,...,a_n~ ~( |a_i| \le 10^9)~
• Dòng thứ ba gồm ~n~ số nguyên dương miêu tả dãy hoán vị ~p_1,p_2,...,p_n~

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra giá trị của đoạn con gồm các phần tử liên tiếp chưa có phần tử nào bị xóa và có tổng lớn nhất trước bước thứ ~i~.

Subtask

• Subtask ~1~ (~30~ điểm): ~n \le 5000~
• Subtask ~2~ (~30~ điểm): ~a_i > 0~
• Subtask ~3~ (~40~ điểm): Không ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

7
6
4
3
3
2
2

Explanation 1

• Trước khi thực hiện thao tác ~1~, dãy là ~4~ ~-1~ ~2~ ~-3~ ~4~ ~-2~ ~3~, đoạn con lớn nhất thỏa mãn là ~[1,7]~
• Trước khi thực hiện thao tác ~2~, dãy là ~4~ ~-1~ ~2~ ~-3~ ~4~ ~*~ ~3~, đoạn con lớn nhất thỏa mãn là ~[1,5]~
• Trước khi thực hiện thao tác ~3~, dãy là ~*~ ~-1~ ~2~ ~-3~ ~4~ ~*~ ~3~, đoạn con lớn nhất thỏa mãn là ~[5,5]~
• Trước khi thực hiện thao tác ~4~, dãy là ~*~ ~-1~ ~2~ ~-3~ ~*~ ~*~ ~3~, đoạn con lớn nhất thỏa mãn là ~[7,7]~
• Trước khi thực hiện thao tác ~5~, dãy là ~*~ ~*~ ~2~ ~-3~ ~*~ ~*~ ~3~, đoạn con lớn nhất thỏa mãn là ~[7,7]~
• Trước khi thực hiện thao tác ~6~, dãy là ~*~ ~*~ ~2~ ~-3~ ~*~ ~*~ ~*~, đoạn con lớn nhất thỏa mãn là ~[3,3]~
• Trước khi thực hiện thao tác ~7~, dãy là ~*~ ~*~ ~2~ ~*~ ~*~ ~*~ ~*~, đoạn con lớn nhất thỏa mãn là ~[3,3]~

Nhắc lại ~F_n~ là số fibonacci thứ ~n~ với ~F_1 = F_2 = 1~.

Cho mảng ~a~ có ~n~ phần tử và ~q~ truy vấn có một trong 2 dạng sau đây:

• 1 l r, cộng thêm giá trị ~F_{i - l + 1}~ với mỗi phần tử ~l \le i \le r~.
• 2 l r, in ra ~\sum_{i=l} ^{r} a_i~ modulo ~10^9+9~.

Input

• Dòng đầu tiên gồm 2 số ~1 \le n, q \le 300000~.
• Dòng tiếp theo gồm ~n~ số tự nhiên của mảng ~a~ (~1 \le a_i \le 10^9~).

Output

• In ra kết quả của mỗi truy vấn 2.

Sample Test

Input:

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

Output:

17
12

Cho một dãy ngoặc ~s~ gồm ~n~ phần tử, phần tử thứ ~i~ là ~s_i~ có thể bằng ~'('~ hoặc ~')'~.

Bạn cần trả lời ~q~ truy vấn, truy vấn thứ ~i~ có dạng: ~l_i,r_i~, yêu cầu cần tìm một dãy con (không nhất thiết liên tiếp) dài nhất của đoạn ~[l_i,r_i]~ sao cho nó tạo thành một dãy ngoặc đúng.

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc đúng.
• Nếu ~A~ là một dãy ngoặc đúng thì ( ~A~ ) là một dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng.

Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Input

• Dòng đầu gồm một xâu kí tự miêu tả dãy ~s~.
• Dòng thứ hai gồm số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~l_i~ và ~r_i~ miêu tả truy vấn thứ ~i~.

Constraints

• ~n \le 2 \times 10^5~
• ~1 \le a_i \le 10^6~

Subtask

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

Output

• Với mỗi truy vấn, in ra kết quả tương ứng.

Sample Input 1:

())(())(())(
7
1 1
2 3
1 2
1 12
8 12
5 11
2 10

Sample Output 1:

0
0
2
10
4
6
6

Cho một dãy ngoặc ~s~ gồm ~n~ phần tử, phần tử thứ ~i~ là ~s_i~ có thể bằng ~'('~ hoặc ~')'~.

Bạn cần trả lời ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

• ~1~ ~l~ ~r~: Yêu cầu cần tìm một dãy con (không nhất thiết liên tiếp) dài nhất của đoạn ~[l,r]~ sao cho nó tạo thành một dãy ngoặc đúng.
• ~2~ ~l~ ~r~: Đảo kí tự của các phần tử trong đoạn ~[l,r]~, cụ thể, từ ( sang ) và ngược lại.

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc đúng.
• Nếu ~A~ là một dãy ngoặc đúng thì ( ~A~ ) là một dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng.

Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~.
• Dòng thứ hai gồm một xâu kí tự miêu tả dãy ~s~.
• Dòng thứ ba gồm số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~t~, ~l~ và ~r~ miêu tả truy vấn thứ ~i~.

Constraints

• ~2 \le n,q \le 10^6~

Output

• Với mỗi truy vấn loại ~2~, in ra độ dài dãy con tìm được.

Sample Input 1:

10
())(())(()
5
1 2 5
2 3 6
1 2 6
2 1 5
1 1 10

Sample Output 1:

0
2
6

Cho một dãy số nguyên ~a~ gồm ~n~ phần tử.

Bạn có ~q~ truy vấn ở một trong hai dạng:

• ~1~ ~x~ ~y~: Gán ~a_x = y~
• ~2~ ~l~ ~r~: Đếm số đoạn con không giảm trong đoạn con ~[a_l,a_{l+1},...,a_r]~. Nói cách khác, hãy đếm số bộ ~(p,q)~ sao cho ~l \le p \le q \le r~ và ~a_p \le a_{p+1} \le ... \le a_{q-1} \le a_q~.

Input

• Dòng đầu gồm hai số nguyên dương ~n,q~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng miêu tả một truy vấn. Nó có dạng "~1~ ~x~ ~y~" hoặc "~2~ ~l~ ~r~".

Constraints

• ~n \le 2 \times 10^5~
• ~1 \le x,y,a_i \le 10^9~

Subtask

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

Output

• Với mỗi truy vấn loại ~2~, in ra kết quả tương ứng.

Sample Input 1:

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

Sample Output 1:

6
4
10
7

Có ~n~ đồng xu được xếp theo thứ tự từ ~1~ tới ~n~ trên mặt đất, mỗi đồng xu có hai mặt: mặt ngửa của đồng xu thứ ~i~ ghi số ~a_i~, mặt sấp của đồng xu thứ ~i~ ghi số ~𝑏_𝑖~.

Phép lật với tham số ~C~ thực hiện như sau: Chọn tất cả các đồng xu có số ở mặt ngửa nhỏ hơn hoặc bằng ~C~ và lật chúng lại. Khi mỗi đồng xu bị lật, mặt ngửa trở thành mặt sấp và ngược lại, mặt sấp trở thành mặt ngửa.

Các sinh viên được cho biết trạng thái ban đầu của ~𝑛~ đồng xu và một dãy ~m~ phép lật với các tham số ~𝑐_1~, ~𝑐_2~, … , ~𝑐_𝑚~ cho trước. Nhiệm vụ của bạn là phải cho biết dãy các số ghi trên mặt ngửa của các đồng xu sau ~𝑚~ phép lật theo đúng thứ tự đã cho.

Input

• Dòng đầu gồm hai số nguyên dương ~n,m~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~a_i,b_i~
• ~m~ dòng sau, dòng thứ ~i~ chứa số nguyên dương ~c_i~.

Constraints

• ~2 \le n,m \le 2\times10^5~
• ~1 \le a_i,c_i \le 10^9~

Output

• In ra dãy số ghi trên mặt ngửa của các đồng xu sau khi biến đổi.

Sample Input 1:

5 3
4 6
9 1
8 8
4 2
3 7
8
2
9

Sample Output 1:

4 1 8 2 3

Explanation 1:

4 9 8 4 3
6 1 8 2 7
Lật (8)
6 9 8 2 7
4 1 8 4 3
Lật (2)
6 9 8 4 7
4 1 8 2 3
Lật (9)
4 1 8 2 3
6 9 8 4 7

Cho một dãy ~a~ gồm ~n~ phần tử. Bạn cần

Có ~q~ truy vấn, mỗi truy vấn bạn được cung cấp ~4~ số nguyên dương ~[l,r,x,y]~, nghĩa là với mọi ~i \in [l,r]~, nếu ~a_i = x~ thì ta gán ~a_i = y~.

Hãy in ra dãy ~a~ sau khi thực hiện cả ~q~ truy vấ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 dương miêu tả dãy ~a~.
• Dòng thứ ba gồm số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, mỗi dòng gồm ~4~ số nguyên dương ~l,r,x,y~

Constraints

• ~1 \le n \le 2\times10^5~
• ~1 \le a_i \le 50~
• ~1 \le q \le 2\times10^5~

Output

• In ra dãy ~a~ sau khi biến đổi.

Sample Input 1:

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

Sample Output 1:

5 2 5 4 5 

Dãy ngoặc là một dãy chỉ gồm các kí tự mở ngoặc ( và đóng ngoặc ). Dãy ngoặc đúng là một dãy ngoặc được xây dựng dựa trên quy tắc sau:

• Dãy ngoặc rỗng là một dãy ngoặc đúng.
• Nếu ~A~ là một dãy ngoặc đúng thì ( ~A~ ) là một dãy ngoặc đúng.
• Nếu ~A~ và ~B~ là hai dãy ngoặc đúng thì ~AB~ cũng là dãy ngoặc đúng.

Ví dụ, (()), ()() và ()(()) là các dãy ngoặc đúng; còn )( hay (() thì không.

Bạn được cho một xâu kí tự ~s~ là một dãy ngoặc đúng cùng dãy ~q~ số ~p_1,p_2,...,p_q~. Bạn cần thực hiện ~q~ lượt thao tác. Tại thao tác thứ ~i~, bạn cần làm những việc sau:

• Thay đổi kí tự thứ ~p_i~ của ~s~ (từ ( sang ) hoặc ngược lại) thì xâu kí tự ~s~ trở thành dãy ngoặc đúng.
• In ra vị trí ~a_i~ vừa tìm được và thay đổi kí tự ở vị trí này.

Chú ý rằng, ở bất kì thao tác nào, bạn bắt đầu khi xâu ~s~ đang là dãy ngoặc đúng. Do đó, việc thay đổi kí tự thứ ~p_i~ khiến ~s~ bây giờ chắc chắn không phải dãy ngoặc đúng, và ta dễ dàng chứng minh được vị trí ~a_i~ cần tìm ở trên là luôn tồn tại. Khi thay đổi kí tự ở vị trí ~a_i~, ~s~ trở lại là dãy ngoặc đúng.

Input: Nhập từ file "DAYNGOAC.INP"

• Dòng đầu tiên chứa hai số nguyên dương ~n,q~ ~(1 \le n \le 10^6, 1 \le q \le 6 \times 10^5)~, lần lượt là độ dài của dãy ngoặc và số thao tác bạn cần thực hiện.
• Dòng thứ hai chứa xâu kí tự ~s~ là một dãy ngoặc đúng độ dài ~n~ .
• Dòng thứ ba chứa ~q~ số nguyên ~p_1,p_2,...,p_n~ ~(1 \le p_q \le n)~ mô tả các thao tác cần thực hiện.

Output: Xuất ra file "DAYNGOAC.OUT"

In ra ~q~ số nguyên ~a_1,a_2,...,a_n~ là các vị trí tìm được ở các thao tác. Các số cần được viết trên một dòng, ngăn cách với nhau bởi dấu cách.

Subtask

• Subtask ~1~ (~20\%~ số test): ~n \le 500, q \le 300~.
• Subtask ~2~ (~30\%~ số test): ~n \le 7000, q \le 4200~.
• Subtask ~3~ (~25\%~ số test): ~n \le 2 \times 10^5, q \le 10^5~.
• Subtask ~4~ (~25\%~ số test): ~n \le 10^6, q \le 6\times10^5~.

Ví dụ

Sample Input 1

6 3
((()))
4 3 1

Sample Output 1

2 2 1

Giải thích

Trong ví dụ trên, ban đầu dãy ngoặc ~s~ là ((())). Các thao tác diễn ra như sau:

• Thao tác đầu tiên: Sau khi thay đổi kí tự ở vị trí ~p_1 = 4~, ~s~ trở thành (((()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_1 = 2~. Khi đó ~s~ trở thành ()(()).
• Thao tác tiếp theo: Sau khi thay đổi kí tự ở vị trí ~p_2 = 3~, ~s~ trở thành ())()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_2 = 2~. Khi đó ~s~ trở thành (()()).
• Thao tác cuối cùng: Sau khi thay đổi kí tự ở vị trí ~p_3 = 1~, ~s~ trở thành )()()), để ~s~ trở lại là dãy ngoặc đúng, bạn cần thay đổi kí tự ở vị trí ~a_3 = 1~. Khi đó ~s~ trở thành (()()).

Cho một tập ~S~ ban đầu rỗng, bạn cần thực hiện ~q~ truy vấn có dạng như sau:

• ~1~ ~x~: Thêm số nguyên ~x~ vào tập ~S~. ~(0 \le x \le 10^9)~

• ~2~ ~x~: Xóa số nguyên ~x~ ra khỏi tập ~S~, nếu số ~x~ xuất hiện nhiều lần, ta chỉ xóa nó một lần, nếu số đó không xuất hiện trong tập ~S~, ta bỏ qua truy vấn này.

• ~3~ ~L~ ~R~: In ra tổng các phần tử trong tập ~S~ có giá trị trong đoạn ~[L,R]~. ~(0 \le L \le R \le 10^9)~

• ~4~ ~k~: In ra phần tử bé thứ ~k~ trong tập ~S~. ~(1 \le K \le |S|)~

• ~5~ ~a~: In ra ~max (a \oplus x) \, \forall \, x \in S~, ở đây ~\oplus~ là phép ~xor~.

Input

Dòng đầu tiên gồm số nguyên ~q~ ~(1 \le q \le 2*10^5)~ mô tả số truy vấn.

~q~ dòng sau, mỗi dòng miêu tả một truy vấn.

Output

Mỗi dòng in ra kết quả theo thứ tự nhập vào của các truy vấn loại ~3,4,5~.

Sample Input 1

10
1 3
1 4
3 1 3
4 2
1 2
2 2
4 1
2 5
3 1 6
5 8

Sample Output 1

3
4
3
7
12

Cho một dãy số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~. Đếm số cách chia dãy này thành ~k~ đoạn con liên tiếp, thỏa mãn tổng ~XOR~ đoạn thứ ~i~ ~(i \le k)~ nằm trong đoạn ~[L_i, R_i]~.

Input

• Dòng thứ nhất gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^5, n * k \le 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1~, ~a_2~, ..., ~a_n~ ~(a_i \le 10^9)~.
• ~k~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~L_i~ và ~R_i~ là điều kiện của đoạn thứ ~i~ ~1 \le L_i \le R_i \le 10^9)~.

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán. Do kết quả có thể khá lớn, hãy in kết quả ~MOD~ ~10^9 + 7~.

Sample Input 1

4 2
1 2 3 4
1 4
2 10

Sample Output 1

2

Bờm viết một chương trình hỗ trợ học ngoại ngữ. Module quản lí từ vựng với phép tìm kiếm từ được Bờm xây dựng theo quy trình: giả sử danh sách từ chương trình đang có là ~w_1, w_2, . . . , w_N~ , mỗi khi nhận được mẫu tìm ~P~, chương trình sẽ lần lượt so sánh ~P~ với ~w_1, w_2, . . .~ cho đến khi gặp từ trùng với ~P~ hoặc đã hết danh sách từ. Khi so sánh ~P~ với các từ, chương trình sẽ lần lượt so sánh các kí tự từ trái qua phải cho đến khi gặp kí tự sai khác hay một trong hai từ kết thúc (khi đó nếu cả hai từ cùng kết thúc là tìm kiếm thành công).

Để khảo sát hiệu năng của module tìm kiếm, Bờm xây dựng một danh sách N từ và thực hiện tìm kiếm ~Q~ mẫu, với mỗi mẫu Bờm cần xác định số thao tác cơ sở mà chương trình thực hiện, thao tác cơ sở là một lần so sánh kí tự hoặc một lần xử lí khi gặp kết thúc từ. Số thao tác cơ sở thực hiện với mỗi mẫu tìm kiếm sẽ bằng tổng của: số lượng từ được so sánh với mẫu, độ dài của tiền tố chung dài nhất của mỗi từ với mẫu.

Hãy giúp Bờm thực hiện việc khảo sát trên mà không cần thực hiện chương trình của Bờm.

Input

• Dòng ~1~ gồm hai số nguyên ~N,Q~ ~(1 \le N,Q \le 3\times10^4)~
• ~N~ dòng sau, dòng thứ ~i~ ghi từ ~w_i~.
• ~Q~ dòng sau, mỗi dòng là một từ mẫu tì kiếm.

Tất cả các từ trong input đều có độ dài không quá ~30~ và chỉ chứa các chữ cái latin in thường.

Output

• Gồm ~Q~ dòng: dòng ~i~ ghi số nguyên là số thao tác cơ sở mà chương trình của Bờm sẽ thực hiện khi tìm kiếm từ mẫu thứ ~i~.

Sample Input 1

4 2
c
cvp
cvy
cvn
cv
cvy

Sample Output 1

11
9

Cho dãy số nguyên ~a = a_1, a_2, . . . , a_n~ và ~q~ truy vấn. Mỗi truy vấn có dạng ~(L, R, x)~, cần tìm ~i~ sao cho ~L \le i \le R~ và ~a_i \oplus x~ (~\oplus~ ở đây là toán tử ~Xor~) đạt giá trị lớn nhất. Các số ~a_i~ và ~x~ đều được cho dưới dạng nhị phân

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ ~q~ ~(1 \le n,q \le 10^5)~;
• Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa ~a_i~ ở dạng nhị phân;
• ~q~ dòng tiếp theo, mỗi dòng chứa ~L~ ~R~ ~x~ trong đó ~x~ ở dạng nhị phân;

Tất cả các số ngoài ~a_i~ và ~x~ đều được cho ở dạng thập phân, độ dài nhị phân của ~a_i~ và ~x~ đều không quá ~30~.

Output

• Với mỗi truy vấn, in ra kết quả trên một dòng. Nếu có nhiều ~i~ thỏa mãn ~a_i \oplus x~ đạt giá trị lớn nhất thì in ra ~i~ nhỏ nhất có thể.

Sample Input 1

5 4
100
101
1
1011
11
2 3 10
1 5 1100
3 5 1010
1 5 11100

Sample Output 1

2
5
3
5

Một lớp học nọ có ~n~ học sinh, tên của học sinh thứ ~i~ được biểu diễn bằng một string ~s_i~.

Có ~n~ biệt danh cũng được biểu diễn bằng các string ~p_i~.

Ta kí hiệu ~lcp(a,b)~ là độ dài tiền tố chung dài nhất giữa hai xâu ~a~ và ~b~.

Bạn có thể chọn ~c~ là dãy hoán vị từ ~1~ tới ~n~, tương đương với việc gán cho bạn thứ ~i~ biệt danh là ~p_{c_i}~. Cách chọn này có độ "hoàn hảo" là ~\sum lcp(s_i,p_{c_i}) \forall i \in[1,n]~.

Hãy tìm dãy hoán vị ~c~ có độ hoàn hảo lớn nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~.
• ~n~ dòng sau, dòng thứ ~i~ là xâu ~s_i~ miêu tả tên của bạn thứ ~i~.
• ~n~ dòng tiếp theo, dòng thứ ~i~ là xâu ~p_i~ miêu tả biệt danh thứ ~i~.
• Lưu ý rằng có thể có các tên hoặc biệt danh trùng với nhau.

Constraints

• ~1 \le n \le 10^5~
• Tổng kí tự của tất cả các xâu không quá ~10^6~.

Output

• In ra độ hoàn hảo lớn nhất tìm được.

Sample Input 1

3
chau
huy
hoang
homhinh
hoanhi
chumchim

Sample Output 1

7

Explanation 1

• chau sẽ ghép với chumchim và có ~lcp~ là ~2~.
• huy sẽ ghép với homhinh và có ~lcp~ là ~1~.
• hoang sẽ ghép với hoanhi và có ~lcp~ là ~4~.

Có ~n~ điểm từ ~1~ tới ~n~ trên trục tọa độ ~OX~. Điểm thứ ~i~ có màu ~c_i~.

Tại điểm ~i~, bạn có thể:

• Đi tới điểm ~i+1~ (nếu ~i \neq n~), tốn ~R~ giây.
• Đi tới điểm ~i-1~ (nếu ~i \neq 1~), tốn ~L~ giây.
• Tốc biến tới điểm ~j~ (nếu ~c_i = c_j~), tốn ~C~ giây.

Cho ~2~ điểm ~st~ và ~en~, hãy tính thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Input

• Dòng thứ nhất chứa ~4~ số nguyên dương ~n,L,R,C~.
• Dòng thứ hai gồm ~2~ số nguyên dương ~st~ và ~en~. ~(1 \le st \le en \le n)~
• Dòng thứ ba chứa ~N~ số nguyên dương ~c_1, c_2, ..., c_n~ là màu của từng điểm.

Output

• In ra thời gian ngắn nhất để đi từ ~st~ đến ~en~.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le L,R,C \le 10^9~.
• ~1 \le c_i \le 10^5~.

Sample Input 1:

5 1 2 3
1 5
1 2 1 1 2

Sample Output 1:

5

Sample Input 1:

5 1 4 3
3 5
1 2 1 1 2

Sample Output 1:

4

Subtasks

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

Cho một đồ thị gồm ~n~ đỉnh và ~m~ cạnh có hướng có trọng số.

Với mỗi đỉnh ~i~, hãy tính độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~.

Input

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

Output

• Gồm ~n~ dòng, dòng thứ ~i~ in ra độ dài của quãng đường ngắn nhất để đi xuất phát từ đỉnh ~1~, đi qua đỉnh ~i~ và quay về đỉnh ~1~. Nếu không có quãng đường nào như vậy thì in ra ~-1~.

Constraints

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

Subtasks

• Subtask ~1~: Nếu tồn tại cạnh ~(u,v,w)~ thì sẽ có cạnh ~(v,u,w)~. ~(30\%)~
• Subtask ~2~: Không có ràng buộc gì thêm ~(70\%)~

Sample Input 1:

5 7
1 4 5
1 5 3
3 5 2
5 4 10
5 1 7
3 2 5
2 1 1

Sample Output 1:

-1
-1
-1
10

Sample Input 2:

2 1
2 1 10

Sample Output 2:

-1

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường một chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và có chi phí ~t_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~. Tuy nhiên anh ta chỉ mang đúng ~K~ đồng tiền.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất từ thành phố ~1~ tới ~n~ mà chỉ mất tổng chi phí ít hơn hoặc bằng ~K~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• Dòng thứ hai chứa số nguyên dương ~K~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,t_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và chi phí ~t_i~.

Output

• In ra độ dài đường đi ngắn nhất từ ~1~ tới ~n~ mà tổng chi phí không quá ~K~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~ và tiêu không quá ~K~, in ra ~-1~.

Constraints

• ~1 \le n \le 100~.
• ~1 \le m \le 1000~.
• ~1 \le k \le 10000~.
• ~1 \le l_i \le 1000~.
• ~0 \le t_i \le 1000~.

Subtasks

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

Sample Input 1:

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

Sample Output 1:

11

Explanation 1:

Đi theo lộ trình ~(1,3,5,4,6)~.

Sample Input 2:

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

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~ tiêu không quá ~0~.

Đất nước ~ABC~ có ~n~ thành phố và ~m~ con đường hai chiều. Con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với nhau, có độ dài ~l_i~ và độ đẹp ~b_i~.

~H~ là một du khách. Hiện tại, anh đang ở thành phố ~1~ và cần đi tới thành phố ~n~ để dự sự kiện. Là một người đam mê cái đẹp, anh muốn chọn một lộ trình sao cho những con đường anh đi qua có tổng độ đẹp là lớn nhất, tuy vậy do cần tiết kiệm thời gian nên anh sẽ chỉ chọn lộ trình ngắn nhất (tức là tổng độ dài các con đường là bé nhất có thể) để đi từ ~1~ tới ~n~.

Hãy giúp ~H~ tính toán lộ trình ngắn nhất và có tổng độ đẹp lớn nhất mà anh ta có thể đi.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương ~n,m~.
• ~m~ dòng sau mỗi dòng gồm ~4~ số nguyên dương ~u_i,v_i,l_i,c_i~ ~(1 \le u, v \le n, u \neq v)~, miêu tả con đường nối thành phố ~u_i~ với ~v_i~ có độ dài ~l_i~ và độ đẹp ~c_i~.

Output

• Gồm một dòng chứa hai số nguyên ~L~ và ~B~, với ~L~ là độ dài của lộ trình ngắn nhất để đi từ ~1~ tới ~n~ và ~B~ là độ đẹp lớn nhất có thể của các lộ trình có độ dài ~L~.
• Nếu không có lộ trình nào để đi từ ~1~ tới ~n~, in ra ~-1~.

Constraints

• ~1 \le n,m \le 2*10^5~.
• ~1 \le l_i,c_i \le 10^9~.

Subtasks

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

Sample Input 1:

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

Sample Output 1:

6 7

Explanation 1:

Có hai lộ trình có độ dài ~6~ có thể đi là ~(1,2,5)~ và ~(1,3,4,5)~. Trong đó lộ trình ~(1,3,4,5)~ có độ đẹp lớn nhất là bằng ~7~.

Sample Input 2:

4 2
1 2 1 1
1 3 1 1

Sample Output 2:

-1

Explanation 2:

Không có lộ trình nào để đi từ ~1~ tới ~4~.

Ở một đất nước nọ, có ~n~ thành phố. Giữa hai thành phố bất kì đều có một con đường với nhau, mỗi con đường sẽ có một độ dài ~w~ và chi phí vận hành ~c~.

Độ tốt của mạng lưới này được tính bằng ~\sum f(u,v)~ với ~f(u,v)~ là đường đi ngắn nhất giữa thành phố ~u~ và thành phố ~v~. ~(f(u,v) = 0)~

Chính phủ đang muốn giảm ngân sách phục vụ cho vận hành giao thông, nên sẽ chọn ra một giá trị ~X~ và ngừng hoạt động toàn bộ các con đường có chi phí vận hành nhỏ hơn ~X~ (lưu ý thao tác xóa này không áp dụng cho các con đường nối chính thành phố ~u~ tới ~u~). Tuy nhiên, hệ thông giao thông vẫn cần đủ tốt, vậy nên sau khi cắt giảm phải thỏa mãn rằng ~2~ thành phố bất kì đều đi đến dược với nhau và độ tốt của mạng lưới mới phải bé hơn hoặc bằng ~T~.

Hãy giúp chính phủ tính toán ra được con số ~X~ lớn nhất thỏa mãn.

Input

• Dòng đầu chứa ~2~ số nguyên dương ~n,T~.
• ~n~ dòng sau, mỗi dòng gồm ~n~ số miêu tả ma trận ~w~. Giá trị thứ ~j~ trên dòng thứ ~i~ là ~w_{i,j}~, độ dài của con đường nối thành phố ~i~ tới ~j~. ~(w(i,i) = 0)~

• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số miêu tả ma trận ~c~. Giá trị thứ ~j~ trên dòng thứ ~i~ là ~c_{i,j}~, chi phí vận hành của con đường nối thành phố ~i~ tới ~j~. ~(c(i,i) = 0)~

  Output

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

Constraints

• ~1 \le n \le 300~
• ~1 \le T \le 10^{15}~
• ~1 \le w_{i,j}, c_{i,j} \le 10^5~

Subtask

• Subtask ~1~ (~50\%~ số điểm): ~c_{i,j} \le 50~
• Subtask ~2~ (~50\%~ số điểm): không ràng buộc gì thêm

Sample Input 1:

3 25

0 2 2
2 0 1
3 1 0

0 2 3
5 0 6
0 7 0

Sample Output 1:

3

Một hệ thống giao thông gồm ~n~ thành phố được đánh số từ ~1~ tới ~n~. Hệ thống giao thông có ~m~ đoạn đường hai chiều nối giữa các thành phố (giữa hai thành phố bất kì luôn có đường đi). Mỗi đoạn đường có tải trọng tối đa là ~w~, nghĩa là các xe có tải trọng không lớn hơn ~w~ mới lưu thông được trên con đường đó.

Cho ~q~ truy vấn, mỗi truy vấn có dạng ~(u,v)~, hãy tìm một lộ trình từ thành phố ~u~ tới thành phố ~v~ sao cho tải trọng cho phép lưu thông trên hành trình đó là lớn nhất có thể.

Input

• Dòng đầu chứa ~3~ số nguyên dương ~n,m,q~.
• ~m~ dòng sau, mỗi dòng gồm ~3~ số nguyên dương ~u,v,w~ miêu tả con đường nối thành phố ~u~ với ~v~.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~u,v~ miêu tả truy vấn. ~(u \neq v)~.

Output

• In ra ~q~ dòng tương ứng ~q~ truy vấn là tải trọng tối đa cho phép lưu thông trên hành trình từ ~u~ tới ~v~.

Constraints

• ~1 \le n,q \le 500~
• ~1 \le m \le 10000~
• ~0 \le w \le 10^9~

Subtask

• Subtask ~1~ (~50\%~ số điểm): ~n \le 50~
• Subtask ~2~ (~50\%~ số điểm): không ràng buộc gì thêm

Sample Input 1:

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

Sample Output 1:

3

Cho bảng số ~A~ kích thước ~n*m~, các hàng được đánh số từ trên xuống dưới, các cột được đánh số từ trái sang phải. Ô giao giữa hàng ~i~ cột ~j~ là ô ~(i,j)~ và có giá trị ~a(i,j)~. Hai ô có thể di chuyển tới nhau nếu chúng chung cạnh. Một đường đi sẽ bao gồm các ô sao cho hai ô liên tiếp chung cạnh, và nó có giá trị bằng tổng giá trị các ô trên đường đi.

Cho ~q~ truy vấn, truy vấn thứ ~i~ sẽ cho bạn hai ô ~(x,y)~ và ~(u,v)~ trong bảng. Kết quả của một truy vấn chính là giá trị của đường đi có trọng số nhỏ nhất giữa hai ô đã cho. Hãy in ra kết quả của từng truy vấn.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~, ~(1 \le n \le 7; 1 \le m \le 5000)~.
• Tiếp theo là ~n~ dòng, mỗi dòng gồm ~m~ số nguyên không âm miêu tả bảng ~A~ ~n*m~, ~(0 \le a(i,j) \le 10^5)~ .
• Dòng tiếp theo là số nguyên dương ~q~, ~(q \le 30000)~.
• Ở ~q~ dòng tiếp theo mỗi dòng miêu tả một truy vấn, truy vấn thứ ~i~ có dạng ~x_i, y_i, u_i, v_i~ miêu tả ô ~(x_i,y_i)~ và ~(u_i,v_i)~. (Các ô đều nằm trong bảng).

Output

• In ra ~q~ dòng là kết quả của ~q~ truy vấn.

Sample Test

Input:

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

Output:

5
9

Sau khi Kawashiro xây xong hệ thống cáp treo, cô lại phải tiếp tục xây dựng một số cáp treo nữa để tất cả địa điểm từ 1 đến ~n~ đều có thể đến đền Moriya nằm ở vị trí ~T~.

Input

• Dòng đầu gồm 3 số tự nhiên ~n, m, T \le 100000~.
• ~m~ dòng tiếp theo gồm 2 số ~u, v~ nghĩa là địa điểm ~u, v~ dã được nối bằng cáp treo một chiều.

Output

• Số lượng tối thiểu cáp treo cô cần xây thêm để mọi địa điểm từ 1 đến ~n~ đều đến được đền Moriya ở ~T~.

Sample Test

Input:

6 4 5
1 3
2 3
4 5
6 5

Output:

1

Cho đồ thị đầy đủ vô hướng có trọng số (nghĩa là đồ thị gồm ~\frac{n*(n-1)}{2}~ cạnh phân biệt), trong đó có ~m~ cạnh có trọng số là ~1~, các cạnh còn lại có trọng số là ~0~.

Hãy tìm cây khung nhỏ nhất của đồ thị này.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le min(4*10^5,\frac{n*(n-1)}{2}))~
• ~m~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên ~u_i,v_i~ ~(1 \le u_i, v_i \le n, u_i \neq v_i)~ - miêu tả cạnh ~(u_i,v_i)~ có trọng số là ~1~.

Output:

• Trọng số của cây khung nhỏ nhất của đồ thị.

Constraints:

• Có ~50\%~ số test ứng với ~n \le 2*10^3~
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input 1

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

Output 1

2

Input 2

3 0

Output 2

0

Cho một cây vô hướng ~n~ đỉnh với gốc là ~1~, mỗi đỉnh ~u~ có một giá trị là ~c[u]~. Cho ~q~ truy vấn có dạng như sau:

• Truy vấn có dạng "~1~ ~v~". Với truy vấn này, tạm gọi dãy ~u_1, u_2, ..., u_k~ là dãy đỉnh trong đường đi ngắn nhất từ đỉnh ~1~ tới đỉnh ~v~, (~u_k = v~). Bạn cần tìm một đỉnh ~u_i~ nào đó thỏa mãn ~gcd(c[u_i], c[v]) > 1~ với ~1 \le i < k~. Nếu có nhiều giá trị ~u_i~ thỏa mãn, hãy chọn đỉnh có ~i~ lớn nhất, ngược lại, in ra ~-1~ nếu không có đỉnh nào như vậy.
• Truy vấn có dạng "~2~ ~v~ ~w~". Với truy vấn này, bạn hãy đổi giá trị ~c[v] = w~. Có tối đa ~50~ truy vấn dạng này.

Hãy giải quyết bài toán trên.

Input

• Dòng đầu gồm ~2~ số nguyên dương ~n~ và ~q~ ~(1 \le n,q \le 10^5)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_1, c_2, ..., c_n~. ~(c_i \le 2*10^6)~
• ~n-1~ dòng tiếp theo, mỗi dòng gồm ~2~ số nguyên dương ~u v~ miêu tả cạnh nối giữa hai đỉnh này.
• ~q~ dòng tiếp theo, mỗi dòng miêu tả một truy vấn. Lưu ý rằng, với mọi truy vấn, ~v \le n~, ~w \le 2*10^6~

Output

• In ra kết quả của các truy vấn dạng ~1~ thành từng dòng.

Sample Test

Input

4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4

Output

-1
1
2
-1
1

Ở một đất nước nọ, có ~n~ thành phố được kết nối với nhau bằng ~n-1~ con đường 2 chiều, đảm bảo rằng từ một thành phố bất kì có thể tới được tất cả các thành phố khác.

Thành phố thứ ~i~ có một giá trị ~a_i~, là độ "đẹp của thành phố đó. Các giá trị a_i này có thể giống nhau, tức là các thành phố có thể có độ đẹp ngang nhau.

Một vị khách du lịch khi tới đất nước này chơi trong ~k (1 \le k \le 10^{18})~ ngày. Hiện tại, vị khách ấy đang ở thành phố 1. Cách di chuyển của vị khách này rất đặc biệt, ví dụ ở ngày thứ i và vị khách đang ở thành phố ~u~ (ở ngày đầu thì anh ta ở thành phố 1), anh sẽ đi tới thành phố ~v~ khác ~u~, sao cho ~a_v - dist(u,v)~ là lớn nhất (~dist(u,v)~ là đường đi ngắn nhất từ thành phố ~u~ tới ~v~). Nếu có nhiều thành phố thỏa mãn điều kiện trên, anh ta sẽ đi tới thành phố có chỉ số nhỏ nhất.

Là một người yêu thích tin học, vị khách đưa ra một yêu cầu trước khi tham quan, đó là hãy tính xem, sau ~k~ ngày, anh ta sẽ ở thành phố nào. Hãy lập trình và giải bài toán này giúp anh ấy.

Input

• Dòng đầu gồm 2 số ~n~ và ~k~, lần lượt là số thành phố và số ngày vị khách ở ~(1 \le n \le 3 \times 10^5, 1 \le k \le 10^{18})~.
• Dòng sau gồm ~n~ số miêu tả dãy ~a~. ~(0 \le a_i \le 10^9 \; \forall \; 1 \le i \le n).~
• ~n-1~ dòng sau, mỗi dòng gồm 2 số ~u,v (1 \le u,v \le n)~ miêu tả con đường 2 chiều nối ~u~ và ~v~.

Output

In ra thành phố mà anh ta sẽ đến sau ~k~ ngày.

Ràng buộc

• Subtask 1: ~n \le 1000, k \le 10^5~ (20%)
• Subtask 2: ~n \le 1000, k \le 10^{18}~ (15%)
• Subtask 3: ~n \le 300000, k \le 10^5~ (50%)
• Subtask 4: ~n \le 300000, k \le 10^{18}~ (15%)

Sample Test

Input:

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

Output:

5

Giải thích:

• Vị khách sẽ đi theo thứ tự 1 --> 3 --> 5 --> 2 --> 5

Cho một đồ thị vô hướng có ~n~ đỉnh, đỉnh thứ ~i~ có màu ~a_i~. Ban đầu đồ thị chưa có cạnh nào.

Cho ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng sau:

• ~1~ ~u~ ~v~: Thêm một cạnh nối ~u~ và ~v~.
• ~2~ ~u~ ~c~: Tính số đỉnh có màu ~c~ trong vùng liên thông của ~u~.

Input:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~ ~(n \le 10^5, q \le 2*10^5)~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1,a_2,...,a_n~. ~(a_i \le n)~.
• ~q~ dòng cuối cùng, mỗi dòng gồm ba số nguyên dương, số nguyên đầu tiên là loại của truy vấn (~1~ hoặc ~2~), hai số nguyên dương còn lại không vượt quá ~n~.

Output

• Với mỗi truy vấn loại ~2~, in ra trên một dòng kết quả của truy vấn đó.

Subtask

• Có ~30\%~ số test chứa ~n,q \le 5000~.
• ~70\%~ số test còn lại không có ràng buộc gì thêm.

Sample Input 1

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

Sample Output 1

1
0
3
1

Cho một cây vô hướng gồm ~n~ đỉnh và số nguyên dương ~k~.

Đếm các cặp đỉnh ~(u,v)~ ~(u > v)~ sao cho khoảng cách của chúng trên cây bằng ~k~.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le k \le n \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~u_i,v_i~ ~(1 \le u_i,v_i \le n u_i \neq v_i;)~.

Output

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~k \le 50, n \le 1000~.
• Có ~25\%~ số test thỏa mãn: ~k \le 500, n \le 5 \times 10^4~.
• Có ~25\%~ số test thỏa mãn: ~n \le 10^5~.
• Có ~25\%~ số test thỏa mãn: ~n \le 10^6~.

Ví dụ

Input

5 2
1 2
2 3
3 4
2 5

Output

4

Cho một đồ thị liên thông vô hướng gồm ~n~ đỉnh, ~n - 1~ cạnh (đây còn được gọi là đồ thị dạng cây). Cạnh thứ ~i~ nối giữa đỉnh ~u_i~ với ~v_i~ và có trọng số là ~w_i~. Quân đưa cho bạn ~m~ tập đỉnh, tập thứ ~i~ gồm ~t_i~ đỉnh là ~a_{i_1}, a_{i_2}, . . . , a_{i_{t_i}}~.

Giả sử ta có hai tập đỉnh ~p~ và ~q~ (một tập không có hai đỉnh giống nhau, nhưng một đỉnh có thể xuất hiện ở cả hai tập).

Đặt ~f(p,q)~ là tổng khoảng cách giữa các cặp đỉnh ~(u, v)~ trong đó ~u~ nằm trong tập ~p~ và ~v~ nằm trong tập ~q~ (khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi giữa chúng).

Cụ thể, nếu gọi ~dist(u,v)~ là khoảng cách giữa cặp đỉnh ~(u,v)~ trên cây, ta có tập ~p~ ~=~ ~ \{2,3\}~ và tập ~q~ ~=~ ~\{1,4,3\}~, thì ~f(p,q)~ sẽ được tính như sau:

• ~f(p,q) = dist(2,1) + dist(2,4) + dist(2,3) + dist (3,1) + dist(3,4) + dist(3,3)~.

Quân muốn bạn tính giá trị của biểu thức sau: ~S = \sum_{i=1}^m \sum_{j=i+1}^m f(i,j)~.

Vì kết quả có thể rất lớn, hãy in ra phần dư của ~S~ khi chia cho ~10^9 + 7~.

Dữ liệu vào từ tệp văn bản: tongcay.inp

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~m~ ~(1 \le n,m \le 10^6)~.
• ~n-1~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên dương ~u_i,v_i,w_i~ ~(1 \le u_i,v_i \le n; u_i \neq v_i; w_i \le 10^5)~.
• Ở mỗi dòng trong ~m~ dòng cuối cùng, số đầu tiên là ~t_i~, theo sau đó là ~t_i~ số ~a_{i_1},a_{i_2},...,a_{t_i}~ ~(1 \le a_x \le n; a_x \neq a_y \forall x \neq y)~.

Tổng ~t_1 + t_2 + ... + t_m~ không vượt quá ~10^6~.

Kết quả ghi ra tệp văn bản: tongcay.out

• In ra một số nguyên không âm là kết quả bài toán.

Ràng buộc

• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 100~.
• Có ~25\%~ số test thỏa mãn: ~n \le 100; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n \le 10^5; m \le 100; t_1 + t_2 + ... + t_m \le 10^5~.
• Có ~20\%~ số test thỏa mãn: ~n, m, t_1 + t_2 + ... + t_m \le 10^5~.
• ~10\%~ số test còn lại không có ràng buộc gì thêm.

Ví dụ

Input

3 3
1 2 1
2 3 1
1 1
1 2
2 1 3

Output

5

Giải thích

~f(1,2) = dist(1,2) = 1~ ~f(1,3) = dist(1,1) + dist(1,3) = 0 + 2 =2~ ~f(2,3) = dist(2,1) + dist(2,3) = 1 + 1 = 2~

Vậy ~S = 1 + 2 + 2 = 5~