Cho ba số ~a, b, c~. Hãy kiểm tra xem ba số có thể tạo thành một cấp số nhân hay không.

Input [MULSEQ.inp]

Gồm một dòng chứa ba số nguyên dương ~a, b, c~ (~a, b, c \leq 10^9~).

Output [MULSEQ.out]

In ra YES nếu ba số tạo được một cấp số nhân, ngược lại in ra NO.

Sample Test 1

Input:

1 9 3

Output:

YES

Note: ~[1, 3, 9]~ là một cấp số nhân công bội ~3~.

Sample Test 2:

Input:

3 9 81

Output:

NO

Cho một số nguyên dương ~n~. Hãy phân tích số ~n~ thành tổng của các số Fibonacci khác nhau.

Input

Gồm một số nguyên dương ~n~ duy nhất (~n \leq 10^9~).

Output

In ra các số Fibonacci trên một dòng, theo thứ tự bất kì và cách nhau một khoảng trắng, sao cho tổng các số đó bằng ~n~. Nếu có nhiều cách phân tích thoả mãn thì in ra cách nào cũng được.

Sample Test 1

Input:

5

Output:

2 3

Note: Có thể phân tích ~5~ thành chính số ~5~ hoặc ~2 + 3~.

Sample Test 2

Input:

16

Output:

5 3 8

Note: Có nhiều cách phân tích thoả mãn, ví dụ như ~16 = 13 + 3~ và ~16 = 8 + 5 + 2 + 1~.

Cho ~n~ điểm trên mặt phẳng Descartes, điểm ~A_i~ có toạ độ ~(x_i, y_i)~. Hãy tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong ~n~ điểm đã cho.

Khoảng cách Manhattan giữa hai điểm ~A(x_A, y_A)~ và ~B(x_B, y_B)~ có giá trị là ~|x_A - x_B| + |y_A - y_B|~.

Input [DISTANCE.inp]

• Dòng đầu tiên chứa số nguyên dương ~n~ - số lượng điểm (~2 \leq n \leq 10^3~).
• ~n~ dòng tiếp theo, một dòng chứa hai số nguyên ~x_i~ và ~y_i~ mô tả toạ độ của điểm ~A_i~ (~|x_i|, |y_i| \leq 10^9~).

Output [DISTANCE.out]

In ra khoảng cách Manhattan lớn nhất tìm được.

Sample Test

Input:

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

Output:

9

Note: Khoảng cách giữa điểm ~A_3~ và ~A_4~ bằng ~9~ là khoảng cách lớn nhất.

Đây là phiên bản khó hơn của bài PA094. Điểm khác biệt duy nhất giữa hai bài là giới hạn của ~n~ và đầu vào/ra dữ liệu.

Cho ~n~ điểm trên mặt phẳng Descartes, điểm ~A_i~ có toạ độ ~(x_i, y_i)~. Hãy tìm khoảng cách Manhattan lớn nhất giữa hai điểm bất kỳ trong ~n~ điểm đã cho.

Khoảng cách Manhattan giữa hai điểm ~A(x_A, y_A)~ và ~B(x_B, y_B)~ có giá trị là ~|x_A - x_B| + |y_A - y_B|~.

Input

• Dòng đầu tiên chứa số nguyên dương ~n~ - số lượng điểm (~2 \leq n \leq 10^5~).
• ~n~ dòng tiếp theo, một dòng chứa hai số nguyên ~x_i~ và ~y_i~ mô tả toạ độ của điểm ~A_i~ (~|x_i|, |y_i| \leq 10^9~).

Output

In ra khoảng cách Manhattan lớn nhất tìm được.

Sample Test

Input:

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

Output:

9

Note: Khoảng cách giữa điểm ~A_3~ và ~A_4~ bằng ~9~ là khoảng cách lớn nhất.

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 nhập vào từ file văn bản DKT.INP:

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ả ghi ra file văn bản DKT.OUT:

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

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

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

Ibuki Suika rất thích uống rượu nhưng uống rượu không thì rất chán nên cô đi mua xiên que về ăn. Có ~n~ cửa hàng bán thịt xếp theo thứ tự từ trái sang phải và cửa hàng thứ ~i~ bán một miếng thịt loại ~a_i~. Cô muốn xiên của mình có ~m~ miếng thịt. Đến một cửa hàng cô hoặc là không mua cửa hàng đó hoặc mua miếng thịt và xiên vào que theo thứ tự. Hỏi có tất cả bao nhiêu cách xiên thịt khác nhau.

Input:

• Dòng đầu tiên là hai số tự nhiên ~n~ và ~m~.
• Dòng tiếp theo gồm ~n~ số lần lượt là loại thịt các cửa hàng bán.

Output:

• In ra một số nguyên duy nhất là số cách xiên thịt khác nhau modulo ~10^9+7~

Sample Test 1

Input:

3 2
1 2 3

Output:

3

Sample Test 2

Input:

4 3
2 3 3 2

Output:

3

Giải thích:

• Ở test 1 có 3 xiên là ~\{1, 2\}, \{1, 3\}, \{2, 3\}~
• Ở test 2 có 3 xiên là ~\{2, 3, 2\}, \{2, 3, 3\}, \{3, 3, 2\}~

Ràng buộc

• ~n, m \le 1000, a_i \le 10^9~

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