Problem H
Pony Express Letters

Original image by Owen Kaser, Public domain

In the days of the “pony express”, it was very expensive to send a message across the United States, so people would go to great lengths to reduce the number of pages they had to pay for.

One approach was that the message’s author would write the first part of the message in one colour of ink, filling up the page. Then they would change the colour of ink, and they would continue the message by writing on top of the earlier parts of the message. Often they would rotate the letter by 90 degrees when they changed the ink colour.

We will assume that the rotation was not done, but the paper was divided into a grid, like graph paper. Using the first colour of ink, they wrote the first part of the message by putting one letter in each grid cell. After the page was filled, they restarted at the top left, changed the ink colour and squeezed a second letter into each grid cell. Sometimes there was more room toward the left side of the cell, and sometimes there was more room toward the right side of the cell. When they added the second letter to the cell, it was squeezed in on the side that had more room.

The filled grid was filled in row by row (starting with the first row), working left to right within a row. If they reached the rightmost column in a row and were still partway through a word, they would continue the word in the leftmost column on the next row (or on the first row, if they changed the ink colour). Besides letters, they could write spaces, and they could put zero or more spaces between words, but no spaces within a word. The cost to send a message was so high that they would always nearly fill the page when writing in the second colour. However, there could be a few rows at the bottom left as spaces.

Over time, the colours of the ink have faded and nobody can distinguish between the two colours anymore. However, it is still possible to tell which two characters (counting both blanks and letters) were written in a grid cell. Either letter in a grid cell could be used as part of a word.

A historian has found one of these messages. She has a list of six words and for each word, she wants to know if it occurs at least once in the message. The words are “attack”, “die”, “fever”, “hunger”, “happy”, and “antidisestablishmentarianism”. If the original message contained “attacked”, we would consider it to contain “attack”; similarly, if it contained “studied”, we would consider to contain “die”.

Input

The input starts with a single positive integer $N$ representing the number of rows and columns in the grid, with $N \leq 30$.

The next $N$ input rows have the contents of the grid. Each row has exactly $2N$ characters on it. The first two characters are the two characters written the first grid cell for that line. The third and fourth characters are the two letter written in the second grid cell for that line, and so forth. We will use only lowercase characters, except that we represent spaces by underscores.

To avoid some ambiguous situations, the input guarantees that a grid cell cannot be used for two of the historian’s words. Thus, you will not get an input like the image, where the words “fever” and “attack” overlap.

Output

The output consist $6$ lines, each containing Y or N. The first line is Y if “attack” was found in the message; it is N otherwise. The second line similarly is Y or N depending on whether “die” was found. The third, fourth, fifth and sixth lines respectively indicate whether the message contains “fever”, “hunger”, “happy” and “antidisestablishmentarianism”.

In the first example, the original message was “bit of fever hunger and blood”.

4
bgeitr__
oafn_df_
eblvoero
_d_h_un_

N
N
Y
Y
N
N

2
site
udd_

N
Y
N
N
N
N