[email protected] High School Programming Competition 2020

snails

Artwork from *Kunstformen der Natur* by
Ernst Haeckel, 1904. Retrieved from
Wikipedia.

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.

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}$.

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 |