Mỗi lần bị kẹt trên đường vì tắc đường, An thường nghĩ ra trò chơi để giải trí. Một trong những trò chơi đó là An đọc ~N~ số từ các biển số xe và tìm số nguyên ~M~ ~(M>1)~ sao cho N số đã đọc đều có cùng số dư khi chia cho ~M~. An muốn tìm được càng nhiều số ~M~ như thế càng tốt. Bạn hãy giúp An tìm tất cả các số ~M~ thoả mãn yêu cầu.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(2< N <100)~. ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~B_i~ thuộc đoạn ~[1; 10^9]~. Tất cả các số nguyên đôi một khác nhau. Dữ liệu vào luôn đảm bảo tồn tại ít nhất một số ~M~ thoả mãn yêu cầu.

Output

• In ra tất cả các số ~M~ tìm được theo thứ tự tăng dần, các số ghi cách nhau ít nhất một dấu cách.

Subtask

• Có ~60\%~ số test tương ứng với ~0 < B_i \le 10^4~ ~(\forall i \in [1,N])~
• ~40\%~ số test còn lại không giới hạn gì thêm.

Sample Input 1

3
6
34
38

Sample Output 1

2  4

Sample Input 2

5
5
17
23
14
83

Sample Output 2

3

Cho số ~n~. Hãy tìm số ~k \le n~ lớn nhất sao cho ~k~ là tích của 3 số nguyên tố liên tiếp.

Input

• Gồm số tự nhiên ~n \le 10^{18}~.

Output

• Gồm duy nhất một số tự nhiên ~k~. Nếu không có số thỏa mãn in ra -1.

Sample Test

Input:

31

Output

30

Cho số ~n~ và dãy số nguyên ~a~ gồm ~n~ phần tử, hãy tìm đoạn con liên tiếp dài nhất của dãy ~a~ có trung bình cộng lớn hơn hoặc bằng ~k~ cho trước.

Input

• Dòng đầu gồm 2 số nguyên ~n~ ~(1 \le n \le 10^5)~ và ~k~ ~(|k| \le 10^6)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra một số nguyên là độ dài của dãy con liên tiếp dài nhất thỏa mãn.

Sample Test

Input

7 3
1 5 2 3 1 4 1

Output

5

Cho một dãy ~a~ gồm ~n~ phần tử nguyên dương và một số nguyên dương ~k~.

Ta có định nghĩa như sau:

• ~MaxSecond(l,r) :~ phần tử lớn thứ hai trong đoạn ~[l,r]~ của dãy ~a~.
• ~MinSecond(l,r) :~ phần tử nhỏ thứ hai trong đoạn ~[l,r]~ của dãy ~a~.
• ~f(l,r) = MaxSecond(l,r) - MinSecond(l,r)~

Hãy tìm một đoạn con ~[l,r]~ dài nhất sao cho ~f(l,r) \le k~.

Input

• Dòng thứ nhất chứa ~2~ số nguyên dương: ~n,k~.
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~a~.

Output

• In ra số ~X~ là độ dài của đoạn con dài nhất thỏa mãn. Dữ liệu đảm bảo luôn tồn tại kết quả.

Constraints

• ~1 \le n \le 10^5~.
• ~1 \le a_i \le 10^9~.
• ~1 \le k \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:

5 2
1 4 2 6 5

Sample Output 1:

4

Explanation 1:

Chọn đoạn ~[1,4]~.

Sample Input 2:

7 3
9 1 4 3 12 16 8

Sample Output 2:

4

Explanation 2:

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

Người ta đo độ giống nhau của hai xâu ~X~, ~Y~ có độ dài bằng nhau là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là số chỉ số ~i~ thỏa mãn ~X_i = Y_i~. Ví dụ: ~X = 'avbc'~; ~Y = 'avvv'~ có độ giống nhau bằng ~2~. Cho một xâu ~S~ có độ dài ~n~ và một xâu ~T~ có độ dài ~m (m \le n)~, độ giống nhau giữa xâu ~S~ và xâu ~T~ là tổng số độ giống nhau giữa xâu ~T~ và mọi xâu con gồm các kí tự liên tiếp của ~S~ có độ dài ~m~.

Yêu cầu: Cho hai xâu ~S~ và ~T~. Tính độ giống nhau giữa xâu ~S~ và xâu ~T~.

Input

• Dòng đầu ghi xâu ~T~.
• Dòng thứ ~2~ ghi xâu ~S~.
• Các kí tự trong hai xâu thuộc ~'a' .. 'z'~ và có độ dài không quá ~2.10^6~ kí tự.

