Cho trước số nguyên dương ~n~

Yêu cầu: Tìm số nguyên dương ~x~ nhỏ nhất sao cho tổng các chữ số của ~x~ bằng tổng các chữ số của ~n~.

INPUT

Số nguyên dương ~n~ có giá trị không vượt quá ~10^9~

OUTPUT

Giá trị ~x~ tìm được

SAMPLE INPUT

2019

SAMPLE OUTPUT

39

Giải thích: 39 là số nguyên dương nhỏ nhất có tổng các chữ số bằng 12.

Cho số nguyên dương ~n~ và ~n~ số nguyên dương ~a_1, a_2, ..., a_n~.

Tìm vị trí ~k~ sao cho chênh lệnh giữa tổng từ ~a_1~ đến ~a_k~ và tổng từ ~a_{k+1}~ đến ~a_n~ là nhỏ nhất ~(1 \le k < n)~.

Input

Dòng 1: Số nguyên dương ~n~ ~(n \le 10^5)~

Dòng 2: ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ (~a_i<=10^9~)

Output

Ghi ra 2 số nguyên là chênh lệnh nhỏ nhất và vị trí ~k~. Nếu có nhiều vị trí ~k~ thỏa mãn thì chọn ~k~ nhỏ nhất.

Sample

Input

4
1 2 3 5

Output

1 3

Cho 3 số nguyên dương ~n~, ~m~ và ~p~, có giá trị không vượt quá ~10^9~

Yêu cầu: Hãy tìm số nguyên ~x~ lớn nhất thoả mãn các điều kiện sau:

• ~x \le n~
• ~x = k * m + p~, với ~k~ là số nguyên

INPUT

Gồm 3 số nguyên dương ~n~, ~m~ và ~p~

OUTPUT

Số ~x~ thoả mãn đề bài

SAMPLE INPUT

60 5 9

SAMPLE OUTPUT

59

Giải thích: ~59 = 10 * 5 + 9~

Cho trước số nguyên dương ~n~. Hai số nguyên dương ~x~ và ~y~ gọi là căp số đặc biệt nếu thỏa mãn điều kiện ~x^2~ ~–~ ~y^2~ ~ = n~.

Yêu cầu: Tìm số lượng các cặp số đặc biệt với ~n~ đã cho

INPUT

Số nguyên dương ~n~ (~n \le 10^9~)

OUTPUT

Số lượng các cặp số đặc biệt tìm được

SAMPLE INPUT

3

SAMPLE OUTPUT

1

Giải thích: Có ~1~ cặp số đặc biệt ~x = 2~, ~y = 1~ thỏa mãn ~x^2~ ~–~ ~y^2 = 3~.

Cho hai số nguyên dương ~a~ và ~b~, có giá trị không vượt quá ~10^9~

Yêu cầu: Tìm số cặp số nguyên dương ~(x, y)~ thoả mãn ~gcd(a, b) = gcd(x, y)~ và ~lcm(a, b) = lcm(x, y)~.

INPUT

Hai số nguyên dương ~a~ và ~b~

OUTPUT

Số cặp số nguyên dương ~(x, y)~ thoả mãn đề bài

SAMPLE INPUT

6 8

SAMPLE OUTPUT

4

Giải thích: Có ~4~ cặp ~(x, y)~ thoả mãn đề bài là các cặp: ~(6, 8)~, ~(8, 6)~, ~(2, 24)~, ~(24, 2)~

Cho trước ba số nguyên dương ~k, m~ và ~x~

Yêu cầu: Tìm số dư của phép chia ~x^k~ cho ~m~

INPUT

Ba số nguyên dương ~k, m~ và ~x~, mỗi số không vượt quá ~10^9~

OUTPUT

Số dư tìm được.

SAMPLE INPUT

5 7 4

SAMPLE OUTPUT

2

Giải thích: ~4^5~ khi chia cho ~7~ có số dư là ~2~

