Алиса и Боб плавают в бассейне под руководством своего инструктора Монокарпа.
Бассейн можно представить как отрезок на оси OX от \(0\) по \(50\). И Алиса, и Боб начали в момент \(0\) в точке \(0\) с положительными вещественными скоростями \(v_A\) и \(v_B\) соответственно.
И Алиса, и Боб плывут от \(0\) до \(50\), затем мгновенно разворачиваются и плывут от \(50\) до \(0\). В точке \(0\) они снова поворачивают и плывут к \(50\) и так далее.
Монокарп записал различную информацию о том, как плавали Алиса и Боб, включая моменты времени, когда они встречались в одной точке (Алиса и Боб плавают по параллельным дорожкам, так что они не мешают друг другу). Давайте назовем эти моменты времени последовательностью \(t_1, t_2, \dots, t_n\).
Из-за некоторого инцидента Монокарп потерял почти все записанные данные, и все, что у него осталось,— это массив \(t\). Монокарп помнит, что Алиса и Боб плавали с различными положительными вещественными скоростями \(v_A\) и \(v_B\) (\(v_A > 0\); \(v_B > 0\); \(v_A \neq v_B\)) и что последовательность \(t\) содержит первые \(n\) моментов встреч.
Но, глядя на последовательность \(t\), он заметил, что все \(t_i\) являются целыми числами. И теперь он сомневается, возможна ли такая последовательность \(t\) или в ней есть какие-то ошибки. Помогите Монокарпу проверить массив \(t\)!
Выходные данные
Для каждого набора входных данных выведите VALID, если массив \(t\) можно было получить, или, другими словами, существуют такие вещественные значения \(v_A\) и \(v_B\) (\(v_A, v_B > 0\); \(v_A \neq v_B\)), что массив \(t\) содержит первые \(n\) моментов встреч Алисы и Боба в бассейне.
В противном случае выведите INVALID.
Ответ можно выводить в любом регистре (верхнем или нижнем). Например, строки «vALid», «valid», «Valid» и «VALID» будут распознаны как положительные ответы.
Примечание
В первом наборе входных данных представим следующую ситуацию: длина бассейна \(v_A = 1\) и \(v_B = \frac{29}{21}\). Тогда в момент \(42\) Алиса и Боб будут в точке \(42\).
Во втором наборе представим, что \(v_A = \frac{175}{6}\) и \(v_B = \frac{25}{6}\). Тогда в момент \(3\) Алиса и Боб встретятся в точке \(12.5\), в \(4\) они встретятся в точке \(\frac{50}{3}\), в \(6\) они встретятся в точке \(25\) и в момент \(8\) — в точке \(\frac{100}{3}\). Поскольку это — в точности первые \(4\) момента встреч, то массив \(t\) — valid.
В третьем набора одна из возможных ситуаций: \(v_A = 25\) и \(v_B = 75\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
1
42
4
3 4 6 8
5
1 2 3 4 5
3
999999998 999999999 1000000000
5
4 6 8 12 16
4
6 11 12 14
2
10 30
|
VALID
VALID
VALID
INVALID
VALID
INVALID
INVALID
|