Cho số nguyên dương \(n\), đếm số cách để chia \(n\) chiếc kẹo thành các phần bằng nhau (mà không phá vỡ hay làm hỏng chiếc kẹo nào).

Input

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

Output

In ra số cách chia \(n\) chiếc kẹo thành các phần bằng nhau.

Sample Test

Input:

10

4

Các cách chia thoả mãn là:

• Chia thành \(1\) phần, mỗi phần \(10\) chiếc kẹo.
• Chia thành \(2\) phần, mỗi phần \(5\) chiếc kẹo.
• Chia thành \(5\) phần, mỗi phần \(2\) chiếc kẹo.
• Chia thành \(10\) phần, mỗi phần \(1\) chiếc kẹo.

Cho một mảng \(a\) gồm \(n\) phần tử nguyên dương. Nhiệm vụ của bạn là tìm cặp chỉ số \((i, j)\) với \(1 \le i < j \le n\) sao cho hiệu \(a_j - a_i\) đạt giá trị lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(1 < n \le 5000\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, \dots, a_n\) ( \(a_i \le 10^{9}\)).

Output

• In ra giá trị lớn nhất của \(a_j - a_i\) với \(1 \le i < j \le n\).

Examples

5
2 1 5 3 7

6

Trong ngày thực tập đầu tiên, thầy Hải có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\) , hãy kiểm tra \(n\) có phải là số
nguyên tố hay không?
Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

• Gồm một dòng duy nhất là số nguyên \(n\) ( \(|n| \le 10^{12})\)

Output:

• In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO .

Sample Tests

Input

9

Output

NO

Input

7

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,..,a_N\) và số nguyên dương \(K\). Chọn ra \(K\) phần tử liên tiếp sao cho tổng của chúng là lớn nhất. In ra giá trị đó

Input

• Dòng 1: hai số nguyên dương \(N\) và \(K\) \((K \le N \le 10^5)\);
• Dòng 2: gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

• In ra đáp án thỏa mãn yêu cầu đề bài.

Example

6 2
2 4 5 2 9 1 

11

Trong Liên minh huyền thoại có \(N\) vị tướng, vị tướng thứ \(i\) có \(2\) sát thương vật lý và sát thương phép.

Vị tướng thứ \(i\) được cho là mạnh hơn vị tướng thứ \(j\) nếu có sát thương vật lý mạnh hơn.

Hai vị tướng có cùng sát thương vật lý thì vị tướng mạnh hơn sẽ có sát thương phép lớn hơn.

Hãy cho biết chỉ số sát thương vật lý và phép của vị tướng mạnh thứ \(m\).

Input

• Dòng đầu chứa số \(n, m (1 \leq m \leq n \leq 10000)\)
• \(n\) dòng, mỗi dòng chứa 2 số nguyên \(A_i(\)vật lý\(),B_i(\)phép\() (0 \leq A_i,B_i \leq 10000)\).

Output

• Chỉ số sát thương

Example

3  2
1  2
3  2
1  3   

1  3

Cho số nguyên \(n\). Hãy phân tích \(n\) thành tích các thừa số nguyên tố.

Ví dụ: \(n=36 \rightarrow n=2\times2\times3\times3\). Khi đó có \(2\) thừa số \(2\) và \(2\) thừa số \(3\).

Input

• Vào từ thiết bị nhập chuẩn gồm dòng duy nhất chứa một số nguyên dương \(n\) \((n\le{10}^{14})\).

Output

• Ghi ra thiết bị xuất chuẩn gồm các ước nguyên tố xếp từ nhỏ đến lớn của \(n\) cùng số lần xuất hiện trong cách phân tích đó.

Example

16

2 4

25

5 2

36

2 2
3 2

Vương quốc Linear có đúng một tuyến tàu điện. Tuyến này có \(n\) điểm dừng. Tại điểm dừng thứ \(i\) có \(a_i\) hành khách xuống tàu, và có \(b_i\) hành khách lên tàu. Ban đầu (trước điểm dừng đầu tiên) xe điện không có hành khách. Ngoài ra, khi đến điểm dừng cuối cùng, tất cả hành khách có trên tàu sẽ xuống tàu.

Yêu cầu: Nhiệm vụ của bạn là tính toán sức chứa tối thiểu của tàu điện, sao cho số người bên trong tàu tại bất kì thời điểm nào đều không vượt quá sức chứa này. Lưu ý rằng tại mỗi điểm dừng, các hành khách xuống tàu trước, sau đó các hành khách khác mới được lên tàu.

Input

