Cho một dãy số nguyên dương gồm n phần tử ~a_1, a_2, \ldots, a_n~. Trọng số ~W~ của dãy ~a~ được định nghĩa là ước chung lớn nhất của tất cả các phần tử trong dãy, tức là ~W = \gcd(a_1, a_2, \ldots, a_n)~.

Ở đây, ~gcd~ được định nghĩa là phép lấy ước chung lớn nhất.

Bạn được phép thay đổi tối đa hai phần tử bất kỳ trong dãy ~a~ thành hai số nguyên dương khác sao cho trọng số mới của dãy đạt giá trị lớn nhất có thể.

Nhiệm vụ của bạn là tìm giá trị lớn nhất có thể của trọng số mới.

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

• Dòng đầu tiên gồm số nguyên dương ~n~ (~3 \le n \le 2 \cdot 10^5~).
• Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ (~1 \le a_i \le 10^9~).

Kết quả ghi ra tệp văn bản: THAYDOISO.OUT

• Gồm số nguyên dương duy nhất là giá trị lớn nhất có thể của trọng số mới sau khi thay đổi tối đa hai phần tử trong dãy ~a~.

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~N = 3~.
• Subtask ~2~ (~30\%~ số điểm): ~N, a_i \le 1000~.
• Subtask ~3~ (~30\%~ số điểm): ~N, a_i \le 10^5~.
• Subtask ~4~ (~10\%~ số điểm): Không có ràng buộc gì thêm.

Example

Sample Input 1

3
4 4 12

Sample Output 1

12

Sample Input 2

5
6 1 9 2 12

Sample Output 2

3

Explanation

Ở ví dụ thứ nhất, ta thay hai phần tử ~a_1~ và ~a_2~ thành giá trị ~12~.

Ở ví dụ thứ hai, ta thay hai phần tử ~a_2~ và ~a_4~ thành giá trị ~3~.

Cho một mảng ~a~ gồm ~n~ số nguyên.

Có ~q~ truy vấn. Mỗi truy vấn gồm ba số nguyên ~l, r, x~. Với mỗi truy vấn, ta thay tất cả phần tử ~a_i~ có giá trị nằm trong đoạn ~[l, r]~ thành ~x~.

Đầu tiên, bạn cần in ra tổng của dãy ~a~ ban đầu.

Sau mỗi truy vấn, hãy in ra tổng các phần tử trong mảng sau khi thực hiện thay đổi.

Yêu cầu

Cho mảng ~a~ và ~q~ truy vấn.

Với mỗi truy vấn ~l, r, x~, cập nhật mọi phần tử ~a_i~ thỏa mãn: ~l \le a_i \le r~ thành: ~a_i = x~

Hãy in ra tổng ban đầu của mảng và tổng của mảng sau mỗi truy vấn.

Input

• Dòng đầu tiên gồm hai số nguyên ~n, q~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~.
• ~q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~l, r, x~.

Output

In ra ~q + 1~ dòng.

• Dòng đầu tiên là tổng ban đầu của mảng.
• Dòng thứ ~i + 1~ là tổng của mảng sau truy vấn thứ ~i~.

Ràng buộc

• ~1 \le n \le 200000~
• ~0 \le q \le 200000~
• ~0 \le a_i \le 10^9~
• ~0 \le x \le 10^9~
• ~0 \le l \le r \le 10^9~

Scoring

Sample Input 1

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

Sample Output 1

31
27
46
0
0

Giải thích

Ban đầu mảng là:

• ~[2, 5, 5, 8, 10, 1]~

• Tổng ban đầu là ~31~.

Sau truy vấn 1, các phần tử có giá trị trong đoạn ~[5, 5]~ được đổi thành ~3~.

Mảng trở thành:

• ~[2, 3, 3, 8, 10, 1]~

• Tổng là ~27~.

Sau truy vấn 2, các phần tử có giá trị trong đoạn ~[1, 3]~ được đổi thành ~7~.

Mảng trở thành:

• ~[7, 7, 7, 8, 10, 7]~

• Tổng là ~46~.

Sau truy vấn 3, các phần tử có giá trị trong đoạn ~[7, 10]~ được đổi thành ~0~.

Mảng trở thành:

• ~[0, 0, 0, 0, 0, 0]~

• Tổng là ~0~.

Sau truy vấn 4, không có phần tử nào có giá trị trong đoạn ~[4, 6]~, nên mảng không đổi.