Output

• Gồm một số nguyên duy nhất là độ giống nhau giữa xâu ~S~ và xâu ~T~.

Subtask

• Có ~25\%~ số test ứng với ~0 < n ≤ 10^2~
• Có ~25\%~ số test ứng với ~10^2 < n ≤ 10^4~
• Có ~50\%~ số test ứng với ~10^4 < n ≤ 2.10^6~

Sample Input 1

 abaab 
 aababacab

Sample Output 1

12

Cho một dãy ~a~ gồm ~n~ phần tử phân biệt. Ta định nghĩa hàm ~g(l,r)~ như sau:

• ~g(l,r) = Max(l,r) \oplus MaxSecond(l,r)~. Ở đây, ~\oplus~ là toán tử ~xor~.
• Trong đó ~Max(l,r)~ là số lớn nhất trong đoạn ~[l,r]~, ~MaxSecond(l,r)~ là số lớn thứ hai trong đoạn ~[l,r]~.

Hãy tính ~max(g(l,r))~ với mọi đoạn ~[l,r]~ của dãy ~a~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^9~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 1000~.
• ~50\%~ còn lại không có điều kiện gì thêm.

Sample Input 1:

5
5 2 1 4 3

Sample Output 1:

7

Explanation 1:

• Kết quả chính là ~g(4,5) = 4 \oplus 3 = 7~, hoặc ~g(1,2)~.

Sample Input 2:

5
9 8 3 5 7

Sample Output 2:

15

Explanation 2:

• Kết quả là ~g(2,5)~.

Cho dãy ~A~ gồm ~n~ số nguyên dương ~a_1,a_2,...,a_n~.

Yêu cầu: Tìm số nguyên dương ~m~ nhỏ nhất không có mặt trong dãy ~A~.

Input

• Dòng đầu gồm số nguyên dương ~n~, ~n \le 10^5~.

• Dòng tiếp theo gồm ~n~ số nguyên dương không vượt quá ~10^9~.

  Output

• Số ~m~ tìm được.

Sample Input 1

5
6 1 3 2 4

Sample Output 1

5

Explanation 1

• Số nguyên dương nhỏ nhất không có mặt trong dãy là ~5~.

Với hai số nguyên dương ~u,v~, khi viết số ~v~ sau số ~u~ ta được một số mới.

Ví dụ: ~u = 99, v = 123~, khi viết số ~v~ sau ~u~ ta thu được số mới là số ~99123~.

Cho ~n~ số nguyên dương ~a_1, a_2, a_3, ... a_n~ và ~m~ số nguyên dương ~b_1, b_2, b_3, ..., b_m~.

Yêu cầu:

