eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Кто хочет жить вечно?

Кто хочет жить вечно?

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Цифровая физика - это набор идей и гипотез, которые вращаются вокруг концепции вычислимой вселенной. Может быть, наша вселенная - это просто большая программа, работающая на машине Тьюринга? Является ли состояние вселенной конечным? Закончится ли жизнь вселенной? Мы можем только теоретизировать.

Чтобы помочь продвинуть текущее состояние знаний по цифровой физике, мы просим Вас рассмотреть конкретную модель вселенной (которую мы будем называть Битверс) и определить, подходит ли ее жизнь к завершению или продолжает развиваться вечно.

Битверс состоит из последовательности n битов (нулей или единиц). Вселенная возникает как особая последовательность, в событии, называемом "Удар по битам", и с тех пор развивается дискретными шагами. Правило простое - чтобы определить следующее значение i - го бита, посмотрите текущее значение битов в позициях i - 1 и i + 1 (если они существуют; в противном случае предположим, что они равны 0). Если Вы видите ровно одну 1, то следующее значение i - го бита 1, в противном случае 0. Все биты меняются одновременно, поэтому новые значения в следующем состоянии зависят только от значений в предыдущем состоянии. Мы считаем вселенную мертвой, если она содержит только нули.

Принимая во внимание состояние Вселенной в момент "Бит-взрыва", ответьте на следующий фундаментальный вопрос: будет ли "Битверс" жить вечно или он в конце концов умрет?

Вхідні дані

Первая строка содержит количество тестов t. Описания тестов приведены ниже:

Каждый тест представляет собой строку длины не менее 1 и не более 200000 символов 0 или 1.

Вихідні дані

Для каждого теста выведите LIVES если вселенная будет жить вечно, и DIES иначе.

Приклад

Вхідні дані #1
3
01
0010100
11011
Вихідні дані #1
LIVES
DIES
LIVES

Примітка

В первом примере вселенная никогда не станет последовательностью нулей (будет продолжаться: 01, 10, 01, ...). Во втором примере вселенная умрет через несколько шагов (0010100, 0100010, 1010101, 0000000). В третьем примере вселенная не будет изменяться.

Джерело 2012 ACM Central Europe Regional Contest, Краков, Ноябрь 16-18, Задача В