Credit Cards

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Did you know that not all credit card numbers are valid? In order to avoid at least some errors when entering credit card numbers, the numbers must satisfy the Luhn algorithm. The Luhn algorithm is a simple checksum formula used to validate various identification numbers. The algorithm works as follows:

1. Given a certain positive number.

2. Multiply each digit at an odd position by 2 (i.e., the first, third, etc.) and replace the initial digits with these results. If the result of the multiplication is a two-digit number, we write down both of these digits.

3. Add together all the digits of the resulting number.

4. If the result is divisible by 10 without a remainder, then the number from step 1 is considered valid, otherwise the number is not valid.

Let’s look at how this algorithm works in the following example:

1. Given the number 126789.

2. 126789 \(\to\) 1\(\cdot\)2|2|6\(\cdot\)2|7|8\(\cdot\)2|9 \(\to\) 2|2|12|7|16|9 \(\to\) 22127169.

3. 2+2+1+2+7+1+6+9 = 30.

4. 30 is divisible by 10, and therefore the number 126789 is valid.

Zenyk is working on a Mastercard credit card number validator for a volunteer foundation, but a bug has crept into his code and he asks you to write the same program. You will be given a credit card number and you need to check if:

1. This number is valid according to the Luhn algorithm.

2. This number has the prefix 51, 52, 53, 54 or 55.

If both conditions are met, it is a valid Mastercard credit card number. We hope you are a better programmer than Zenyk.

Input

The only line contains a Mastercard credit card number — exactly 16 digits without spaces.

Output

If the given number satisfies the Luhn algorithm and has the correct prefix, print the word VALID. Otherwise, print the word BAD.

Samples

Input (stdin) сopy	Output (stdout) сopy
5555555555554443	BAD

Input (stdin) сopy	Output (stdout) сopy
8888888888888888	BAD

Input (stdin) сopy	Output (stdout) сopy
5375411203491563	VALID

Input (stdin) сopy	Output (stdout) сopy
5168742063537207	VALID

Input (stdin) сopy	Output (stdout) сopy
5169330524195689	VALID

Input (stdin) сopy	Output (stdout) сopy
5168745606525191	VALID

Notes

The first example does not satisfy the Luhn algorithm.

The second example satisfies the Luhn algorithm, but does not have the correct prefix.

Join the fundraiser from Algotester for drones for aerial reconnaissance using the card number in example 3!

The cards in examples 4-6 are cards of the Serhiy Prytula Foundation, People’s Project, and Army SOS. Each of these organizations helps the Armed Forces of Ukraine and we will be grateful to you for donations to these organizations :)