• Với mỗi giá trị ~b_i~ ~(1 \le i \le m)~, bạn hãy cho biết có bao nhiêu số ~a_j~ (~1 \le j \le n~) sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,m~. (~1 \le n,m \le 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương miêu tả dãy ~a~. (~a_i \le 10^8, 1 \le i \le n~).
• Dòng tiếp theo chứa ~m~ số nguyên dương miêu tả dãy ~b~. (~b_i \le 10^8, 1 \le i \le m~).

Output

• Gồm ~m~ dòng, dòng thứ ~i~ ghi số lượng số ~a_j (1 \le j \le n)~ sao cho sau khi viết ~a_j~ sau ~b_i~ ta được một số mới chia hết cho ~3~.

Subtask

• Subtask ~1~ (~60\%~ số điểm): ~n,m \le 1000~
• Subtask ~2~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

5  2
123  4  5  7  10
3  2

Sample Output 1

1
3

Explanation 1

~b_1 = 3~ chỉ có duy nhất một số ~a_1~ thỏa mãn. ~b_2 = 2~, có ba số ~a_2,a_4,a_5~ thỏa mãn.

Bé Tommy rất thích tìm hiểu về các số đặc biệt, hôm trước trong giờ học lập trình thầy giáo dạy cho bé về số hoàn hảo (số hoàn hảo là số có tổng các ước (không kể nó) bằng chính nó, ví dụ số ~6~ là số hoàn hảo vì ~6=1+2+3~), bé cảm thấy hứng thú với con số này. Về nhà bé nghĩ ra khá nhiều bài toán xử lí số hoàn hảo. Nhưng hôm nay, thầy cho bé một bài tập rất hóc búa, nghĩ mãi không ra cách làm tốt nhất để được tối đa điểm của bài, nên bé nhờ các bạn học sinh giỏi làm giúp. Bài toán như sau:

Cho dãy ~a_1,a_2,…,a_n~ , ban đầu tất cả các phần tử có giá trị bằng ~0~. Có ~m~ phép biến đổi dạng ~(u,v,k)~: tăng giá trị các phần tử từ vị trí ~u~ đến vị trí ~v~ lên ~k~ đơn vị. Dữ liệu đảm bảo sau ~m~ phép biến đổi ~0<a_i \le 10^6~ ~(\forall i=1..n)~ và có ít nhất một số hoàn hảo trong dãy. </p>

Yêu cầu:

• Với dãy ~a_1,a_2,…,a_n~ sau ~m~ phép biến đổi, thầy yêu cầu đưa ra vị trí các số hoàn hảo theo thứ tự tăng dần.

Input

• Dòng đầu là hai số nguyên dương ~n,m~ tương ứng là số phần tử của dãy và số lượng phép biến đổi;
• ~m~ dòng sau mỗi dòng là ba số nguyên dương ~u,v,k~ ~(0 < u \le v \le n)~.

Output

• In ra các dòng, mỗi dòng chứa một số nguyên dương là vị trí của số hoàn hảo tìm được trong dãy theo thứ tự tăng dần.

Subtask

• Subtask ~1~ (~35\%~ số điểm): ~ 1 \le n,m \le 10^2~
• Subtask ~2~ (~35\%~ số điểm): ~n \le 10^5, m \le 10^3~
• Subtask ~3~ (~30\%~ số điểm): ~n \le 10^5, m \le 10^5~

Sample Input 1

6 3
1 6 6
2 3 4
3 5 22

Sample Output

1
4
5
6

Explanation 1

• Dãy thu được sau ~3~ phép biến đổi là: 6 10 32 28 28 6

Gọi ~A~ là dãy số với ~A(i)~ được tạo bởi ghép ~i~ số nguyên tố đầu tiên với nhau: ~2, 23, 235, 2357, 235711, 23571113, ... ~.

Cho ~n~ và ~k~, hãy tìm cách xóa ~k~ chữ số ra khỏi số ~A(n)~ để thu được số lớn nhất có thể.

Input

• Gồm một dòng chứa hai số nguyên không âm ~n~ và ~k~ ~(1 \le n \le 50000)~, dữ liệu đảm bảo ~k~ bé hơn số chữ số của ~A(n)~.

  Output

• In ra một dòng miêu tả kết quả của bài toán.

Subtask

• ~50\%~ số test có ~n \le 50~.
• ~50\%~ số test không ràng buộc gì thêm.

Sample Input 1:

7 4

Sample Output 1:

711317

Cho một dãy ~a~ gồm ~n~ phần tử. Ta định nghĩa ~g(l,r) = min (a[i]) \forall (l \le i \le r)~.

Tiếp đó, ta có ~f(k) = max (g(l,r)) \forall (r - l + 1= k)~, hay ~f(k)~ là giá trị lớn nhất của các ~g(l,r)~ với mọi đoạn ~(l,r)~ có độ dài ~k~.

Hãy lập trình tính các ~f(k)~ từ ~1 -> n~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~. ~(1 \le n \le 10^5).~
• Dòng sau gồm n số nguyên dương miêu tả dãy ~a~. ~(1 \le a[i] \le 10^6~ ~\forall (1 \le i \le n))~.

Output

• In ra một dòng gồm ~n~ số miêu tả kết quả của ~f(k)~ từ ~1 -> n~.

Sample Test

Input:

10
1 2 3 4 5 4 3 2 1 6

Output:

6 4 4 3 3 2 2 1 1 1 

Người thầy quốc dân Gojo Satoru giờ đang có một niềm đam mê với tin học. Để lan tỏa điều này, anh muốn đố các học sinh của mình một bài toán như sau: Cho một dãy số nguyên ~a~ gồm ~n~ phần tử, định nghĩa ~f(l,r)~ là ~max(a_i) - min(a_i) \forall (l \le i \le r)~.

Hãy tính tổng của ~f(l,r) \forall (1 \le l \le r \le n)~.

Tất nhiên, do bận đi làm nhiệm vụ, các học sinh của thầy không rảnh để giải bài toán này, hãy thử giải nó giúp họ nhé.

Input:

• Dòng đầu gồm số nguyên dương ~n~. ~(1 \le n \le 10^5)~.
• Dòng sau gồm n số nguyên miêu tả dãy ~a~. ~(|a_i| \le 10^6)~.

Output:

• Ghi ra một số nguyên miêu tả kết quả của bài toán.

Subtasks

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

Sample Test

Input:

3
1 2 3

Output:

4

Giải thích:

Ta có ~f(1,1) + f(1,2) + f(1,3) + f(2,2) + f(2,3) + f(3,3) = 0 + 1 + 2 + 0 + 1 +0 = 4~.

Cho dãy số có quy luật như sau: ~1,2,2,3,3,3,4,4,4,4,5,5,…~ Cho một số tự nhiên ~N~, hãy tìm số thứ ~N~ của dãy số trên (các số được đánh thứ tự từ ~1~).

Input

• Gồm một số nguyên dương ~N~ ~(N ≤ 10^{15})~.

Output

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

Subtasks

• Subtask 1 (~60\%~ số điểm): ~N ≤ 10^{6}~;
• Subtask 2 (~20\%~ số điểm): ~N ≤ 10^{10}~;
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5

Output

3

Cho một xâu ~S~ gồm các kí tự số. Hãy đếm xem có bao nhiêu xâu con chia hết cho ~4~ (xâu con có thể bắt đầu bằng ~0~).

Input:

Xâu ~S~ có độ dài không quá ~10^6~.

Output:

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

Scoring

• Subtask 1 [60%]: Xâu ~S~ có độ dài không quá ~100~.
• Subtask 2 [40%]: Không có ràng buộc gì thêm.

Examples

Input1

08

Output1

3

Giải thích

~0, 8, 08~

Input2

13085

Output2

5

Cho hai số nguyên dương ~n~ và ~k~.

Ta có thể xây dựng một dãy số nguyên dương ~a~ gồm ~n~ phần tử: ~a_1,a_2,...,a_n~ sao cho với mọi ~1 \le i \le n~ thỏa mãn điều kiện ~a_i \in [1,k]~.

Gọi ~g(a)~ là ước chung lớn nhất của dãy số ~a~.

Nhiệm vụ của bạn chính là tính tổng ~g(a)~ của mọi dãy số có thể xây dựng (có ~k^n~ dãy số như vậy).

Vì kết quả có thể rất lớn, hãy in nó ra theo module ~10^9+7~.

Input: nhập vào từ file "SUMGCD.INP"

• Gồm một dòng chứa hai số nguyên dương ~n,k~ ~(1 \le n \le 10^9, 1 \le k \le 10^6)~.

Output: ghi ra file "SUMGCD.OUT"

• In ra kết quả theo module ~10^9+7~.

Subtask

• Subtask ~1~ ~(20\%)~: ~n,k \le 7~
• Subtask ~2~ ~(20\%)~: ~n \le 10^5, k = 4~
• Subtask ~3~ ~(25\%)~: ~n \le 10^5, k \le 20~
• Subtask ~4~ ~(20\%)~: ~k \le 10^5~
• Subtask ~5~ ~(15\%)~: Không giới hạn gì thêm.

Ví dụ

Sample Input 1

1  5

Sample Output 1

15

Sample Input 2

5 4

Sample Output 2

1060

Sample Input 3

3 2

Sample Output 3

9

Giải thích

Ở ví dụ ~3~ ta có:

• ~g([1,1,1]) = 1~
• ~g([1,1,2]) = 1~
• ~g([1,2,1]) = 1~
• ~g([1,2,2]) = 1~
• ~g([2,1,1]) = 1~
• ~g([2,1,2]) = 1~
• ~g([2,2,1]) = 1~
• ~g([2,2,2]) = 2~

Kết quả thu được là ~9~.

Cho dãy ~a~ nguyên dương gồm ~n~ phần tử phân biệt. Hãy đếm có bao nhiêu dãy con tăng chỉ gồm đúng ~k+1~ phần tử. Vì kết quả có thể rất lớn, hãy in ra số cách theo module ~10^9+7~.

Input

• Dòng đầu gồm hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 10^5, 0 \le k \le 10)~.
• Dòng sau gồm ~n~ số nguyên dương miêu tả dãy ~a~ ~(1 \le a_i \le n)~, tất cả các giá trị ~a_i~ đều khác nhau.

