Кредитні картки

Limits: 2 sec., 256 MiB

Чи знали ви, що не всі номери кредитних карток є валідними? Для того, щоб уникнути хоча б частини помилок при введенні номерів кредитних карток, номери повинні задовільняти алгоритм Луна. Алгоритм Луна — це проста формула перевірки контрольної суми, котру використовують для валідації різноманітних ідентифікаційних номерів. Алгоритм працює наступним чином:

1. Дано певне додатнє число.

2. Помножимо кожну цифру на непарній позиції на 2 (тобто першу, третю і т.д.) і замінимо початкові цифри на ці результати. Якщо в результаті множення вийшло двоцифрове число, то впишемо обидві ці цифри.

3. Додамо разом усі цифри з числа, яке вийшло.

4. Якщо результат ділиться на 10 без остачі, то число з кроку 1 вважається валідним, в протилежному випадку це число не валідне.

Давайте глянемо як цей алгоритм працює на наступному прикладі:

1. Дано число 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 ділиться на 10, а отже число 126789 валідне.

Зеник працює над валідатором номерів кредиток мастеркард для одного волонтерського фонду, проте в його код закрався баг і він просить вас написати таку ж програму. Вам буде дано номер кредитної карти і вам потрібно перевірити чи:

1. Цей номер є валідним згідно алгоритму Луна.

2. Цей номер має префікс 51, 52, 53, 54 або 55.

Якщо обидві умови виконано, це валідний номер кредитки мастеркард. Сподіваємось, що ви кращий програміст ніж Зеник.

Input

Єдиний рядок містить номер кредитної картки мастеркард — рівно 16 цифр без пробілів.

Output

Якщо заданий номер задовільняє алгоритм Луна і має коректний префікс, виведіть слово VALID. Інакше, виведіть слово 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

Перший приклад не задовільняє алгоритм Луна.

Другий приклад задовільняє алгоритм Луна, проте не має корректного префіксу.

Долучайся до збору від Algotester на дрони для аеророзвідки за номером картки у прикладі 3!

Картки в прикладах 4-6 це картки фондів Сергія Притули, Мир і Ко, та Армія SOS. Кожна з цих організацій допомагає ЗСУ і ми будемо вдячні вам за донати цим організаціям :)