• Tổng vẫn là ~0~.

Sample Input 2

5 3
100 200 300 400 500
150 350 50
50 100 10
10 500 1

Sample Output 2

1500
1100
930
5

Giải thích

Ban đầu mảng là:

• ~[100, 200, 300, 400, 500]~

• Tổng ban đầu là ~1500~.

Sau truy vấn 1, các phần tử có giá trị trong đoạn ~[150, 350]~ được đổi thành ~50~.

Mảng trở thành:

• ~[100, 50, 50, 400, 500]~

• Tổng là ~1100~.

Sau truy vấn 2, các phần tử có giá trị trong đoạn ~[50, 100]~ được đổi thành ~10~.

Mảng trở thành:

• ~[10, 10, 10, 400, 500]~

• Tổng là ~930~.

Sau truy vấn 3, các phần tử có giá trị trong đoạn ~[10, 500]~ được đổi thành ~1~.

Mảng trở thành:

• ~[1, 1, 1, 1, 1]~

• Tổng là ~5~.

Cho một đa giác lồi có ~n~ đỉnh, các đỉnh được đánh số từ ~1~ đến ~n~. Người ta chia đa giác này thành ~m+1~ đa giác con bằng ~m~ đường chéo (~m \le n-3~). Các đường chéo này cùng với ~n~ cạnh của đa giác đôi một không trùng nhau hay cắt nhau (chỉ có điểm chung tại các đầu mút). Một đa giác con gồm các đỉnh lần lượt ~x_1,x_2,...,x_t~ được coi là có giá trị ~\Sigma_{i=1}^t 2^{x_i}~.

Cho đa giác, ~m~ đường chéo và số nguyên dương ~k~ (~k \le m+1~), sắp xếp các đa giác con theo giá trị tăng dần, hãy xác định đa giác con thứ ~k~.

Input

• Dòng đầu gồm ba số nguyên ~n,m,k~ (~3 \le n \le 5 \times 10^5, 0 \le m \le n-3, 1 \le k \le m+1~).
• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u,v~ (~1 \le u,v \le n~) thể hiện một đường chéo trong đa giác.

Output

• Một dòng chứa các đỉnh của đa giác con thứ ~k~ (các đỉnh được ghi theo thứ tự tăng dần).

Scoring

• Subtask ~1~ (~25\%~ số điểm): ~n \le 50, m \le 20~.
• Subtask ~2~ (~25\%~ số điểm): ~m = 1~.
• Subtask ~3~ (~25\%~ số điểm): ~m = n-3~.
• Subtask ~4~ (~25\%~ số điểm): không có ràng buộc gì thêm.

Example

Sample Input

6 3 2
1 3
1 4
1 5

Sample Output

1 3 4

An đang chơi một trò chơi điện tử gồm ~n~ nhiệm vụ được đánh số từ ~1~ đến ~n~. Nhiệm vụ thứ ~i~ làm thay đổi năng lượng của người chơi thêm ~a_i~ đơn vị. Giá trị ~a_i~ có thể dương, bằng ~0~ hoặc âm.

An có thể chọn làm một số nhiệm vụ theo đúng thứ tự ban đầu, không nhất thiết phải làm các nhiệm vụ liên tiếp. An chỉ được làm một nhiệm vụ nếu sau khi hoàn thành nhiệm vụ đó, năng lượng của An không bị âm.

Có ~q~ kịch bản. Ở kịch bản thứ ~j~, An có năng lượng ban đầu là ~s_j~.

Yêu cầu

Với mỗi kịch bản, hãy tính số nhiệm vụ nhiều nhất mà An có thể hoàn thành.

Input

