Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của hai số tự nhiên liên tiếp hay không.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~1 \leq N \le 10^9~)

Output

In ra YES nếu ~N~ là tổng của hai số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

5

Output:

YES

Note: Do ~5 = 2 + 3~ nên ~5~ là tổng của hai số tự nhiên liên tiếp.

Sample Test 2

Input:

6

Output:

NO

Cho một số tự nhiên ~N~. Hãy cho biết số ~N~ có là tổng của ~4~ số tự nhiên liên tiếp hay không, nếu có hãy đưa ra số nhỏ nhất trong ~4~ số đó.

Input

Gồm một số tự nhiên ~N~ duy nhất. (~N \le 10^9~)

Output

In ra số nhỏ nhất trong ~4~ số nếu ~N~ là tổng của ~4~ số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

10

Output:

1

Note: Do ~10 = 1 + 2 + 3 + 4~ nên ~10~ là tổng của bốn số tự nhiên liên tiếp.

Sample Test 2

Input:

12

Output:

NO

Cho hai số tự nhiên ~N~ và ~k~. Hãy cho biết số ~N~ có là tổng của ~k~ số tự nhiên liên tiếp hay không, nếu có hãy đưa ra số nhỏ nhất trong ~k~ số đó.

Input

Gồm hai dòng, dòng thứ nhất chứa số tự nhiên ~N~ và dòng thứ hai chứa số tự nhiên ~k~. (~N, k \le 10^9~, ~k \ge 1~)

Output

In ra số nhỏ nhất trong ~k~ số nếu ~N~ là tổng của ~k~ số tự nhiên liên tiếp, ngược lại in ra NO.

Sample Test 1

Input:

10
4

Output:

1

Note: Do ~k = 4~, ~10 = 1 + 2 + 3 + 4~ nên ~10~ là tổng của ~k~ số tự nhiên liên tiếp.

Sample Test 2

Input:

15
3

Output:

4

Note: ~15 = 4 + 5 + 6~

Sample Test 3

Input:

50
6

Output:

NO

Một số nguyên dương ~A~ được gọi là hoàn hảo nếu ~2 \times A \leq K~, với ~K~ là tổng các ước dương của ~A~.

Ví dụ, ~12~ là số hoàn hảo vì ~2 * 12 \leq K~ với ~K = 1 + 2 + 3 + 4 + 6 + 12 = 28.~

Cho ~N~ số nguyên dương ~A_1, A_2, \ldots, A_n~, hãy đếm số lượng số hoàn hảo trong dãy đã cho.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~. (~N \leq 10^4~)
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên dương ~A_i~. (~A_i \leq 10^6~)

Output

• In ra số lượng số hoàn hảo trong dãy đã cho.

Sample Test

Input:

5
8
16
12
6
7

Output:

2

Cho ~N~ số nguyên ~A_1, A_2, \ldots, A_n~, hãy đếm số lượng số đơn lẻ trong dãy đã cho.

Số đơn lẻ trong dãy là số chỉ xuất hiện đúng một lần.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~. (~N \leq 10^6~)
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~A_i~. (~0 \leq A_i \leq 10^6~)

Output

• In ra số lượng số đơn lẻ trong dãy đã cho.

Sample Test

Input:

8
9
9
7
7
6
11
9
5

Output:

3

TDZ rất thích con số ~42~, vì nó là số trước số ~43~ và số sau số ~41~. Với ước mơ tương lai trở thành một giáo sư đại tài, cậu quyết định đi nghiên cứu sâu hơn số ~42~ này.

Cậu lấy số ~42~ này nhân đôi lên, lấy 2 chữ số cuối của kết quả tìm được tiếp tục nhân đôi tiếp. Quá trình này diễn ra vô tận. Sau ~N~ lần lặp lại như thế, cậu đã tìm ra một phát hiện mới mẻ. Đố các bạn, sau ~N~ lần TDZ đã thu được số nào?

Input

Gồm một số tự nhiên ~N~ duy nhất.

Output

In ra số TDZ thu được sau khi lặp lại quá trình nhân đôi ~N~ lần.

Subtasks

Subtask ~1~ (~50\%~ số điểm): ~N \leq 10^3~.

Subtask ~2~ (~50\%~ số điểm): ~N \leq 10^9~.

Sample Test

Input:

3

Output

