Mẹ có ~2024~ cái kẹo để chia cho hai anh em Dino và Daisy. Mẹ muốn chia sao cho cả hai anh em đều có kẹo (mỗi người nhận ít nhất ~1~ cái) và số kẹo của em Daisy nhiều hơn anh Dino đúng ~K~ cái kẹo.

Yêu cầu: Hãy giúp mẹ tính số kẹo chia cho anh Dino.

Dữ liệu nhập vào từ bàn phím

• Gồm một dòng duy nhất chứa một số tự nhiên ~K~ (~K \le 10^9~).

Kết quả ghi ra màn hình

• In ra một số nguyên duy nhất là số kẹo của anh Dino.
• Nếu không có cách chia nào thoả mãn yêu cầu đề bài, thì in ra ~0~.

Ví dụ

Ví dụ 1:

Input

24

Output

1000

Giải thích: Số kẹo của anh Dino là ~1000~ và em Daisy là ~1024~. (Tổng số kẹo: ~1000 + 1024 = 2024~. Daisy nhiều hơn Dino: ~1024 - 1000 = 24~).

Ví dụ 2:

Input

2023

Output

0

Giải thích: Không có cách chia nào thoả mãn đồng thời các điều kiện tổng bằng ~2024~, hiệu bằng ~2023~ và cả hai anh em đều có kẹo. Do đó kết quả là ~0~.

Cho dãy số tự nhiên từ ~1~ đến ~N~: ~1, 2, 3, ..., N - 1, N~.

Quy tắc lấy các số từ dãy để tính tổng như sau: Lần lượt lấy số ở tận cùng bên trái của dãy, sau đó lấy số ở tận cùng bên phải của dãy, tiếp tục quay lại lấy số tận cùng bên trái, rồi lại tận cùng bên phải... Cứ liên tục cộng dồn các số được lấy theo quy tắc đó, cho đến khi tổng nhận được lớn hơn ~K~ thì dừng lại.

Yêu cầu: Hãy đếm xem bạn đã lấy ra bao nhiêu số để tổng đạt được lớn hơn ~K~?

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên chứa một số tự nhiên ~N~ (~N \le 10^9~).
• Dòng thứ hai chứa một số tự nhiên ~K~ (~K \le 10^{18}~).

Kết quả ghi ra màn hình

• In ra một số nguyên duy nhất là số lượng số đã được lấy ra để tính tổng.
• Lưu ý: Nếu tổng của cả dãy (đã lấy hết số) mà vẫn không lớn hơn ~K~ thì in ra ~0~.

Ví dụ

Ví dụ 1:

Input

6
15

Output

5

Giải thích: Dãy số ban đầu là: ~1, 2, 3, 4, 5, 6~. Các số lần lượt được lấy ra từ hai đầu là: ~1, 6, 2, 5, 3~. Tổng tính được là: ~1 + 6 + 2 + 5 + 3 = 17~. Vì ~17 > 15~ nên ta dừng lại. Tổng cộng đã lấy ra 5 số.

Ví dụ 2:

Input

3
10

Output

0

Giải thích: Dãy số ban đầu là: ~1, 2, 3~. Các số lần lượt được lấy ra là ~1, 3, 2~. Tổng của tất cả các số trong dãy là ~1 + 3 + 2 = 6~. Vì lấy hết cả dãy mà tổng ~6~ vẫn không lớn hơn ~10~, nên theo yêu cầu đề bài ta in ra 0.

Ràng buộc:

• Có 80% số test tương ứng với 80% số điểm thỏa mãn: ~N \le 1000~.
• 20% số test còn lại tương ứng với 20% số điểm không có ràng buộc gì thêm.

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, ..., A_N~. Một số được gọi là số đơn lẻ nếu nó chỉ xuất hiện đúng một lần trong dãy số đó.

Yêu cầu: Tính tổng các số đơn lẻ trong dãy số ~A~.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên gồm một số nguyên dương ~N~ (~N \le 10^5~) là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ mô tả dãy ~A~ (~|A_i| \le 10^9~ với ~1 \le i \le N~).

Kết quả ghi ra màn hình

• In ra một số nguyên duy nhất là tổng của các số đơn lẻ có trong dãy ~A~.

Ví dụ

Input

4
10 30 20 30

Output

30

Giải thích: Dãy số ban đầu là: ~10, 30, 20, 30~. Trong dãy này, số ~30~ bị lặp lại (xuất hiện 2 lần). Các số chỉ xuất hiện 1 lần (số đơn lẻ) là số ~10~ và số ~20~. Tổng các số thỏa mãn yêu cầu là: ~10 + 20 = 30~.

Ràng buộc:

• Có 60% số test tương ứng với 60% số điểm của bài thoả mãn: ~N \le 10^3~ và ~|A_i| \le 10^3~.
• 40% số test còn lại tương ứng với 40% số điểm của bài không có ràng buộc gì thêm.

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1,A_2,…,A_N~. In ra độ dài của dãy con liên tiếp đan dấu dài nhất. (Đan dấu là không có hai phần tử nào cạnh nhau mà có cùng dấu)

Input:

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N≤10^5)~ là số lượng phần tử của dãy ~A~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_1,A_2,…,A_N~ mô tả dãy ~A~ ~(0<|A_i|≤10^9)~.

Output:

Ghi ra một số nguyên duy nhất là độ dài của dãy con liên tiếp đan dấu dài nhất.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm có ~N≤10^3~;
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không có ràng buộc gì thêm.

Sample Test 1

Input:

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

Output

6

Giải thích

Dãy đan dấu: 3 -1 3 -2 4 -5

Sample Test 2

Input:

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

Output

7

Giải thích

Dãy đan dấu 3 -1 3 -2 4 -5 6

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, \dots, A_N~. Vị trí ~i~ (~1 \leq i < N~) được gọi là vị trí cân bằng của dãy khi ~H = |(A_1 + A_2 + \dots + A_i) - (A_{i + 1} + \dots + A_N)|~ đạt giá trị bé nhất.

Hãy tìm giá trị ~H~ bé nhất thỏa mãn.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq n \leq 2 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên dương ~A_1, A_2, A_3, \ldots, A_n~ (~A_i \leq 10^9~).

Output

• In ra một số nguyên duy nhất là kết quả bài toán.

Sample Tests

Note

• Có thể chọn vị trí cân bằng ~i = 3~, khi đó ~H = |(1 + 1 + 3) - (6 + 2)| = 3~.

Cho một dãy số nguyên ~A~ gồm ~N~ phần tử ~A_1, A_2, ..., A_N~. Đoạn con từ vị trí ~L~ đến vị trí ~R~ của dãy số là dãy số ~A_L, A_{L+1}, ..., A_R~ (~1 \le L \le R \le N~).

Yêu cầu: Tìm đoạn con liên tiếp của dãy số ~A~ có tổng giá trị các phần tử là lớn nhất.

Dữ liệu nhập vào từ bàn phím

• Dòng đầu tiên gồm số nguyên dương ~N~ (~N \le 10^6~).
• Dòng thứ hai gồm ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~|A_i| \le 10^9~, ~1 \le i \le N~).

Kết quả ghi ra màn hình

• Ghi ra một số nguyên duy nhất là tổng của đoạn con thoả mãn.

Ví dụ

Input

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

Output

7

Giải thích: Đoạn con liên tiếp có tổng lớn nhất là: ~4, -1, -2, 1, 5~. Tổng của đoạn con này là: ~4 + (-1) + (-2) + 1 + 5 = 7~.

Ràng buộc:

• Có 20% số test tương ứng với 20% số điểm có ~N = 3~;
• 20% số test khác tương ứng với 20% số điểm có ~N \le 100~;
• 30% số test khác tương ứng với 30% số điểm có ~N \le 10^3~;
• 30% số test còn lại tương ứng với 30% số điểm không có ràng buộc gì thêm.

Cho một chuỗi kí tự gồm các kí tự chữ viết hoa, có bao nhiêu cách chọn ra bộ kí tự AMS khác nhau. Các kí tự được chọn phải để theo thứ tự trước sau như ban đầu.

Ví dụ, với câu CHAO AMS có ~2~ bộ kí tự AMS, tính theo vị trí là ~(3, 7, 8)~ và ~(6, 7, 8)~.

Input

Nhập vào một xâu văn bản ~S~ có tối đa ~10^6~ kí tự. Các kí tự đều là chữ in hoa.

Output

Ghi ra số cách chọn bộ kí tự AMS.

Ví dụ

Input

CHAO AMS

Output

2

Input

AMSER IN AMS

Output

4

Sau thành công từ quán cà phê nổi tiếng của mình, TDZ quyết định tự thưởng cho bản thân.

Ở cửa hàng có trưng bày ~n~ món hàng, món thứ ~i~ có giá ~v_i~. Với tổng số tiền ~x~ trong tay, TDZ muốn mua 2 món quà khác nhau có tổng giá trị lớn nhất và tất nhiên không vượt quá khả năng chi trả của mình. TDZ đang loay hoay không biết phải chọn món nào, bạn hãy giúp TDZ nhé.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ và ~x~ lần lượt là số món hàng và số tiền TDZ sở hữu (~2 \leq n \leq 10^5, x \leq 10^9~).
• Dòng tiếp theo chứa ~n~ số nguyên dương ~v_1, v_2, v_3, \ldots, v_n~ tương ứng với giá tiền từng món hàng (~v_i \leq 10^9~).

Output

In ra số tiền cần trả, hoặc 0 nếu TDZ không thể chọn được ~2~ món thoả mãn.