• Dòng đầu tiên chứa hai số nguyên ~n, q~ ~(1 \le n \le 2000, 1 \le q \le 2 \times 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(|a_i| \le 10^9)~.
• Dòng thứ ba chứa ~q~ số nguyên ~s_1, s_2, \ldots, s_q~ ~(0 \le s_j \le 10^9)~.

Output

In ra ~q~ số nguyên trên một dòng, số thứ ~j~ là số nhiệm vụ tối đa An có thể hoàn thành trong kịch bản thứ ~j~.

Subtask

Sample Input

7 3
-13 0 1 -14 -9 -5 4
20 12 2026

Sample Output

5 4 7

Giải thích ví dụ

Với năng lượng ban đầu ~s = 12~, An có thể làm các nhiệm vụ ~2, 3, 6, 7~.

Năng lượng sau mỗi nhiệm vụ lần lượt là:

• Sau nhiệm vụ ~2~: ~12 + 0 = 12~
• Sau nhiệm vụ ~3~: ~12 + 1 = 13~
• Sau nhiệm vụ ~6~: ~13 + (-9) = 4~
• Sau nhiệm vụ ~7~: ~4 + 4 = 8~

Vậy với ~s = 12~, An hoàn thành được tối đa ~4~ nhiệm vụ.

Cho một đồ thị vô hướng gồm ~n~ đỉnh ~m~ cạnh. Cạnh ~i~ nối giữa đỉnh ~u_i~ và ~v_i~ và có kí tự ~c_i~ được viết lên trên nó.

Hãy tìm một đường đi từ ~1~ đến ~n~ ngắn nhất mà sau khi viết các kí tự có được khi đi qua các cạnh là một xâu palindrome. Nếu không tồn tại bất kì đường đi nào thỏa mãn là palindrome, in ra ~-1~.

Lưu ý: Đồ thị có thể tồn tại khuyên và cạnh lặp, các đỉnh và cạnh có thể đi qua lại nhiều lần.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n, m~ ~(1 \le n, m \le 1000)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~u_i, v_i, c_i~ mô tả cạnh thứ ~i~ của đồ thị.

Output

• Nếu tồn tại một đường đi tạo ra xâu palindrome, in ra độ dài ngắn nhất có thể. Nếu không, in ra ~-1~.

Sample Input 1

4 5
1 1 a
1 2 a
2 3 a
3 4 b
4 4 a

Sample Output 1

5

Explanation 1

Đi qua các cạnh ~2, 3, 4, 5, 5~, ta nhận được xâu aabaa.

Sample Input 2

3 4
1 1 a
1 2 a
2 3 b
3 3 b

Sample Output 2

-1

Cho dãy số gồm ~n~ số nguyên ~a_1, a_2, …, a_n~ và ~2~ số nguyên không âm ~L, R (L ≤ R)~.

Yêu cầu: Đếm số cặp ~(i, j)~ thỏa mãn điều kiện: ~i ≤ j~ và ~L ≤ |a_i+…+a_j| ≤ R~.

Input

• Dòng đầu tiên chứa ~3~ số nguyên ~n, L, R~ ~(n ≤ 3*10^5 ; 0 ≤ L ≤ R ≤ 10^9)~
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2,…, a_n (|a_i|≤ 10^9)~

Output

• Một số nguyên duy nhất là số lượng cặp ~(i, j)~ đếm được.

Subtask

• Subtask 1 (~30\%~ số điểm): ~n \le 10^3~.
• Subtask 2 (~50\%~ số điểm): ~n \le 10^5~ và ~a_i \ge 0~.
• Subtask 3 (~20\%~ số điểm): Không có giới hạn gì thêm.

Sample Test

Input

3 0 1
1 -1 2

Output

4

Cho dãy số nguyên dương ~a_1,a_2,...,a_n~ và một số ~k~.

Một tập con ~S~ của ~\{1,2,...,n\}~ được gọi là tập ~xor~ nếu ~S~ không có quá ~k~ phần tử và với mọi ~i,j~ thuộc ~S~ ta có ~a_i + a_j = a_i \oplus a_j~, với ~\oplus~ là phép ~xor~.

Trọng số của ~S~ được hiểu là ~\sum a_i, \forall i \in S~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai chứa số nguyên dương ~k~.
• Nếu ~n \le 10^4~ thì có dòng thứ ba, ngược lại không có.

Output

• Ghi ra tổng trọng số tất cả các tập ~xor~, sau khi lấy dư cho ~10^9+7~.

Subtask

• Sub ~1~ ~(20\%)~: ~1 \le n,k,a_i \le 10^2~
• Sub ~2~ ~(20\%)~: ~1 \le n,k,a_i \le 10^3~.
• Sub ~3~ ~(20\%)~: ~1 \le n,k \le 10^4~ và ~a_i = i~.
• Sub ~4~ ~(20\%)~: ~1 \le n,k,a_i \le 10^4~.
• Sub ~5~ ~(20\%)~: ~1 \le n,k \le 10^{1000}~ và ~a_i = i~.

Sample Input 1

6 
3
1 1 2 3 4 5

Sample Output 1

66