36

Note:

• Nhân đôi lần ~1~ được ~42 \times 2 = 84~.
• Nhân đôi lần ~2~ được ~84 \times 2 = 168~, lấy hai chữ số cuối được ~68~.
• Nhân đôi lần ~3~ được ~68 \times 2 = 136~, láy hai chữ số cuối được ~36~.

Cho dãy ~A~ gồm ~n~ phần tử, phần tử thứ ~i \ (1 \le i \le n)~ có giá trị ~a_i~.

Bạn có thể biến đổi dãy ~A~ bằng thao tác sau: Chọn hai phần tử liên tiếp trong dãy và thay thế hai phần tử này bằng tổng của chúng.

Hãy đếm số lượng thao tác tối thiểu để dãy ~A~ là dãy đối xứng. Dãy ~A~ được coi là dãy đối xứng nếu đọc từ phải sang trái vẫn thu được dãy ~A~ ban đầu.

Input

• Dòng đầu tiên chứa số nguyên dương ~n;~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_i \ (1 \le a_i \le 10^9)~.

Output

In ra kết quả là số thao tác tối thiểu để dãy ~A~ là dãy đối xứng.

Scoring

• Subtask 1 [30%]: ~n \le 10;~
• Subtask 2 [30%]: ~n \le 1000;~
• Subtask 3 [40%]: ~n \le 10^6.~

Examples

Input

3
1 2 3

Output

1

Giải thích: ~\textbf{1 2} \ 3 \rightarrow 3 \ 3.~

Input

5
1 2 4 6 1

Output

1

Giải thích: ~1 \ {\textbf{2 4}} \ 6 \ 1 \rightarrow 1 \ 6 \ 6 \ 1~.

Input

4
1 4 3 2

Output

2

Giải thích: ~\textbf{1 4} \ 3 \ 2 \rightarrow 5 \ \textbf{3 2} \ \rightarrow 5 \ 5~.

Một số ~X~ ban đầu được tách thành ~N~ số ~A_1, A_2, \ldots, A_n~. Hãy tìm cách ghép lại ~N~ số này, theo thứ tự bất kỳ, thành số lớn nhất có thể.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~N \leq 100~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa số ~A_i~ (độ dài số ~A_i~ không vượt quá ~100~). Lưu ý, ~A_i~ có thể có các chữ số ~0~ đứng ở đầu.

Output

• In ra số lớn nhất có thể tạo được từ việc ghép ~N~ số đã cho. Số này có thể có các chữ số ~0~ đứng ở đầu.

Sample Test

Input:

4
2
20
004
66

Output:

66220004

Cho số nguyên dương ~N~. Hãy đếm số cách xoá đi một đoạn chữ số liên tiếp của ~N~ (không được xoá hết) để nhận được số mới chia hết cho ~3~, biết rằng số mới nhận được có thể có thừa chữ số ~0~ ở đầu.

Hai cách xoá được coi là khác nhau nếu có một vị trí được xoá trong cách này nhưng không được xoá trong cách kia.

Input

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

Output

• In ra một số nguyên là số cách xoá tìm được.

Subtasks