Output

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

Subtasks

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

Sample Input 1

5 2
1 2 3 5 4

Sample Output 1

7

Yakumo Ran rất giỏi toán, nhưng với những số rất lớn cô sẽ gặp khó khăn nên cô nhờ các bạn giúp bài toán sau.

Cho hai số nguyên dương ~a,b~, hãy tính: ~\sum_{i=a}^b~ ~⌊\sqrt{i}⌋~.

Ở đây, ~⌊a⌋~ có nghĩa là số nguyên lớn nhất không lớn hơn ~a~.

Input

• Gồm một dòng chứa hai số nguyên dương ~a,b~.

Output

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

Sample Test

Input 1

3 10

Output 1

17

Giải thích

~⌊\sqrt{3}⌋+⌊\sqrt{4}⌋+⌊\sqrt{5}⌋+⌊\sqrt{6}⌋+⌊\sqrt{7}⌋+⌊\sqrt{8}⌋+⌊\sqrt{9}⌋+⌊\sqrt{10}⌋~ ~=1+2+2+2+2+2+3+3=17~

Input 2

14 29

Output 2

67

Giới hạn:

• Subtask 1 (60% số điểm): ~a,b \le 10^6~
• Subtask 2 (40% số điểm): ~a,b \le 10^{12}~

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