Cho bốn số nguyên dương ~a, b, c, d~, ~(1 \le a \le b \le 10^9), (4 \le c \le d \le 10^9)~.

Đếm các cặp số nguyên dương ~(x, y)~ sao cho ~x \le y, a \le x \times y \le b, c \le 2 \times (x+y) \le d~.

Input

1 dòng chứa 4 số ~a, b, c, d~.

Output

1 số duy nhất là kết quả bài toán.

Examples

Input

2 10 4 8

Output

3

Cho một dãy số gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ có giá trị không vượt quá ~10^6~. Tìm dãy con liên tiếp ngắn nhất có chứa ít nhất hai số nguyên tố.

Dữ liệu:

• Dòng đầu tiên gồm một số nguyên dương ~N \ (N \le 10^6)~ là số lượng phần tử của dãy số;
• Dòng thứ hai gồm ~N~ số nguyên dương ~a_1, a_2, ..., a_N~ lần lượt mô tả các phần tử của dãy số.

Kết quả:

Một số nguyên duy nhất là số lượng phần tử của dãy con thoả mãn đề bài. Trường hợp không tồn tại dãy con thoả mãn, in ra ~-1~.

Ví dụ

Input

10
3 4 8 4 5 6 1 7 4 6

Output

4

Giải thích

Chọn dãy con từ vị trí thứ ~5~ đến vị trí thứ ~8~: ~5, 6, 1, 7~.

Ràng buộc

• Có ~50\%~ số test ứng với ~50\%~ số điểm của bài thoả mãn: ~N \le 10^3; \ a_i \le 10^3~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 10^6; \ a_i \le 10^3~;
• ~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.

Trong phòng thí nghiệm chỉ có đúng ba loại cốc có dung tích là ~5 \ (ml)~, ~3 \ (ml)~ và ~2 \ (ml)~. Hỏi cần ít nhất bao nhiêu lần đong nước để lấy được đúng ~N \ (ml)~.

Dữ liệu:

Một số nguyên dương duy nhất ~N~ ~(2 \le N \le 10^{18})~ là số nước cần đong.

Kết quả:

Một số nguyên dương duy nhất là số lượng lần đong ít nhất thoả mãn yêu cầu đề bài.

Ví dụ

Input

12

Output

3

Giải thích

Đong hai lần bằng cốc ~5 \ (ml)~ và một lần bằng cốc ~2 \ (ml)~.

Input

6

Output

2

Giải thích

Đong hai lần bằng cốc ~3 \ (ml)~.

Cho hai điểm ~A~, ~B~ trên trục Ox có toạ độ nguyên. Tìm hai điểm ~X~, ~Y~ có toạ độ nguyên trên trục Ox sao cho hai điểm này chia đoạn thằng ~AB~ thành ba phần có độ dài bằng nhau. Nếu không tồn tại hai điểm như trên, in ra ~-1~.

Input

Gồm một dòng duy nhất chứa hai số nguyên ~a~, ~b~ (~1 \le a < b \le 10^9~) lần lượt mô tả toạ độ của điểm ~A~ và toạ độ của điểm ~B~.

Output

Nếu tồn tại hai điểm ~X~, ~Y~ như trên, in ra hai số nguyên ~x~, ~y~ (~x \le y~) lần lượt là toạ độ của hai điểm ~X~, ~Y~ tìm được, ngược lại in ra ~-1~.

Example

Input 1

1 4

Output 1

2 3

Input 2

2 6

Output 2

-1

Cho ~2~ số nguyên ~A~ và ~B~. Tìm số nguyên ~M~ nằm giữa ~A~ và ~B~ sao cho khoảng cách giữa ~A \times M~ và ~B \times M~ là nhỏ nhất. ~M~ phải khác ~A~ và ~B~

Input