• Dòng đầu tiên là số nguyên \(n\) - số điểm dừng của tuyến tàu điện.
• Trong \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a_i\) và \(b_i\). Số lượng khách xuống tàu không lớn hơn số lượng khách hiện có trên tàu. Số khách trên tàu sau điểm dừng thứ \(n\) luôn đảm bảo bằng \(0\).

Output

• Gồm một số nguyên là sức chứa tối thiểu của tàu điện.

Constraints

• \(2\leq n\leq 1000\)
• \(0\leq a_i ,b_i\leq 1000\)

Example

4
0 60
56 79
54 77
106 0 

106

Một ngày nọ, Dima và Alex có một cuộc tranh cãi về giá cả và chất lượng của máy tính xách tay. Dima cho rằng máy tính xách tay càng đắt tiền thì càng tốt. Alex không đồng ý. Alex cho rằng có hai máy tính xách tay, như vậy giá của máy tính xách tay đầu tiên thấp hơn (nhỏ hơn) so với giá của máy tính xách tay thứ hai nhưng chất lượng của máy tính xách tay thứ nhất cao hơn (lớn hơn) so với chất lượng của máy tính xách tay thứ hai. Vui lòng kiểm tra phỏng đoán của Alex. Bạn được cung cấp mô tả của \(n\) máy tính xách tay. Xác định xem hai máy tính xách tay được mô tả ở trên có tồn tại không.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^{5})\) - số lượng máy tính xách tay.
• \(n\) dòng tiếp theo chứa hai số nguyên, dòng thứ \(i\) gồm \(2\) số \(a_{i}\) và \(b_{i}\) \((1 \leq a_{i}, b_{i} \leq n)\), trong đó \(a_{i}\) là giá của máy tính xách tay thứ \(i\) và \(b_{i}\) là số đại diện cho chất lượng của máy tính xách tay thứ \(i\) ( số lượng càng lớn thì chất lượng càng cao).

Output

• Gồm \(1\) dòng duy nhất, nếu Alex đúng, hãy in \(Happy Alex\), nếu không thì in \(Poor Alex\).

Example

2
1 2
2 1

Happy Alex

3
1 1
2 2
3 3

Poor Alex

Trường mầm non SuperKids dành ra hai phòng để trưng bày một số mô hình lego do học sinh tự lắp ghép. Có tất cả \(𝑛\) mô hình lego đánh số từ \(1\) tới \(n\). Mô hình thứ \(i\) có kích thước là \(a_i\).
.
Để có độ hài hòa, hai mô hình lego bất kỳ trong cùng một phòng trưng bày phải có kích thước chênh lệch nhau không quá \(k\). Hãy giúp ban tổ chức chọn ra một số tối đa các mô hình lego để đưa vào hai phòng trưng bày theo ràng buộc nêu trên.

Input

Từ tệp văn bản LEGOSHOW.INP gồm:

• Dòng \(1\) chứa hai số nguyên dương \(𝑛 ≤ 10^5\); \(𝑘 ≤ 10^9\).
• Dòng \(2\) chứa \(𝑛\) số nguyên dương \(𝑎_1, 𝑎_2, … , 𝑎_𝑛\) (\(∀𝑖: 𝑎𝑖 ≤ 10^9\)).

Output

• Ghi ra file văn bản LEGOSHOW.OUT một số nguyên duy nhất là số mô hình lego được chọn để trưng bày theo phương án tìm được.

Ví dụ:

9 2
3 4 5 7 9 1 10 11 100

6

Cho một dãy số \(A\) có \(N\) phần tử. Tìm số nguyên dương \(P\) nhỏ nhất thỏa mãn: \(P\) là số chính phương và \(P\) chia hết cho tất cả các phần tử của dãy số \(A\).

Yêu cầu: In ra phần dư của phép chia khi chia \(P\) cho \(10^9+7\)

Input

• Dòng đầu tiên chứa số nguyên dương \(N\) là số lượng phần tử của dãy số.
• Dòng tiếp theo chứa \(N\) số nguyên dương \(a_i\) là các phần tử của dãy số \(A\) \((1 \le i \le N)\)

Các số trên một dòng được ghi cách nhau bởi dấu cách

Output

= Ghi ra thiết bị ra chuẩn gồm một số nguyên duy nhất là kết quả của bài toán.

Example

3
2 1 3

36

Scoring

• Subtask \(1\): Có \(30\%\) số test ứng với \(N \le 10\), \(a_i \le 10\)
• Subtask \(2\): Có \(30\%\) số test khác ứng với \(N \le 10^4\), \(a_i \le 10^5\)
• Subtask \(3\): Có \(40\%\) số test còn lại ứng với \(N \le 10^5\), \(a_i \le 10^7\)