Hãy tìm một đường đi từ ~1~ tới ~n~ sao cho chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi là nhỏ nhất có thể.

Input:

• Dòng đầu tiên ghi số nguyên ~n~ và ~m~ ~(1 \le n \le 2*10^5, 1 \le m \le 2*10^5)~
• ~n~ dòng sau, mỗi dòng gồm ~n~ số nguyên dương ~c_i~ là trọng số của đỉnh thứ ~i~ ~(1 \le c_i \le 10^9)~.
• ~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)~.

Output:

• In ra chênh lệch lớn nhất giữa trọng số của hai đỉnh liền kề trên đường đi sao cho nó nhỏ nhất có 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

3 3
1 2 3
1 2
2 3
1 3

Output 1

1

Explanation 1:

Đi đường ~(1,2,3)~ thay vì ~(1,3)~.

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

Mùa tuyển sinh đã đến, là một người đã cố gắng suốt cả năm qua nên AP đang phải đau đầu để chọn trường cho mình. Ting ting tiếng chuông điện thoại của AP kêu lên và AP nhận được một tin nhắn từ Hogwarts báo nhập học, AP đồng ý ngay. Đời không như mơ, để bước vào ngôi trường pháp thuật trứ danh này AP phải qua một bài kiểm tra của thầy hiệu trưởng như sau:

AP được phù phép dịch chuyển đến một mỏm đá, trước mặt AP là những hòn đảo được đánh số từ ~1~ đến ~n~ có diện tích là ~w_i~, giữa những hòn đảo có ~m~ cây cầu được xây sắn bằng phép thuật, cây cầu thứ ~j~ nối hai đảo ~u_i~ và ~v_j~ lại với nhau. Thầy hiệu trưởng muốn qua bài thi này để đánh giá khả năng sử dụng thần chú của AP với đề bài là hai thần chú:

• ~C~ ~i~ ~W~ có tác dụng thay đổi kích thước của hòn đảo thứ ~i~ thành diện tích ~W~
• ~D~ ~j~ có tác dụng xóa đi cầy cầu thứ ~j~ (nếu lúc này nó vẫn tồn tại) nối hai hòn đảo ~u_i~ và ~v_j~.

Sau mỗi thao tác thay đổi như thế, thầy hiệu trưởng muốn biết tổng diện tích lớn nhất của những hòn đảo đến được với nhau. Vốn trí nhớ AP không được tốt và AP cũng khá lười để trả lời những câu hỏi của thầy khi thực hiện một đống phép thuật nên AP cần bạn hơn bao giờ hết. Hãy giúp AP trả lời câu hỏi của thầy hiệu trưởng để vượt qua bài kiểm tra nha.

Input:

• Dòng thứ nhất gồm ~3~ số nguyên ~n,m,q~ ~(n,m,q \le 3*10^5)~
• Dòng thứ hai cho biết diện tích ban đầu của ~n~ hòn đảo lần lượt là ~w_1,w_2,...,w_n~ ~(w_i \le 10^9)~
• ~m~ dòng tiếp theo cho biết thứ tự và thông tin các cây cầu được xây sẵn, cây cầu thứ ~j~ nối giữa hai hòn đảo là ~u_i~ và ~v_j~.
• ~q~ dòng tiếp theo cho biết thầy hiệu trưởng yêu cầu AP sử dụng thần chú ~C~ ~i~ ~W~ hoặc ~D~ ~j~.

Output

• ~q~ dòng được in ra là câu trả lời cho yêu cầu của thầy hiệu trưởng, vì thầy hiệu trưởng là một người thông thái cho nên khi đặt câu hỏi cho AP thì luôn có câu trả lời cho câu hỏi đó.

Subtask

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

Sample Input 1

