UPC check digit (UPC Check Digit)

Source: Problem Solving and Program Design in C

Version: Phuoc Hung OJ Extended

Problem

Given 12 decimal digits

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

where $d_{12}$ is the UPC check digit.

Compute

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

The required check digit is

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

The code is valid if and only if

$$d_{12}=c.$$

Print the computed check digit $c$ and whether the given 12 digits are valid.

Input

One line contains exactly 12 integers $d_1,d_2,\ldots,d_{12}$, each a digit from $0$ to $9$.

Output

Print $c$ on the first line. Print VALID on the second line if $d_{12}=c$; otherwise print INVALID.

Subtask

Subtask 1 (100 points): $0\le d_i\le9$ for every $1\le i\le12$.

Example

Input

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

Output

2
VALID

Explanation

Here $S=58$, so $c=(10-8)\bmod10=2$. The last digit is also $2$, therefore the code is valid.