• Gồm 1 dòng duy nhất chứa hai số nguyên ~A~ và ~B~ ~(-10^{9} \leq A \leq B \leq 10^{9})~
• Dữ liệu đảm bảo ~A \le B-2~

Output

• Gồm 1 dòng duy nhất chứa số nguyên ~M~ cần tìm.

Example

Sample input 1

1 3

Sample output 1

2

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^6;~
• ~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

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

Chuẩn bị Gala mừng năm mới Tết Tân Sửu 2021 của công ty HiTech, ban giám đốc quyết định có giải thưởng đặc biệt cho thành viên của công ty. Sau khi đưa ra các tiêu chí đánh giá, việc bầu chọn sẽ được thực hiện bằng cách tất cả các thành viên sẽ được bỏ phiếu cho nhau.

Hình thức bỏ phiếu được thực hiện thông qua phiếu bầu chọn online. Danh sách các thành viên của công ty được niêm yết và quy định là số thứ tự từ ~1~ đến ~N~ ~(1≤N≤5000),~ tương ứng với ~N~ ô trên phiếu bầu chọn. Sau khi thực hiện, ban tổ chức thu được các danh sách phiếu tương ứng của các thành viên công ty. Trong mỗi phiếu bầu chọn, giá trị ô ở vị trí tương ứng ghi ~'X'~ là bầu chọn cho người đó, ô ghi ~'0'~ là không bầu chọn (coi các trường hợp bầu chọn không hợp lệ là không bầu chọn).

Yêu cầu: Em hãy giúp ban tổ chức đưa ra danh sách các nhân viên có phiếu bầu chọn cao nhất.

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

• Dòng đầu tiên gồm số một số nguyên dương ~N~ ~(1≤N≤5000)~ là số lượng phiếu bầu chọn.
• ~N~ dòng tiếp theo mỗi dòng tương ứng là ~N~ giá trị của các phiếu đã bầu chọn.

Các kí tự cách nhau một dấu cách.

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

• Dòng đầu tiên ghi số lượng người được nhiều phiếu nhất và số lượng phiếu.
• Dòng thứ hai ghi thứ tự tương ứng của những người được cao phiếu nhất đó theo thứ tự tăng dần.

Ví dụ

Input

5
X 0 X 0 X
X 0 0 X X
0 0 X 0 0
0 X 0 X 0
0 0 X X 0

Output

2 3
3 4

Giải thích:

• Người số ~1~ được ~2~ phiếu bầu chọn.
• Người số ~2~ được ~1~ phiếu bầu chọn.
• Người số ~3~ được ~3~ phiếu bầu chọn.
• Người số ~4~ được ~3~ phiếu bầu chọn.
• Người số ~5~ được ~2~ phiếu bầu chọn.
• Người số ~3~ và số ~4~ cùng được số phiếu bầu chọn lớn nhất.

Giới hạn

• Có ~70\%~ số test tương ứng với số điểm có ~N \le 1000;~
• ~30\%~ số test còn lại tương ứng với số điểm có ~N \le 5000.~

Trên mặt phẳng toạ độ Oxy, bạn nhận được một hình vuông với cạnh song song với trục toạ độ, có góc trái dưới là ~(0, 0)~ và góc phải trên là ~(n, n)~. Hãy đếm xem có bao nhiêu điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Khoảng cách Manhattan giữa hai điểm ~(x, y)~ và ~(u, v)~ được tính bằng ~|x - u| + |y - v|~.

Input

Gồm một dòng duy nhất chứa bốn số nguyên ~n~, ~x_0~, ~y_0~, ~k~ (~1 \le n, k \le 10^{18}~; ~1 \le x_0, y_0 \le n~).

Output

In ra một số nguyên là số điểm toạ độ nguyên nằm trong hoặc nằm trên biên hình vuông mà có khoảng cách Manhattan đến ~(x_0, y_0)~ đúng bằng ~k~.

Scoring

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

Example

Input

4 1 1 2

Output

