Word by mouth

N friends play a word by mouth game. Friend 1 is the leader, and the game starts with the leader saying one word, either cat or hat, to each of the other friends. m of the N friends pronounce the words badly: where such a friend means hat, the listener hears cat. To keep the rules simple, a friend like this always says cat to the others, whatever he was told. The leader may be one of them, and then he says a different word to different friends.

To settle on one word, the friends run the algorithm WBM(m).

Algorithm WBM(m), m > 0

1. The leader sends his word to every other friend.
2. For each friend $i$, let $v_i$ be the word friend $i$ received from the leader. Friend $i$ then acts as the leader of WBM(m-1) and sends $v_i$ to the friends taking part in the current call, himself and the current leader excluded. A message that started at friend $i$ never comes back to $i$.
3. For each $i$ and each $j \ne i$, let $v_j$ be the word friend $i$ received from friend $j$ in step 2. Friend $i$ takes the word that occurs more often among $v_1, v_2, \dots, v_{N-1}$. When both words occur the same number of times, friend $i$ takes cat.

Algorithm WBM(0)

1. The leader sends his word to every other friend.
2. Each friend takes the word he received from the leader.

The game starts with the leader running WBM(m). Every time a friend passes a word on he adds his own ID to the message, so the receiver knows which path the message came along. The messages the leader sends first carry no path.

The first figure shows $N = 4$ friends where the leader sends cat to friend 2 and hat to friends 3 and 4. Friend 2 gets cat from 1, hat from 3, hat from 4, and takes hat. Friend 3 gets hat from 1, cat from 2, hat from 4, and takes hat. Friend 4 gets hat from 1, cat from 2, hat from 3, and takes hat. The three friends other than the leader all reach the same word even though the leader said two different words.

Fig. 1 $N = 4$ friends, leader $i = 1$ sends a word he pronounces badly.

The second figure again has $N = 4$ friends, but this time $m = 2$ of them pronounce badly, friends 2 and 3, and the leader says hat to everyone. More messages travel. Friend 2 sends cat to friend 3, and friend 3 passes it on to friend 4, drawn in the figure as 2,3:cat. Friend 2 also sends cat straight to friend 4, drawn as 2:cat. Friend 4 therefore holds cat twice for friend 2 and decides that friend 2 said cat. In the same way friend 4 holds cat directly from friend 3 and cat once more along 3,2:cat, so he decides that friend 3 said cat. The leader told friend 4 hat. The word that occurs more often is cat, so friend 4 takes cat.

Fig. 2 $N = 4$ friends, friends $i = 2$ and $i = 3$ send a word they pronounce badly.

Report the word taken by every friend who pronounces correctly, the leader excluded. There are $N - m - 1$ such friends when the leader pronounces correctly, and $N - m$ when he does not.

The first line contains N and m ($2 < N < 101$, $0 < m < 8$). The second line contains m distinct integers, the IDs of the friends who change the words. The leader always has ID 1. Each of the next $N - 1$ lines contains the word, cat or hat, that the leader sends to friend $2, 3, \dots, N$, in this order. When the leader pronounces correctly, all $N - 1$ of those words are the same.

Print the word taken by each correctly pronouncing friend other than the leader, one per line, in increasing order of friend ID. That is $N - m - 1$ lines when the leader pronounces correctly, and $N - m$ lines when he does not.