Độ khó: Trung bình (2/4 điểm)

Một số nguyên được gọi là "đẹp" nếu nó thỏa mãn đồng thời hai điều kiện sau:

• Nó là một số nguyên tố.

• Tổng các chữ số của nó lớn hơn hoặc bằng một giá trị ~N~ cho trước.

Cho số nguyên dương ~N~, hãy tìm số "đẹp" nhỏ nhất.

Input

• Một dòng duy nhất chứa số nguyên dương ~N~ ~(1 \le N \le 63)~.

Output

• Ghi ra một số nguyên duy nhất là số "đẹp" nhỏ nhất tìm được.

Scoring

Sample Input 1

10

Sample Output 1

19

Sample Input 2

20

Sample Output 2

389

Notes

Ví dụ 1: Các số nguyên tố đầu tiên là: ~2, 3, 5, 7, 11, 13, 17, 19, \dots~ Số ~19~ có tổng chữ số là ~1 + 9 = 10 \ge 10~ là số nguyên tố nhỏ nhất thỏa mãn.

Ví dụ 2: Số ~389~ là số nguyên tố và có tổng các chữ số là ~3 + 8 + 9 = 20 \ge 20~. Đây là số nguyên tố nhỏ nhất thỏa mãn.

Độ khó: Dễ (1/4 điểm)

Cho số nguyên ~N~ có ~K~ chữ số. Gọi ~S~ là tổng lũy thừa bậc ~K~ của các chữ số trong ~N~. Ví dụ, ~N = 154~ có ~K = 3~ chữ số, ~S = 1^3 + 5^3 + 4^3 = 190~.

Nếu ~S = N~, hãy in ra EQUAL. Ngược lại, in ra giá trị ~|N - S|~.

Input

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

Output

In ra EQUAL hoặc kết quả của phép tính ~|N - S|~.

Scoring

Sample Input 1

154

Sample Output 1

36

Sample Input 2

153

Sample Output 2

EQUAL

Notes

~N = 154~ có ~K = 3~ chữ số. Ta có ~S = 1^3 + 5^3 + 4^3 = 190~. Kết quả in ra là ~|154 - 190| = 36~.

~N = 153~ có ~K = 3~ chữ số. Ta có ~S = 1^3 + 5^3 + 3^3 = 153~.

Độ khó: Khá (3/4 điểm)

Cho một mảng vòng tròn gồm ~N~ số nguyên không âm ~a_1, a_2, a_3, \dots, a_N~.

Ta có thể thực hiện thao tác sau một số lần tùy ý: Chọn hai phần tử kề nhau và cộng thêm vào cả hai phần tử cùng một lượng nguyên dương. Mục tiêu là làm cho tất cả các phần tử trong mảng có giá trị bằng nhau.

Trong trường hợp không thể làm các phần tử bằng nhau chỉ bằng thao tác cộng, ta bắt buộc phải giảm giá trị của một số phần tử ban đầu sao cho tổng lượng giảm là ít nhất để việc biến đổi sau đó trở nên khả thi.

Yêu cầu:

• Nếu không thể làm các phần tử bằng nhau chỉ bằng thao tác cộng, hãy tìm SMIN - tổng lượng giảm tối thiểu của các phần tử ban đầu.

• Nếu có giải pháp chỉ bằng thao tác cộng, hãy tìm AMIN - giá trị bằng nhau cuối cùng nhỏ nhất có thể đạt được.

Input

• Dòng đầu tiên chứa số nguyên ~N~ ~(1 \le N \le 10^5)~.

• Dòng thứ hai chứa ~N~ số nguyên ~a_1, a_2, \dots, a_N~ ~(0 \le a_k \le 10^6)~ cách nhau bởi khoảng trắng.

Output

• Ghi ra hai số nguyên cách nhau một khoảng trắng trên một dòng: Nếu có giải pháp chỉ bằng thao tác cộng, in ra ~1~ và theo sau là giá trị AMIN. Nếu không thể làm các phần tử bằng nhau chỉ bằng thao tác cộng, in ra ~0~ và theo sau là giá trị SMIN.

• Dữ liệu đảm bảo đáp án AMIN hoặc SMIN không vượt quá ~10^9~.

Scoring

Sample Input 1

4
1 2 4 3

Sample Output 1

1 4

Sample Input 2

2
1 3

Sample Output 2

0 2

Sample Input 3

5
5 2 1 3 4

Sample Output 3

1 5

Notes

Ví dụ 1: Giá trị bằng nhau nhỏ nhất đạt được là ~4~. Vì mảng có thể cân bằng chỉ bằng thao tác cộng, ta in ra ~1~ và theo sau là giá trị AMIN.

Ví dụ 2: Không thể làm hai phần tử bằng nhau chỉ bằng thao tác cộng. Bắt buộc phải giảm ~a_2~ đi ~2~ đơn vị (từ ~3~ xuống ~1~), lúc này mảng cân bằng ở giá trị ~1~. Tổng lượng giảm tối thiểu là ~2~. Vì phải sử dụng phép giảm, ta in ra ~0~ và theo sau là giá trị SMIN.

Ví dụ 3:

Có thể áp dụng các thao tác sau:

• Cộng ~1~ vào ~a_3~ và ~a_4~, mảng thành: ~5, 2, 2, 4, 4~.

• Cộng ~3~ vào ~a_2~ và ~a_3~, mảng thành: ~5, 5, 5, 4, 4~.

• Cộng ~1~ vào ~a_4~ và ~a_5~, mảng thành: ~5, 5, 5, 5, 5~.

Mảng có thể cân bằng tại giá trị ~5~ chỉ bằng thao tác cộng, do đó ta in ra ~1 \ 5~.

Độ khó: Khá (3/4 điểm)

Cho ba số nguyên dương ~S, N~ và ~F~. Hãy đếm số lượng dãy gồm ~N~ số nguyên ~x_1, x_2, \dots, x_N~ thỏa mãn đồng thời các điều kiện sau:

• Tổng các phần tử trong dãy đúng bằng ~S~: ~x_1 + x_2 + \dots + x_N = S~.

• Dãy không tăng: ~x_1 \ge x_2 \ge \dots \ge x_N~.

• Phần tử nhỏ nhất trong dãy không nhỏ hơn ~F~.

Hãy xác định số lượng dãy ~x~ khác nhau thỏa mãn các điều kiện trên.

Input

Một dòng duy nhất chứa ba số nguyên ~S, N~ và ~F~ ~(2 \le F \le S \le 400; 1 \le N \le 50)~, các số cách nhau bởi một khoảng trắng.

Output

Ghi ra một số nguyên duy nhất là số lượng dãy thỏa mãn.

Scoring

Sample Input 1

9 3 2

Sample Output 1

3

Notes

Có ~3~ dãy số thỏa mãn tất cả các điều kiện, bao gồm:

• ~5 \ 2 \ 2~

• ~4 \ 3 \ 2~

• ~3 \ 3 \ 3~

Phần tử nhỏ nhất trong các dãy trên đều là ~2~ (thỏa mãn điều kiện ~\ge F = 2~).