6

Bản đồ thành phố X có dạng lưới ô vuông ~M~ hàng ~N~ cột, các hàng được đánh số từ ~1~ tới ~M~, các cột được đánh số từ ~1~ tới ~N~. Mỗi ô vuông trên bản đồ có thể là khu đất trống hoặc một khu dân cư hoặc một siêu thị.

Mỗi siêu thị chỉ có thể phục vụ các khu dân cư có khoảng cách so với nó không quá ~D~, nghĩa là nếu siêu thị nằm ở ô ~(x, y)~ thì nó có thể phục vụ được tất cả các khu dân cư nằm trong hình vuông có ô trái trên là ~(x - D, y - D)~, ô phải dưới là ~(x + D, y + D)~ (như Hình 1).

Một khu dân cư gọi là "chất lượng cao" nếu được ít nhất ~K~ siêu thị có thể phục vụ nó. Cho biết bản đồ của thành phố X, hãy đếm số lượng khu dân cư "chất lượng cao".

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

• Dòng đầu chứa bốn số nguyên ~M, N, D~ và ~K~ ~(1\le D \le \max(M, N); \ 1\le K\le M \times N)~;
• ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự, mỗi ký tự biểu diễn một ô vuông bản đồ. Mỗi ký tự sẽ thuộc một trong ba loại sau:
  • . biểu diễn một khu đất trống;
  • P biểu diễn một khu dân cư;
  • M biểu diễn một siêu thị;

Dữ liệu đảm bảo tồn tại ít nhất một khu dân cư và ít nhất một siêu thị.

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

Ghi ra một số duy nhất là số khu dân cư "chất lượng cao".

Ví dụ

Input

5 5 1 2
P....
....P
..PM.
.M...
.....

Output

1

Giải thích

Bản đồ minh hoạ thành phố ~X~ như Hình 2.

Khu dân cư ở ô ~(1, 1)~ không được siêu thị nào phục vụ;

Khu dân cư ở ô ~(2, 5)~ được một siêu thị có thể phục vụ;

Khu dân cư ở ô ~(3, 3)~ được hai siêu thị có thể phục vụ;

Vậy có một khu dân cư "chất lượng cao".

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~M = 1; \ N, D \le 10^3~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~M = 1; \ N \le 10^5~;
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~2 \le M, N \le 1000;~ số khu dân cư, số siêu thị không vượt quá ~1000~;
• ~20\%~ số test còn lại ứng với ~20\%~ số điểm của bài thoả mãn: ~2 \le M, N \le 1000~.

An có một xâu ký tự ~S~ có độ dài ~N~, chỉ gồm các chữ cái Latin in thường. An muốn tìm một xâu con liên tiếp không rỗng của xâu ~S~ sao cho chênh lệch giữa số lần ký tự xuất hiện nhiều nhất và số lần ký tự xuất hiện ít nhất ở trong xâu con là lớn nhất. Lưu ý rằng, ký tự xuất hiện ít nhất phải xuất hiện ít nhất một lần trong xâu con.

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

• Dòng đầu tiên chứa số nguyên ~N~ ~(1\le N\le 10^6)~ là độ dài của xâu ~S~;
• Dòng thứ hai chứa xâu ~S~.

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

Một số nguyên duy nhất là chênh lệch lớn nhất của xâu con tìm được.

Ví dụ

Input

6
caabac

Output

2

Giải thích

Có thể chọn xâu con: aaba hoặc caaba hoặc aabac hoặc caabac.

Input

3
ttt

Output

0

Giải thích

Có thể chọn xâu con: ttt hoặc tt hoặc t.

Ràng buộc

• Có ~40\%~ số test ứng với ~40\%~ số điểm của bài thoả mãn: ~N \le 10^2~;
• ~30\%~ số test khác ứng với ~30\%~ số điểm của bài thoả mãn: ~N \le 10^5~;
• ~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.