Bài tập

Một số nguyên dương \(n\) được gọi là số chia hết tổng chữ số nếu \(n\) chia hết cho tổng các chữ số trong biểu diễn thập phân của nó. Chẳng hạn \(36\) có tổng chữ số là \(9\) và \(36 = 4 \cdot 9\) nên thỏa mãn, còn \(25\) có tổng chữ số \(7\) và không chia hết cho \(7\) nên không thỏa mãn.

Cho số nguyên dương \(n\). Hãy kiểm tra \(n\) có thỏa mãn tính chất trên hay không.

Input

• Một dòng chứa số nguyên dương \(n\).

Output

• In ra 1 nếu \(n\) thỏa mãn, ngược lại in ra 0.

Constraints

• \(1 \le n \le 10^{18}\)

Sample Input 1

36

Sample Output 1

1

Sample Input 2

25

Sample Output 2

0

Một chiếc bánh kem hình tròn (nhìn từ trên xuống) đã bị cắt sẵn \(n\) nhát. Mỗi nhát cắt là một đoạn thẳng đi từ tâm bánh ra tới mép bánh; nhát thứ \(i\) hợp với tia \(Ox\) (chiều dương) một góc \(a_i\) độ. Các góc được liệt kê theo chiều ngược chiều kim đồng hồ và không giảm, nên có thể có nhiều nhát cắt trùng nhau (khi đó chúng chỉ được tính là một nhát cắt duy nhất).

Các nhát cắt chia chiếc bánh thành các miếng hình quạt: mỗi miếng nằm giữa hai nhát cắt kề nhau (kể cả cặp nhát cuối và nhát đầu quay vòng lại). Cần cắt thêm một số nhát (cũng là các đường từ tâm ra mép, ở góc tùy ý) sao cho tất cả các miếng bánh đều có góc bằng nhau.

Hãy tính số nhát cắt thêm ít nhất cần thực hiện.

Input

• Dòng đầu chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\).

Output

• In ra một số nguyên: số nhát cắt thêm ít nhất.

Constraints

• \(1 \le n \le 10\)
• \(0 \le a_i \le 359\)
• \(a_i \le a_{i+1}\)

Sample Input 1

3
0 90 120

Sample Output 1

9

Sample Input 2

2
10 190

Sample Output 2

0

Explanation

Ví dụ 1: các nhát cắt ở 0, 90 và 120 độ tạo các miếng 90, 30 và 240 độ. Góc miếng nhỏ nhất có thể chia đều là ước chung lớn nhất của các góc này và 360, tức 30 độ, tổng cộng 12 miếng. Đã có 3 nhát nên cần thêm 9 nhát.

Ví dụ 2: hai nhát tạo hai miếng 180 độ bằng nhau, không cần cắt thêm.

Bạn Minh gặp một "đẳng thức" sai có dạng \(A = S\), trong đó \(A\) và \(S\) là hai số nguyên dương viết bằng chữ số thập phân, không có chữ số \(0\) đứng đầu, và \(A \ne S\). Để sửa lại cho đúng, Minh được phép chèn thêm các dấu cộng + vào giữa một số cặp chữ số liền nhau của \(A\), sao cho tổng các số hạng thu được đúng bằng \(S\). Các số hạng sau khi tách có thể có chữ số \(0\) đứng đầu (ví dụ 05 được hiểu là \(5\), 000 là \(0\)).

Hãy tìm số dấu cộng ít nhất cần chèn.

Input

Một dòng duy nhất có dạng A=S (không có dấu cách). Dữ liệu đảm bảo luôn tồn tại ít nhất một cách chèn.

Output

In ra số dấu cộng tối thiểu cần chèn.

Constraints

• \(A\) có tối đa \(1000\) chữ số.
• \(1 \le S \le 5000\).

Sample Input

3120405=96

Sample Output

3

Explanation

Chèn thành 31+20+40+5 có tổng \(96\) với \(3\) dấu cộng. Không thể dùng ít hơn \(3\) dấu cộng.

Kỳ thi chọn đội tuyển có \(K\) bài tập và \(N\) giám khảo. Giám khảo thứ \(i\) đề nghị cho bài thứ \(j\) số điểm \(A[i][j]\).

Hội đồng cần gán cho mỗi bài một số điểm \(b_1, b_2, \dots, b_K\) thỏa mãn đồng thời:

• Tổng điểm \(b_1 + b_2 + \dots + b_K\) đúng bằng \(S\).
• Điểm không giảm theo thứ tự bài: \(b_1 \le b_2 \le \dots \le b_K\).
• Với mỗi bài \(j\), điểm \(b_j\) phải bằng số điểm mà một giám khảo nào đó đề nghị cho bài \(j\) (tức \(b_j = A[i][j]\) với một \(i\) nào đó).

Hãy tìm một cách gán điểm hợp lệ. Nếu có nhiều cách, in cách có dãy \((b_1, b_2, \dots, b_K)\) nhỏ nhất theo thứ tự từ điển.

Input

• Dòng đầu gồm ba số nguyên \(S, N, K\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) gồm \(K\) số nguyên \(A[i][1], \dots, A[i][K]\).

Output

• Nếu không có cách gán nào, in NO.
• Ngược lại in YES ở dòng đầu, dòng thứ hai in \(K\) số \(b_1, \dots, b_K\) cách nhau một dấu cách.

Constraints

• \(1 \le S \le 200\), \(1 \le N \le 20\), \(1 \le K \le 20\)
• \(0 \le A[i][j] \le 200\)

Sample Input 1

24 3 3
4 7 10
6 5 12
3 9 8

Sample Output 1

YES
3 9 12

Sample Input 2

10 3 2
1 2
3 4
2 1

Sample Output 2

NO

Explanation

Ở ví dụ 1, điểm bài 1 lấy từ \(\{4,6,3\}\), bài 2 từ \(\{7,5,9\}\), bài 3 từ \(\{10,12,8\}\). Cách \(3, 9, 12\) có tổng \(24\) và không giảm. Ở ví dụ 2, tổng lớn nhất có thể là \(3+4=7<10\) nên không có cách nào.