[email protected] High School Programming Competition 2020

Start

2020-04-25 08:23 AKDT

[email protected] High School Programming Competition 2020

End

2020-04-25 11:53 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -268 days 9:42:50

Time elapsed

3:30:00

Time remaining

0:00:00

Problem K
snails

/problems/mines20.snails/file/statement/en/img-0001.jpg
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.

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