6 6 8
8 2 1 8 3 7 
4 3
4 2
3 4
6 1
4 3
4 3
D 5
D 4
C 5 8
D 3
C 2 8
C 5 1
C 6 1
D 2

Sample Output 1

15
11
11
11
17
17
17
9

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

Hãy tìm đoạn con liên tiếp có tổng lớn nhất của dãy

Input

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

Output

• In ra giá trị thỏa mãn.

Điều kiện

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

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 2*10^5~.

Ví dụ

Input 1:

4
3 -2 4 -1

Output 1:

5

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.

Hãy đếm số đoạn con liên tiếp ~[l,r]~ của dãy ~a~ sao cho tổng của đoạn con đó bằng độ dài của đoạn, hay ~a_l + a_{l+1} + ... + a_r = r - l + 1~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.

Output

• In ra số đoạn con thỏa mãn.

Điều kiện

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

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 2*10^5~.

Ví dụ

Input 1:

3
1 2 0

Output 1:

3

Input 2:

5
1 1 0 1 1 

Output 2:

6

Cho bảng ~a~ có kích thước ~n \times m~.

Hãy tìm một hình chữ nhật con có tổng lớn nhất trong bảng.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m~.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên miêu tả bảng ~a~.

Output

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

Điều kiện

• ~1 \le n,m \le 400~.
• ~|a_{i,j}| \le 10^5~

Subtask

• ~50\%~ số điểm: ~n,m \le 40~
• ~50\%~ số điểm: ~n,m \le 400~.

Ví dụ

Input 1:

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

Output 1:

7

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm và ~q~ thao tác, thao tác thứ ~i~ có dạng ~(l_i,r_i,d_i)~, nghĩa là tăng giá trị của các phần tử trong mảng ~a~ từ vị trí ~l_i~ tới ~r_i~ thêm ~d_i~ đơn vị.

Bạn cần thực hiện ~k~ truy vấn, truy vấn thứ ~i~ có dạng ~(x_i,y_i)~, có nghĩa là thực hiện các thao tác ~x_i,x_{i+1},...,y_i~.

Hãy in ra giá trị của các phần tử trong mảng ~a~ sau khi thực hiện ~k~ truy vấn.

Input

• Dòng đầu tiên chứa ~3~ số nguyên dương ~n,q,k~.
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
• ~q~ dòng sau, dòng thứ ~i~ gồm ~3~ số nguyên dương ~l_i,r_i,d_i~ miêu tả thao tác thứ ~i~.
• ~k~ dòng sau, dòng thứ ~i~ gồm ~2~ số nguyên dương ~x_i,y_i~ miêu tả truy vấn thứ ~i~.

Output

• Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~k~ truy vấn.

Điều kiện

• ~1 \le n \le 10^5~.
• ~0 \le a_i,d_i \le 10^5~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 10^5~.

Ví dụ

Input 1:

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

Output 1:

9 18 17

Input 2:

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

Output 2:

5 18 31 20

Cho một dãy ~a~ gồm ~n~ phần tử nguyên không âm.

Có ~q~ truy vấn, mỗi truy vấn có dạng ~l,r,d~, có nghĩa là tăng phần tử thứ ~l~ lên ~d~ đơn vị, phần tử thứ ~l+1~ lên ~2*d~ đơn vị, ..., phần tử thứ ~r~ lên ~(r-l+1)*d~ đơn vị. Nói cách khác, phần tử thứ ~i \in [l,r]~ sẽ được tăng thêm ~(i-l+1)*d~ đơn vị.

Hãy in ra dãy ~a~ sau khi thực hiện đủ ~q~ truy vấn.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~
• Dòng thứ hai gồm ~n~ số nguyên không âm miêu tả dãy ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~3~ số nguyên ~(l,r,d)~ miêu tả truy vấn.

Output

• Gồm một dòng in ra ~n~ số, số thứ ~i~ là giá trị của phần tử ~a_i~ sau khi thực hiện ~q~ truy vấn.

Điều kiện

• ~1 \le n,q \le 10^6~.
• ~0 \le a_i,d_i \le 10^5~.

Subtask

• ~50\%~ số điểm: ~n \le 1000~.
• ~50\%~ số điểm: ~n \le 10^5~.

Ví dụ

Input 1:

1
10
3
1 1 40
1 1 0
1 1 -15

Output 1:

35 

Input 2:

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

Output 2:

5 9 13 20 25 

Cho bảng ~a~ có kích thước ~n \times m~. Có ~q~ truy vấn, mỗi truy vấn có dạng: ~(x,y,u,v)~, yêu cầu in ra tổng của hình chữ nhật có ô trái trên là ~(x,y)~ và ô phải dưới là ~(u,v)~ của bảng.