• Subtask 1 (~50\%~ số điểm): ~N \le 10^{300}~.
• Subtask 2 (~25\%~ số điểm): ~N \le 10^{10000}~.
• Subtask 3 (~25\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test 1

Input

1005

Output

4

Sample Test 2

Input

2009

Output

3

Trên trục số ~Ox~, cho ~𝑁~ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm ~𝑀~ được gọi là nằm trong đoạn thẳng ~𝐴𝐵~ nếu ~𝐴 ≤ 𝑀 ≤ 𝐵~.

Yêu cầu: Đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

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

• Dòng đầu tiên gồm hai số nguyên ~𝑁~ và ~𝐾~ ~(1 ≤ 𝐾 ≤ 𝑁 ≤ 10^5);~
• ~𝑁~ dòng sau, mỗi dòng gồm hai số nguyên ~𝑎, 𝑏~ mô tả hai điểm đầu và cuối của đoạn thẳng ~(1 ≤ 𝑎 ≤ 𝑏 ≤ 10^{18})~.

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

Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng ~𝐾~ đoạn thẳng.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~𝑎, 𝑏 ≤ 10^3;~
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~𝐾 = 𝑁;~
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

3 2
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong đúng ~2~ đoạn thẳng là: ~2, 6, 7~.

• Điểm có toạ độ ~2~ nằm trong ~2~ đoạn thẳng: đầu tiên và thứ hai.
• Điểm có toạ độ ~6, 7~ nằm trong ~2~ đoạn thẳng: thứ hai và thứ ba.

Input

3 1
1 5
2 8
3 7

Output

2   

Giải thích: Toạ độ của ~2~ điểm nằm trong đúng ~1~ đoạn thẳng là: ~1, 8~.

• Điểm có toạ độ ~1~ chỉ nằm trong đoạn thẳng đầu tiên.
• Điểm có toạ độ ~8~ chỉ nằm trong đoạn thẳng thứ ba.

Input

3 3
1 5
2 8
3 7

Output

3

Giải thích: Toạ độ của ~3~ điểm nằm trong cả ~3~ đoạn thẳng là: ~3,4,5~.

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng ~N~ tờ tiền. Tờ tiền thứ ~i~ có mệnh giá ~a_i~. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu: Hãy giúp hai bạn tính tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Dữ liệu:

• Dòng đầu tiên chứa số nguyên dương ~N \ (N \le 500);~
• Dòng thứ hai bao gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá ~10^5~.

Kết quả:

Gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn ~N \le 3;~
• ~30\%~ số test tiếp theo ứng với ~30\%~ số điểm của bài thoả mãn ~N \le 12;~
• ~30\%~ số test còn lại ứng với ~30\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5
1 2 4 5 2

Output

7

Giải thích:

• An có thể chọn những tờ tiền có mệnh giá ~1, 2, 4~.
• Bình chọn những tờ tiền còn lại có mệnh giá ~5, 2~.
• Mỗi người sẽ nhận được tổng số tiền là ~7~. Vì số tiền mỗi người nhận đã bằng nhau và đã chia hết số tiền nên họ sẽ không đầu tư.

Input

5
9 8 4 5 13

Output

17

Giải thích:

• An sẽ chọn những tờ tiền có mệnh giá ~9, 8~.
• Bình sẽ chọn những tờ tiền có mệnh giá ~4, 13~.
• Mỗi người sẽ nhận được tổng số tiền là ~17~. Tờ tiền còn lại có mệnh giá ~5~ sẽ đem đi đầu tư.

Đã là sản phẩm thì phải có mã vạch ở trên nên Nitori quyết định in mã vạch cho sản phẩm dưa chuột của mình. Cô muốn mã vạch có kích thước ~n \times m~, kí tự # thể hiện màu đen còn . thể hiện màu trắng. Các cột của mã vạch phải cùng màu, số lượng cột cùng màu nhau ở cạnh nhau ít nhất là ~x~ và nhiều nhất là ~y~.

Do máy in bị trục trặc nên mã vạch đã bị in sai hết cả. Nitori muốn tiết kiệm chi phí nên hãy đếm số lượng ít nhất kí tự phải sửa để được mã vạch thỏa mãn yêu cầu nhé!

Input

• Dòng đầu tiên gồm các số nguyên dương ~1 \le n, m, x, y \le 1000~.
• ~n~ dòng tiếp theo gồm ~m~ kí tự thuộc # hoặc ..

Output

• Số lượng kí tự ít nhất phải sửa.

Sample Test

Input:

6 5 1 2
##.#.
.###.
###..
#...#
.##.#
###..

Output:

11

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~1~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Ví dụ, một vị khách đến ở thời điểm ~5~, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~6~ và tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ (~n \leq 10^5~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^5~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Sample Test

Input:

4
1 10 45 10

Output:

2

Đây là phiên bản khó hơn của bài PA120. Điểm khác biệt duy nhất giữa hai bài là số ~k~ và giới hạn các số.

Sau khi bán hết sách, TDZ chuyển sang mở một quán cà phê.

Qua thăm dò, TDZ đã biết trước ngày khai trương sẽ có ~n~ khách, khách thứ ~i~ sẽ vào thời điểm ~h_i~. Để phục vụ lượng khách đến dồn dập, quán cà phê có thuê thêm một số nhân viên ưu tú. Mỗi nhân viên có thể hoạt động không ngừng nghỉ, mỗi lần chỉ phục vụ một khách trong đúng ~k~ đơn vị thời gian. Nhưng nếu một vị khách tới mà không nhận được sự phục vụ ngay thì sẽ lập tức bỏ đi.

Cụ thể, một vị khách đến ở thời điểm ~x~ nào đó, thì nhân viên sẽ phục vụ xong cho vị khách đó ở thời điểm ~x + k~. Khách đó sẽ rời quán và nhân viên tiếp tục phục vụ luôn khách tiếp theo (nếu có).

Hãy giúp TDZ tìm ra số lượng nhân viên cần thuê ít nhất mà vẫn đảm bảo tất cả các khách đều được phục vụ.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n~, ~k~ (~n \leq 10^6, k \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~h_1, h_2, h_3, \ldots, h_n~ tương ứng với thời điểm khách đến (~h_i \leq 10^9~).

Output

In ra số lượng nhân viên ít nhất cần thuê.

Subtasks

• Subtask ~1~ (~25\%~): ~n \leq 10^3~.
• Subtask ~2~ (~37.5\%~): ~n \leq 10^6, h_i \leq 10^6~.
• Subtask ~3~ (~37.5\%~): Không có điều kiện gì thêm.

Sample Test

Input:

5 2
1 2 5 3 5

Output:

2

Note: Thuê hai nhân viên:

• Nhân viên thứ nhất sẽ phục vụ khách thứ nhất, rồi đến khách thứ tư và cuối cùng phục vụ khách thứ ba.
• Nhân viên thứ hai phục vụ khách thứ hai rồi đến khách thứ năm.

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

Có ~n~ người xếp hàng mua vé một trận bóng theo thứ tự ~1~ đến ~n~. Mỗi người cần mua một vé, nhưng người bán vé lại có thể bán cho mỗi người tối đa hai vé. Do đó, một số người có thể rời hàng và nhờ người đứng trước mình mua hộ vé. Biết ~t_i~ là thời gian cần thiết để người thứ ~i~ mua vé cho mình. Nếu người thứ ~i+1~ rời hàng và nhờ người ~i~ mua hộ vé thì mất ~r_i~ thời gian để mua cho cả hai.

Hãy xác định thời gian mua vé nhỏ nhất.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(n \le 6*10^4)~
• Dòng thứ hai chứa ~n~ số nguyên dương miêu tả dãy ~t[1], t[2], ..., t[n]~.~(t[i] \le 30000)~
• Dòng thứ ba chứa ~n-1~ số nguyên dương miêu tả dãy ~r_[1], r_[2], ..., r_[n-1]~. ~(r[i] \le 30000)~

Output

• In ra thời gian ít nhất để mua vé cho ~n~ người.

Sample Test

Input

5
2 5 7 8 4
4 9 10 10

Output

18

Cho ba số nguyên dương ~c~, ~d~, ~x~. Bạn cần phải tìm số cặp ~(a,b)~ thỏa mãn ~c*lcm(a,b) - d*gcd(a,b) = x~. Ở đây, ~lcm(a,b)~ là bội chung nhỏ nhất của ~(a,b)~, ~gcd(a,b)~ là ước chung lớn nhất của ~(a,b)~.

Input

• Dòng đầu gồm số nguyên dương ~t~ ~(t \le 10^4)~ là số lượng test case.
• ~t~ dòng sau, mỗi dòng gồm ba số nguyên dương ~c~, ~d~, ~x~ miêu tả test case. ~(1 \le c,d,x \le 10^7)~

Output

• Với mỗi test case, in ra số lượng cặp ~(a,b)~ thỏa mãn.

Sample Test

Input

4
1 1 3
4 2 6
3 3 7
2 7 25

Output

4
3
0
8

Giải thích: Ở test case thứ nhất, có ~4~ cặp thỏa mãn là ~(1,4), (4,1), (3,6), (6,3)~

Cho ~t~ truy vấn và giá trị ~mod~ ~(1 \le mod \le 2*10^9)~, mỗi truy vấn gồm hai số nguyên dương ~n~, ~k~. Kí hiệu ~C(k,n)~ là tổ hợp chập ~k~ của ~n~, hãy in ra ~C(k,n)~ cho mỗi truy vấn tương ứng. Do kết quả có thể rất lớn nên hãy in nó sau khi lấy phần dư cho ~mod~.

Subtask

• Sub ~1~: ~t \le 10^5~, ~1 \le k \le n \le 2000~. (30%)
• Sub ~2~: ~t = 1~, ~1 \le k \le n \le 10^5~. (30%)
• Sub ~3~: ~t \le 10^5~, ~1 \le k \le n \le 10^5~, ~mod = 10^9+7~. (40%)

Input

• Dòng đầu tiên gồm một số nguyên dương ~sub~ miêu tả subtask mà test này tương ứng. (~1 \le sub \le 3~)
• Dòng thứ hai gồm hai số nguyên dương ~t~ và ~mod~.
• ~t~ dòng sau, mỗi dòng gồm hai số nguyên dương ~n~, ~k~ (~k \le n~) miêu tả truy vấn tương ứng.

Output

• In ra ~t~ dòng, mỗi dòng là kết quả của truy vấn tương ứng.

Sample Test

Input:

1
3 2345
6 4
8 4
15 8

Output:

15
70
1745

Định nghĩa ~f(x)~ là tổng các chữ số của số nguyên ~x~. Cho số nguyên ~k~, hãy tìm giá trị ~f(x)~ nhỏ nhất có thể khi xét các số nguyên dương ~x~ chia hết cho ~k~.

Input

• Gồm một số nguyên ~2 \le k \le 100000~.

Output

• In ra giá trị ~f(x)~ nhỏ nhất.

Sample Test

Input:

6

Output:

3

Cho bốn số thực ~𝐴, 𝐵, 𝐶, 𝐷~. Hỏi tích của bốn số đó là số dương, số âm hay số ~0~.

Dữ liệu:

Gồm bốn dòng, mỗi dòng gồm một số thực lần lượt là bốn số ~𝐴, 𝐵, 𝐶, 𝐷~ ~(-10^{18} ≤ 𝐴, 𝐵, 𝐶, 𝐷 ≤ 10^{18})~.

Kết quả:

Một số nguyên duy nhất là:

• ~1~ nếu tích bốn số là số dương~;~
• ~-1~ nếu tích bốn số là số âm~;~
• ~0~ nếu tích bốn số là số ~0.~

Ví dụ

Input

20.21
-1.2
-2.3
1.0

Output

1

Input

5.0
-8.9
0.0
123.456

Output

0

Lớp học của thầy Tùng có ~n~ học sinh được đánh số thứ tự từ ~1~ đến ~n~. Một học kỳ trôi qua, thầy hỏi từng bạn xem trong lớp bạn đó ghét bạn nào nhất để chuẩn bị cho một "mưu đồ đen tối". Sau khi hỏi cả lớp xong, thầy có một danh sách "tư thù" của mỗi bạn là một dãy ~A~, trong đó, người mà bạn ~i~ ghét nhất là bạn ~a_i~. Vì lớp của thầy là một môi trường thân thiện rộn rã tiếng cười nên không ai ghét chính mình.

Sau đó, thầy muốn biết là có bao nhiêu cặp là "kẻ thù" của nhau để sang học kỳ sau thầy xếp chỗ hai bạn đó ngồi gần nhau để hoá thù thành bạn, từ "ghét ghét" thành "thích thích" rồi "thương thương". Hai học sinh ~(x,y)~ là "kẻ thù" của nhau nếu ~a_x=y~ và ~a_y=x~.

Hãy giúp thầy Tùng đếm số cặp học sinh là "kẻ thù" của nhau.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~.
• Dòng tiếp theo chứa ~n~ số nguyên ~a_1,a_2,…,a_n~ ~(1≤a_i≤n; \ a_i≠i)~.

Output

Một số nguyên là số cặp là "kẻ thù" của nhau.

Scoring

• Subtask ~1 \ (50\%)~: ~n \le 5000~.
• Subtask ~2 \ (50\%)~: ~n \le 10^6~.

Ví dụ

Input

4
2 1 4 3

Output

2

Giải thích

Các cặp đó là: ~(1, 2), (3, 4)~.

Make sure you read the statement carefully. Try to get AC at the first submission :D .

Cho số nguyên dương ~n~ và ~3~ số nguyên tố ~a,b,c~.

Hãy đếm số số nguyên dương ~x~ thỏa mãn ~x \le n~ và ~x~ chia hết cho ít nhất một trong ~3~ số ~a,b,c~.

Input

• Một dòng duy nhất chứa các số ~n,a,b,c~ (~a,b,c \in P~, ~a,b,c,n \le 10^{10}~)

Output

• In ra trên một dòng một số nguyên duy nhất là kết quả của bài toán.

Sample Input

20 2 3 5

Sample Output

14

Notes

• Các số đó là ~2,3,4,5,6,8,9,10,12,14,15,16,18,20~.

Scoring

• Subtask ~1 \ (50\%)~: ~n,a,b,c \le 10^7~.
• Subtask ~2 \ (50\%)~: ~n,a,b,c \le 10^{10}~.

Khôi có một xâu ~S~ gồm các chữ cái tiếng Anh thuờng. Cậu sẽ lần luợt thực hiện các thao tác sau cho đến khi xâu ~S~ rỗng:

• Chèn phần tử trung vị của xâu ~S~ vào cuối xâu ~T~.
• Xoá phần tử trung vị của xâu ~S~ khỏi xâu.

Phần tử trung vị của một dãy có ~n~ phần tử là phần tử thứ ~\lceil n / 2 \rceil~ của dãy đó. Ví dụ: abcdefg, dino có phần tử trung vị là d và i.

Cho ~T~ là xâu sau khi Khôi thực hiện hết tất cả các thao tác, nhiệm vụ của bạn là tìm lại xâu ~S~ ban đầu.

Input

Gồm hai dòng, dòng đầu tiên gồm số nguyên duơng ~N~ là số kí tự của xâu ~T~ ~(N \le 2 \times 10^5)~. Dòng thứ hai chứa xâu ~T~ có ~N~ kí tự.

Output

In ra xâu ~S~ ban đầu thoả mãn

Sample Input

8       
tungfint

Sample Output

nfntugit

Có ~n~ đồ chơi trong balo của bạn kh0i, đồ chơi thứ ~i~ có kích thước là ~a_i~. kh0i có ~q~ người bạn cả trai và gái, mỗi người bạn sẽ đưa kh0i một số nguyên ~x~ và yêu cầu kh0i tìm đồ chơi thứ ~j~ có kích thước lớn nhất nhất thỏa mãn ~a_j \leq x~.

Input

• Dòng đầu chứa hai số nguyên duơng ~n, q \ (n, q \leq 10^6)~.
• Dòng thứ hai chứa n số nguyên dương ~a_1, a_2, ..., a_n \ (a_i \leq 10^9)~
• ~q~ dòng sau, mỗi dòng là một số nguyên dương ~x \ (x \leq 10^9)~

Output

• Với mỗi yêu cầu của một người bạn, hãy in ra kích thước của đồ chơi có kích thước lớn nhất thỏa mãn (nếu không có đồ chơi nào bé hơn ~x~ thì in ra ~-1~).

Sample Input

5 2
2 7 3 2 5
3
6

Sample Output

3
5

Giới hạn

• ~50\%~ test đầu tiên: ~n, q \leq 1000~.
• ~50\%~ test sau: Không có ràng buộc gì thêm.

Số nguyên tố là số gồm đúng ~2~ ước là ~1~ và chính nó. Số nửa nguyên tố là số có số lượng ước nguyên dương của nó là một số nguyên tố.

Yêu cầu: Cho 2 số nguyên dương ~a,b~, đếm số lượng số nửa nguyên tố trong đoạn ~[a,b]~.

Input

• Dòng đầu tiên gồm số nguyên dương ~T~ tương ứng với số bộ dữ liệu;
• ~T~ dòng sau, mỗi dòng gồm hai số nguyên dương ~a,b~.

Output

• Gồm ~T~ dòng, mỗi dòng ghi kết quả của bộ dữ liệu tương ứng.

Sample Input

2
6 9
100 100

Sample Output

2
0

Scoring

• Subtask ~1 \ (20\%)~: ~1\le T, a, b \le 100~.
• Subtask ~2 \ (30\%)~: ~1\le T, a, b \le 1000~.
• Subtask ~3 \ (30\%)~: ~1\le T, a, b \le 10^5~.
• Subtask ~4 \ (20\%)~: ~1\le T, a, b \le 10^6~.

Cho một bảng cờ caro ~3 \times 3~, gồm các kí tự X, O và . lần lượt là dấu của người thứ nhất, người thứ hai và ô trống. Người thứ nhất đi trước, sau đó hai người chơi lần lượt đặt các dấu của mình vào các ô trống. Trò chơi kết thúc khi có một người tạo được ra một dãy gồm 3 dấu của người chơi đó liên tiếp theo hàng dọc, ngang hoặc chéo, hoặc hòa khi không còn ô trống mà chưa có ai thắng. Ví dụ:

Người thứ nhất thắng:

XOX
X.O
X.O

Người thứ hai thắng

OOO
X.X
X..

Ván chưa kết thúc (chưa có ai thắng)

OX.
.X.
O..

Ván đấu hòa

XOX
OOX
XXO

Không hợp lệ (người chơi thứ nhất có quá nhiều dấu trên bàn so với người thứ hai)

XXX
OXO
...

Chú ý: Tất cả các bàn cờ không thỏa mãn bốn trường hợp đầu tiên thì được coi là không hợp lệ.

Cho trước một bảng cờ đã có một số dấu được đặt lên, hãy xác định xem trạng thái của bàn cờ là người thứ nhất thắng, người thứ hai thắng, chưa kết thúc, hòa hoặc không hợp lệ.

Input

Input gồm nhiều bộ test, mỗi test gồm một bảng ~3 \times 3~, chỉ có các kí tự X, O, .. Số lượng bộ test không quá ~2000~.

Chú ý: Sample Input có một dòng cách giữa các test để cho dễ nhìn, còn trong Input thật các bộ test được viết liền nhau.

Output

Với mỗi test, in ra TROLL nếu người thứ nhất thắng, MIM nếu người thứ hai thắng, DAK nếu ván đấu hòa, INCOMPLETE nếu ván đấu chưa kết thúc hoặc INVALID nếu trạng thái hiện tại là không hợp lệ.

Sample Input

3
XOX
X.O
X.O

XXX
OXO
...

XOX
OOX
XXO

Sample Output

TROLL
INVALID
DAK

Cho số nguyên dương ~n~. Hãy đếm số cặp số nguyên dương ~(x, y)~ thoả mãn:

• ~1\le x, y \le n~.
• Chữ số đầu tiên của ~x~ bằng chữ số cuối cùng của ~y~.
• Chữ số đầu tiên của ~y~ bằng chữ số cuối cùng của ~x~.

Input

Một dòng duy nhất chứa số nguyên dương ~n~.

Output

Một số nguyên là số cặp ~(x, y)~ thoả mãn.

Examples

Input

11

Output

12

Giải thích

Các cặp số ~(x,y)~ thoả mãn: ~(1,1), (2,2), (3,3),(4,4), (5,5),(6,6),(7,7),(8,8),(9,9),(11,1),(1,11),(11,11)~.

Scoring

• Subtask ~1 \ (50\%)~: ~n \le 1000~.
• Subtask ~2 \ (50\%)~: ~n \le 10^6~.

Có ~n~ lá bài, lá bài thứ ~i~ có giá trị là ~a_i~. Alice và Bob thì lại rất thích chơi bài, và họ chia bài như sau:

• Alice sẽ chọn một số ~x~ và Bob sẽ chọn một số ~y~ ~(x < y)~.
• Sau đó, các lá bài ~a_1, a_2, \dots, a_x~ sẽ đuợc chia cho Alice, còn các lá bài từ ~a_y, a_{y + 1}, \dots, a_n~ sẽ đuợc chia cho Bob.

Vì Alice và Bob là bạn thân và không muốn ai thua thiệt, họ sẽ chia sao cho tổng giá trị các lá bài đuợc chia cho mỗi nguời là bằng nhau.

Với tất cả cách chia thoả mãn, bạn hãy tìm cách sao cho số luợng bài đuợc chia ra là lớn nhất.

Input

Dòng đầu chứa số nguyên duơng ~n~ là số luợng lá bài. Dòng thứ hai gồm ~n~ số nguyên duơng ~a_1, a_2, \dots, a_n~.

Output

In ra trên một dòng một số nguyên duy nhất là kết quả của bài toán.

Sample Input

7
1 2 1 3 1 2 2

Sample Output

5

Notes: Chọn ~x = 3, \ y = 6~. Vậy có tổng cộng 5 lá bài ~1, 2, 3, 6, 7~ đuợc chọn.

Sample Input 2

5
1 2 3 4 4

Sample Output 2

0

Cho 2 số nguyên dương ~n~ và ~k~. Một số ~mim~ cơ số ~x~ được định nghĩa là một số có thể thu được từ tổng các lũy thừa riêng biệt của ~x~.

Ví dụ, với ~n=3~, các số ~mim~ có thể là ~9 = 3^2~, ~12=3^2+3^1~, ~37=3^3+3^2+3^0…~ Trong khi đó, với ~n=3~, các số 2, 5, 18, … không phải là một số ~mim~.

Vậy, với số ~n~ và ~k~ cho trước, hãy tìm số ~mim~ thứ ~k~ theo thứ tự tăng dần. Vì kết quả có thể rất lớn nên hãy in ra theo module ~10^9+7~.

Input

2 số tự nhiên ~n~ và ~k~.

Output

Số ~mim~ cơ số ~n~ thứ ~k~.

Sample Test

Input:

3 2

Output:

3

Ràng buộc:

• Subtask 1: ~n = 2, k \le 10^{18}~ (30%)
• Subtask 2: ~2 \le n \le 100, k \le 10^{18}~ (70%)

Một xâu xoay được tạo ra bởi chuyển một chữ cái từ cuối lên đầu xâu. Ví dụ, các xâu xoay của ~marisa~ là ~marisa, amaris, samari, isamar, risama~ và ~arisam~.

Hãy xác định xâu xoay có thứ tự từ điển nhỏ nhất của xâu ~S~ cho trước.

Input

• Gồm một dòng chứa xâu ~s~.

Constraints

• ~1 \le |s| \le 10^6~

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~n \le 10^3~
• Subtask ~2~ (~50\%~ số điểm): ~n \le 10^6~

Output

• In ra xâu có thứ tự từ điển nhỏ nhất.

Sample Input 1

marisa

Sample Output 1

amaris

Cho ~n~ xâu kí tự, đây được gọi là ~n~ xâu "dữ liệu".

Bạn cần trả lời ~m~ câu hỏi có dạng như sau:

• Cho xâu ~s~, hãy xác định xem có tồn tại xâu kí tự trong ~n~ xâu dữ liệu được cho thỏa mãn nó có chung độ dài và khác xâu ~s~ ở đúng một vị trí.

Input

• Dòng đầu tiên gồm ~2~ số nguyên dương ~n,m~.
• ~n~ dòng sau, mỗi dòng gồm một xâu kí tự miêu tả các xâu dữ liệu.
• ~m~ dòng sau, mỗi dòng gồm một xâu kí tự miêu tả truy vấn.
• Các xâu trong Input đều chỉ chứa ba kí tự ~'a','b','c'~.

Constraints

• ~1 \le n,m \le 3\times10^5~
• Độ dài các xâu được cho không quá ~6 \times 10^5~.

Subtask:

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

Output

• Với mỗi truy vấn, in ra "YES" nếu tồn tại xâu thỏa mãn, ngược lại in ra "NO".

Sample Input 1

2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

Sample Output 1

YES
NO
NO

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]~.

Cho 2 dãy số nguyên dương ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử. Với ~j~ từ 1 đến ~m~ hãy tìm ~gcd(a_1 + b_j, a_2 + b_j,...,a_n + b_j)~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le n, m \le 2 \times 10^5~.
• Dòng thứ 2 gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~.
• Dong thứ 3 gồm ~n~ số nguyên dương ~1 \le b_j \le 10^9~.

Output

• In ra ~m~ số nguyên tương ứng với đáp án.

Sample Test

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24

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

Có ~q~ truy vấn, mỗi truy vấn có dạng ~l_i,r_i~ ~(l_i < r_i)~, hãy in ra tổng của số lớn nhất và số lớn thứ hai trong đoạn ~[l_i,r_i]~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ là số phần tử của dãy.
• 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~.
• ~q~ dòng sau, mỗi dòng gồm ~2~ số nguyên dương ~l_i,r_i~ miêu tả truy vấn.

Constraints

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

Subtask:

• Subtask ~1~ (~50\%~ số điểm): ~n \le 2000~
• Subtask ~2~ (~50\%~ số điểm): ~n \le 3*10^{5}~

Output

• Với mỗi truy vấn, in ra kết quả cần tính.

Sample Input 1

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

Sample Output 1

5
9
8