Problem K
snails
In prehistoric times, there were many creatures with shells that lived in the ocean. You are part of a team of researchers who are looking at a collection of shell fossils with spiral shapes. You want to determine what kind of animal each one came from.
For each shell, you have taken a sequence of measurements along the spiral part. It is hypothesized that if the measurements $ M_1\ M_2\ \ldots \ M_ k$ for a given shell follow the pattern of the following sequence, it is a nautilus shell:
\begin{align*} M_1 & = 0 \\ M_2 & = 1 \\ M_3 & = 2 \\ M_4 & = 3 \\ M_{k} & = M_{k-1} + M_{k-2} + M_{k-3} + M_{k-4} & \text {when $k > 4$} \end{align*}Otherwise, it is a snail shell.
The team has collected a very large number of measurements. Being the member with the most programming experience, you have been asked to write a computer program to automate the task of determining whether each sequence of measurements is for a snail shell or nautilus shell.
Input
The first line of input shall be $n$, the number of lines of input that follow, where $1 \leq n < 2^{15} $.
The subsequent $n$ lines of input shall each be a sequence of $k$ (where $1 \leq k < 2^{15}$) measurements $M_1\ M_2\ \ldots \ M_ k$ pertaining to one shell fossil. Measurements are separated by spaces. Each measurement shall be in the range $0 \leq M < 2^{32}$.
Output
For each line of input where the measurements came from a nautilus shell, the output shall be a line with only NAUTILUS. For each line of input where the measurements came from a snail shell, the output shall be a line with only SNAIL.
Sample Input 1 | Sample Output 1 |
---|---|
4 0 1 2 0 1 1 2 0 1 2 3 4 0 1 2 3 6 |
NAUTILUS SNAIL SNAIL NAUTILUS |