Input

• Dòng đầu tiên chứa ba số nguyên dương ~n,m,q~.
• ~n~ dòng sau, mỗi dòng gồm ~m~ số nguyên miêu tả bảng ~a~.
• ~q~ dòng sau, mỗi dòng gồm ~4~ số nguyên dương ~x,y,u,v~ miêu tả truy vấn.

Output

• Với mỗi truy vấn, in ra tổng của hình chữ nhật con cần tính.

Điều kiện

• ~1 \le n,m \le 500~.
• ~1 \le q \le 10^5~.
• ~1 \le x \le u \le n~
• ~1 \le y \le v \le m~.
• ~1 \le a_{i,j} \le 500~

Subtask

• ~50\%~ số điểm: ~q \le 100~
• ~50\%~ số điểm: ~q \le 10^5~.

Ví dụ

Input 1:

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

Output 1:

18
3
6
8

Kaguya đang bị Mokou đuổi đánh trên một đồ thị gồm ~n~ đỉnh và ~m~ cạnh. Kaguya hiện đang ở đỉnh ~a~ và Mokou thì ở đỉnh ~b~. Cả hai đều cần 1 đơn vị thời gian để di chuyển từ đỉnh này sang đỉnh khác.

Có bao nhiêu đỉnh mà nếu bạn đứng ở đó sẽ cứu được Kaguya?

Input

• Dòng đầu tiên gồm 2 số nguyên ~n, m~.
• Dòng thứ hai gồm 2 số nguyên ~a, b~.
• ~n~ dòng tiếp theo, mỗi dùng gồm 2 số nguyên ~u, v~, thể hiện có cạnh nối ~u~ và ~v~.

Output

• In ra số lượng đỉnh bạn có thể đứng để cứu Kaguya.

Điều kiện

• ~1 \le n, m \le 10^5~.
• ~1 \le u, v, a, b \le n~.

Ví dụ

Input:

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

Output:

2

Chú ý: Bạn có thể đứng ở đỉnh ~2~ hoặc ~3~.

Giới hạn

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

Cho hàm ~f(x)~ nhận đầu vào ~x~ là số nguyên không âm được định nghĩa như sau:

• Nếu ~x<10, f(x)=x~
• Ngược lại ~f(x)=f(D(x))~ với ~D(x)~ là tổng các chữ số trong biểu diễn thập phân của ~x~.
• Cho số nguyên dương ~n~, hãy tính ~f(n)~ .

Input:

Gồm một dòng duy nhất chứa số nguyên n ~(1≤n<10^{100000}).~

Output:

In ra một số nguyên là kết quả.

Sample Input 1

4

Sample Output 1

4

Cho dãy số gồm ~n~ số nguyên ~c_1, c_2, …, c_n~ và số nguyên dương ~m~. Nhiệm vụ của bạn là tìm một đoạn ~b_1,b_2,...,b_k~ ~(1 \le b_1 < b_2 < ... < b_k \le n)~ sao cho ~(\sum c_{b_i}) \% m~ là lớn nhất có thể. Đoạn con tìm được có thể rỗng.

Yêu cầu: Hãy in ra giá trị lớn nhất tìm được.

Input

• Dòng đầu tiên chứa ~2~ số nguyên duyên ~n,m~
• Dòng thứ hai chứa dãy ~c~ gồm ~n~ phần tử.

Output

• Một số nguyên duy nhất là giá trị lớn nhất tìm được.

Constraints

• ~1 \le n \le 40~
• ~1 \le m \le 10^9~
• ~1 \le c_i \le 10^9~

Subtask

• Có ~50\%~ số test ứng với ~n \le 20~.
• Có ~50\%~ số test ứng với ~n \le 40~.

Sample Input 1

4 4
5 2 4 1

Sample Output 1

3

Sample Input 2

3 20
199 41 299

Sample Output 2

19

Cho dãy số nguyên ~a~ gồm ~n~ phần tử. Hãy tính tổng của ~|a_i-a_j|~ với mọi cặp ~(i,j)~ thỏa mãn ~1 \le i < j \le n~.

Input

• Dòng đầu gồm ~1~ số nguyên ~n~ ~(1 \le n \le 10^5)~.
• Dòng sau gồm ~n~ số nguyên miêu tả dãy ~a~ ~(|a_i| \le 10^6)~

Output

• In ra kết quả tìm được.

Sample Test

Input

3
5 1 2

Output

8

