Problem H
Who Wants to Live Forever?
Digital physics is a set of ideas and hypotheses that revolve around the concept of computable universe. Maybe our universe is just a big program running on a Turing machine? Is the state of the universe finite? Will the life of the universe end? We can only theorize.
In order to help advance the current state of knowledge on digital physics, we ask you to consider a particular model of the universe (which we shall call Bitverse) and determine whether its life comes to a conclusion or continues evolving forever.
Bitverse consists of a single sequence of $n$ bits (zeros or ones). The universe emerges as a particular sequence, in an event called the “Bit Bang”, and since then evolves in discrete steps. The rule is simple—to determine the next value of the $i$-th bit, look at the current value of the bits at positions $i - 1$ and $i + 1$ (if they exist; otherwise assume them to be 0). If you see exactly one 1, then the next value of the $i$-th bit is 1, otherwise it is 0. All the bits change at once, so the new values in the next state depend only on the values in the previous state. We consider the universe dead if it contains only zeros.
Given the state of the universe at the Bit Bang, answer the following fundamental question: will Bitverse live forever, or will it eventually die?
Input
The first line of the input contains the number of test cases $T$, where $1 \le T < 2^{16}$. Then $T$ lines follow, and each contains one test case, which is a string of at least $1$ and at most $200\, 000$ characters 0 or 1. The total number of 0 and 1 characters across all test cases is at most $2^{24}$.
Output
Print the answers to the test cases in the order in which they appear in the input. For each test case, print LIVES if the universe lives forever, and DIES otherwise.
Example
The first example universe will never become a sequence of zeros (it will continue flipping: 01, 10, 01, …). The second one will die in a few steps (0010100, 0100010, 1010101, 0000000). The third one does not change.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 01 0010100 11011 |
LIVES DIES LIVES |