Subtasks

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

Sample Test

Input:

6 18
5 3 10 2 4 9

Output:

15

Note: Ở ví dụ trên TDZ sẽ chọn món thứ nhất và thứ ba. Tổng số tiền cần chi sẽ là ~5 + 10 = 15~.

Cho một bảng ô vuông gồm ~n~ hàng và ~n~ cột. Các hàng được đánh số từ ~1~ đến ~n~, các cột được đánh số từ ~1~ đến ~n~. Ô ở hàng thứ ~i~ và cột thứ ~j~ có giá trị là ~i \times j~ ~(1 \le i \le n, \ 1 \le j \le n)~.

Yêu cầu: Cho một số nguyên dương ~x~. Hãy đếm số lượng ô trong bảng có giá trị bằng ~x~.

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

Gồm hai số nguyên ~n~ và ~x~ ~(1 \le n \le 10^6, \ 1 \le x \le 10^{12})~ là kích thước của bảng và số nguyên ta cần tìm trong bảng.

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

Số nguyên duy nhất là số lượng ô trong bảng có giá trị bằng ~x~.

Ràng buộc

• Có ~70\%~ số test ứng với ~70\%~ số điểm của bài thoả mãn ~0 \lt n \le 10^3, \ 1 \le x \le 10^6;~
• ~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

6 5

Output

2

Input

6 12

Output

4

Input

5 13

Output

0

Giải thích

Mít có các que tính có nhiều độ dài và màu sắc. Hôm nay học về hình tam giác nhọn, Mít đã nghĩ ra một bài toán rất độc đáo có liên quan tới tam giác nhọn và các que tính của mình. Mít chia các que tính thành ~N~ bộ, các que tính trong cùng một bộ thì có độ dài bằng nhau nhưng có màu khác nhau. Độ dài của các que tính trong hai bộ bất kì là khác nhau. Mít đố các bạn đếm xem có bao nhiêu tam giác nhọn khác nhau có thể được tạo ra từ ~N~ bộ que tính đó. Chú ý: mỗi cạnh của tam giác được chọn từ một bộ que tính khác nhau tức là sẽ không có tam giác cân và hai tam giác nhọn được gọi là giống nhau khi các cặp cạnh tương ứng bằng nhau và cùng màu, ngược lại là khác nhau.

Yêu cầu: Cho độ dài và số lượng các que tính của ~N~ bộ que tính, hãy lập trình đếm số lượng tam giác nhọn khác nhau có thể tạo ra.

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

• Dòng đầu tiên gồm một số nguyên dương ~N~ ~(N ≤ 2000)~ là số bộ que tính;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~L, C~ mô tả độ dài và số lượng que tính của bộ thứ ~i~ ~(1 ≤ i ≤ N~; ~\ L ≤ 10^6~; ~\ C ≤ 10^3)~.

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

Một số nguyên duy nhất là số lượng tam giác nhọn khác nhau.

Ràng buộc

• Có ~50\%~ số test ứng với ~N ≤ 200~;
• ~50\%~ số test còn lại không có điều kiện gì thêm.

Ví dụ

Input

4
3 3
4 1
5 2
6 2

Output

4

Giải thích

Có ~4~ tam giác nhọn có thể tạo ra từ bộ que tính thứ ~2, 3, 4~.

Cho dãy số nguyên ~A~ gồm ~N~ phần tử ~A_{1}, A_{2}, \ldots, A_{N}~ và một số nguyên ~K~.

Yêu cầu: Đếm số cặp số ~L, R~ ~(1 \leq L \leq R \leq N)~ sao cho dãy con liên tiếp ~A_{L}, A_{L + 1}, \ldots, A_{R}~ có hiệu giữa số lớn nhất và số nhỏ nhất không vượt quá ~K~.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~N, K~ ~(N \leq 10^{5}, K \leq 10^{18})~
• Dòng thứ hai gồm ~N~ số nguyên dương ~A_{1}, A_{2}, \ldots, A_{N}~ ~(|A_{i}| \leq 10^{9})~.

Outputs

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

Scoring

• Subtask ~1~ (~50\%~ số điểm): ~N \leq 100~.
• Subtask ~2~ (~20\%~ số điểm): ~N \leq 5000~.
• Subtask ~3~ (~30\%~ số điểm): không có ràng buộc gì thêm.

Sample Test

Input

5 2
2 -1 3 1 3

Output

8

Cho dãy ~a~ gồm ~n~ phần tử và một số nguyên dương ~k~. Hãy tìm đoạn ~a[l..r]~ có độ dài tối thiểu là ~k~ sao cho ~med(l, r)~ đạt giá trị lớn nhất.