Số nguyên dương ~N~ là chia hết cho ~9~ khi và chỉ khi tổng các chữ số của nó chia hết cho ~9~.

Yêu cầu: Cho số nguyên dương ~N~. Hãy đổi một chữ số trong ~𝑁~ sao cho số mới được tạo ra có giá trị nhỏ nhất và chia hết cho ~9~. Số mới được tạo ra có thể có chữ số ~0~ ở đầu tiên.

Dữ liệu nhập vào từ file văn bản CH9.INP:

• Dòng đầu tiên chứa ~T~ là số test dữ liệu của bài toán ~(T \le 15);~
• ~T~ dòng tiếp theo, mỗi dòng chứa một số nguyên dương ~N~.

Tổng số lượng chữ số ở mọi test không quá ~10^6~.

Kết quả ghi ra file văn bản CH9.OUT:

Gồm ~𝑇~ dòng, mỗi dòng chứa một số nguyên dương tương ứng là kết quả theo yêu cầu.

Ràng buộc:

• Có ~50\%~ số test tương ứng với ~50\%~ số điểm của bài thoả mãn: ~T=1;~
• ~50\%~ số test còn lại ứng với ~50\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3
34125
5441
22221

Output

34128
0441
22221

It works … on my machine 😈

Cho bốn số nguyên ~n, x, y, m~. Dãy số ~A~ có độ dài ~n~ được tạo ra theo cách sau:

• ~a_1 = x~;
• ~a_i = (a_{i-1}*x+y) \% m~ với ~2 \le i \le n~.

Dãy số ~B~ là dãy số ~A~ sau khi sắp xếp không giảm.

Tính: ~\sum_{i=1}^{n} (b_i * i) \% m~

Input: smod.inp

• Gồm một dòng chứa bốn số nguyên ~n, x, y, m~ ~(1 \le x, y \le m)~.

Output: smod.out

• In ra một số nguyên là kết quả của bài toán.

Scoring:

• Subtask ~1~ ~(40\%)~: ~n \le 10^5; m \le 10^9~;
• Subtask ~2~ ~(40\%)~: ~n \le 3*10^7; m \le 3*10^7~;
• Subtask ~3~ ~(20\%)~: ~n \le 10^{18}; m \le 10^6~;

Sample Input

3 2 1 10

Sample Output

0

Note

• Dãy số ~A~: ~2, 5, 1~;
• Dãy số ~B~: ~1, 2, 5~;
• Kết quả: ~(1*1+2*2+5*3)\%10=0~.

Ở một vương quốc nọ có ~n~ thành phố, được đánh số từ ~1~ đến ~n~. Mạng lưới giao thông của vương quốc gồm ~m~ con đường, con đường thứ ~i~ nối hai thành phố ~u_i~ và ~v_i~ với độ dài đúng bằng ~1~ ki-lô-mét.

Có ~k~ dự án nhà máy điện đang được triển khai, dự án thứ ~j~ sẽ xây một nhà máy điện đặt tại thành phố ~p_j~, cung cấp điện cho tất cả các thành phố nằm trong bán kính ~r_j~ ki-lô-mét (giả sử rằng quãng đường di chuyển trong nội thành là bằng ~0~). Nhà vua đang băn khoăn, những thành phố nào đã được cấp điện, và những thành phố nào chưa được cấp điện? Hãy giúp nhà vua giải quyết bài toán này nhé.

Input

Dòng đầu chứa ba số nguyên ~n~, ~m~, ~k~ (~2 \le n, m \le 2 \times 10^5~; ~0 \le k \le 5 \times 10^5~).

~m~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~u_i~, ~v_i~ (~1 \le u_i, v_i \le n~; ~u_i \ne v_i~) mô tả con đường thứ ~i~.

~k~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~p_j~, ~r_j~ (~1 \le p_j \le n~; ~0 \le r_j \le 10^9~) mô tả dự án thứ ~j~.

Output

Gồm một dòng duy nhất chứa một xâu nhị phân gồm ~n~ kí tự, kí tự thứ ~i~ bằng "1" nếu thành phố thứ ~i~ đã được cấp điện, ngược lại kí tự thứ ~i~ bằng "0" nếu thành phố thứ ~i~ chưa được cấp điện.

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~n, m \le 1000~.
• Subtask ~2~ (~30\%~ số điểm): ~r_1 = r_2 = \dots = r_{k - 1} = r_k~.
• Subtask ~3~ (~30\%~ số điểm): Không có ràng buộc gì thêm.

Example

Input 1

4 3 1
1 2
1 3
2 4
2 1

Output 1

1101

Input 2

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

Output 2

101111