UPC check digit (UPC Check Digit)

Nguồn: Problem Solving and Program Design in C

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho 12 chữ số thập phân

$$d_1,d_2,\ldots,d_{12},\qquad 0\le d_i\le9,$$

trong đó $d_{12}$ là chữ số kiểm tra của mã UPC.

Tính

$$S=3(d_1+d_3+d_5+d_7+d_9+d_{11}) +(d_2+d_4+d_6+d_8+d_{10}).$$

Chữ số kiểm tra phải có giá trị

$$c=(10-(S\bmod10))\bmod10.$$

Mã được xem là hợp lệ khi và chỉ khi

$$d_{12}=c.$$

Hãy in chữ số kiểm tra $c$ tính được và kết luận tính hợp lệ của 12 chữ số đã cho.

Input

Một dòng chứa đúng 12 số nguyên $d_1,d_2,\ldots,d_{12}$, mỗi số là một chữ số từ $0$ đến $9$.

Output

Dòng đầu in $c$. Dòng thứ hai in VALID nếu $d_{12}=c$, ngược lại in INVALID.

Subtask

Subtask 1 (100 điểm): $0\le d_i\le9$ với mọi $1\le i\le12$.

Ví dụ

Input

0 3 6 0 0 0 2 9 1 4 5 2

Output

2
VALID

Giải thích

Ta có $S=58$, nên $c=(10-8)\bmod10=2$. Chữ số cuối cũng bằng $2$, vì vậy mã hợp lệ.