Biết rằng: ~med(l, r)~ là phần tử trung vị sau khi sắp xếp đoạn ~a[l..r]~ theo thứ tự không giảm, phần tử trung vị của một dãy có độ dài ~n~ là phần tử ở vị trí thứ ~\lfloor \frac{n+1}{2} \rfloor~ của dãy đó.

Ví dụ: Với ~A = \{3, 1, 4, 1, 5, 1, 2, 1, 2\}~, ~med(1, 5) = 3; \ med(6, 9) = 1~.

Input

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

Output

In ra một số nguyên là giá trị lớn nhất của ~med(l, r)~ thoả mãn đề bài.

Sample Test

Input

4 2
1 3 4 2

Output

3

Chọn ~l=2, r=4~. Khi đó, ~med(2, 4) = 3~.

Cho một dãy ngoặc ~s~ là một dãy ngoặc đúng, 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 ~i~ có dạng: ~l_i, r_i~, nhiệm vụ của bạn là kiểm tra xem dãy ~[l_i, r_i]~ có tạo thành một dãy ngoặc đúng hay không. Nếu ~[l_i, r_i]~ tạo thành một dãy ngoặc đúng, in ra YES, ngược lại in ra NO.

Dãy ngoặc là một dãy chỉ gồm các kí tự ( hoặ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ụ: (()), ()()(), ()(()) là các dãy ngoặc đúng, còn (, ), ()(((() 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 một số nguyên dương ~q~ miêu tả số truy vấn.
• ~q~ dòng sau, dòng thứ ~i~ gồm hai số nguyên dương ~l_i, r_i~ miêu tả dãy ngoặc con cần kiểm tra.

Constraints

• ~|s| \leq 10^6, \ q \leq 10^5~
• ~1 \leq l_i, r_i \leq |s|, \ \forall i = 1 ... q~

Subtask

• Subtask ~1~ ~(10 \%)~: ~r_i - l_i = 1~, tức dãy ~[l_i, r_i]~ chỉ gồm 2 kí tự.
• Subtask ~2~ ~(40 \%)~: ~|s|, q \leq 1000~.
• Subtask ~3~ ~(25 \%)~: ~|s|, q \leq 10^5~.
• Subtask ~4~ ~(25 \%)~: Không có giới hạn gì thêm.

Examples

Input

()()()
2
1 5
1 2

Output

NO
YES

Input

()()()(())
4
5 8
5 10
1 6
2 8

Output

NO
YES
YES
NO

Khôi có một dãy ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một dãy con ~a_l, a_{l + 1}, \dots, a_{r}~ được gọi là pro nếu

• ~a_i + 1 = a_{i + 1},\ \forall l \le i \lt r~.

Ví dụ ~a = [1, 3, 4, 5, 2]~, thì dãy con ~[3, 4, 5]~ là dãy pro, dãy con ~[3]~ là dãy pro, nhưng dãy ~[3, 4, 5, 2]~ thì không. Chú ý dãy con có một phần tử cũng được gọi là pro.

Khôi định nghĩa độ pro của dãy ~a~ là dãy con dài nhất của ~a~ mà là dãy pro. Trong ví dụ trên, độ pro của dãy ~a = [1, 3, 4, 5, 2]~ là ~3~.

Để làm cho dãy số của mình trở nên pro nhất có thể, Khôi sẽ thực hiện tối đa ~k~ lần chỉnh sửa, mỗi lần chọn một vị trí ~i~, và tăng hoặc giảm ~a_i~ đi ~1~ đơn vị. Trong tất cả các cách chỉnh sửa có thể, Khôi muốn chọn ra cách có độ pro lớn nhất. Vì Khôi khá ga` nên hãy giúp Khôi tìm ra độ pro có thể này nhé!

Input (vào từ file văn bản proseq.inp)

• Dòng đầu chứa hai số nguyên ~n, k~ ~(1 \le n \le 5 \times 10^5,\ 0 \le k \le 10^{15})~.
• Dòng sau chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(|a_i| \le 10^9)~.

Output (ghi ra file văn bản proseq.out)

• In ra một sô nguyên duy nhất là độ pro lớn nhất có thể sau khi thực hiện tối đa ~k~ lần chỉnh sửa.

Subtasks

• Subtask 1 (~20\%~ số điểm): ~k = 0~.
• Subtask 2 (~20\%~ số điểm): ~n \le 500~.
• Subtask 3 (~30\%~ số điểm): ~n \le 5000~
• Subtask 4 (~30\%~ số điểm): Không có điều kiện gì thêm.

Sample Input 1

5 0
1 3 4 2 5

Sample Output 1

2

Notes: Ta không thể thực hiện bước chỉnh sửa nào, nên dãy ~a~ giữ nguyên và có độ pro là ~2~.

Sample Input 2

6 5
2 0 3 3 6 8

Sample Output 2

5

Notes: Ta có thể biến dãy ~a~ về ~[1, 2, 3, 4, 5, 8]~ và có độ pro là ~5~.