This is an interactive problem.

Description

In this problem, you need to play a classic game with an interactive library. In each game, the library generates a 5-letter word from a dictionary and tells you its first letter. You need to guess it within 5 attempts.

Each guess must be a word that exists in the dictionary. If you guess correctly, the game ends. After each incorrect guess, the interactive library returns which letters are in the correct position (indicated in gold) and which letters appear in the target word but are in the wrong position (indicated in silver).

Specifically, the interactive library returns two boolean arrays, gold and silver. gold[i] ($0 \le i < 5$, same below) indicates whether the $i$-th letter is guessed correctly (both position and content are correct). silver[i] indicates, if the $i$-th letter is not guessed correctly (i.e., not gold), whether this letter appears in the non-gold part of the target word.

For example, if the target word is panic and you guess paper, the library returns gold[0] = true (p is correct), gold[1] = true (a is correct), and the rest are false (note that although the second p in paper appears in panic, its position corresponds to a gold letter in this guess, so silver[2] = false).

As another example, if the target word is apple and you guess paper, the library returns gold[2] = true (p is correct), silver[0] = true (p appears in the non-gold part of this guess), silver[1] = true (a appears), silver[3] = true (e appears), and the rest are false.

Subtasks

Since each game has a high degree of randomness, you need to play $T = 1000$ consecutive games. The scoring criteria for each game are as follows:

• If the length of any guessed word is not 5, or the guessed word is not in the dictionary, you get 0 points.
• If you guess correctly on the 1st attempt, you get 150 points.
• If you guess correctly on the 2nd attempt, you get 120 points.
• If you guess correctly on the 3rd attempt, you get 100 points.
• If you guess correctly on the 4th attempt, you get 90 points.
• If you guess correctly on the 5th attempt, you get 85 points.
• If you fail after 5 attempts, you get 0 points.

Your score for this problem is the minimum of the average score of the 1000 games and 100 points.

Interaction

This problem only supports C++. You must submit a single source file word.cpp that implements the following functions and follows the naming and interface conventions below.

You need to include the header file word.h. You do not need to, and should not, implement the main function.

The functions you need to implement are:

const char *guess(int num_testcase, int remaining_guesses, char initial_letter, bool *gold, bool *silver);
void init(int num_scramble, const char *scramble);

For the $i$-th game, the num_testcase parameter is $i$ ($1 \le i \le T$). Each game will call the guess function 1 to 5 times. For the $j$-th call, the remaining_guesses parameter is $6-j$ ($1 \le j \le 5$). The initial_letter parameter is the first letter of the target word for the current game (guaranteed to be a lowercase letter). It is guaranteed that num_testcase is monotonically non-decreasing across calls to guess. When num_testcase is the same, initial_letter remains unchanged and remaining_guesses is monotonically decreasing. If a guess is correct or invalid, the current game ends, and the next call to guess will be for the next game.

gold and silver are the two boolean arrays described above. When remaining_guesses is 5, the gold and silver arrays are unavailable (i.e., they may be null pointers), so please avoid using them. When remaining_guesses is less than 5, gold and silver are two boolean arrays of size 5, storing the results of the previous guess.

The return value of the guess function must be a string of length 5, representing the guessed word. This word must be in the dictionary.

The init function will be called exactly once before all guess function calls. The num_scramble parameter is the size of the dictionary, and scramble is a string of length num_scramble * 5, storing all words in the dictionary, each of length 5, with no separators in between.

Examples

Input 1

7
p
gg---
gg---
ggg--
a
g----
ssgs-
a
g---g
gggg-
a
g---g
g---g
g---g
g---g
a
a
c
-sss-

Output 1

paper
paths
panda
panic

aargh
paper
apple

afore
apply
apple

apple
apple
apple
apple
apple

abcde

apple

kraal
cobra

Note

• For game 1, the target word is panic, guessed correctly on the 4th attempt.
• For game 2, the target word is apple, guessed correctly on the 3rd attempt.
• For game 3, the target word is apple, guessed correctly on the 3rd attempt. Note that even if every position has been guessed as gold at least once, an additional guess is still required to count as a correct guess.
• For game 4, the target word is above, all 5 guesses are incorrect. Note that the result of the 5th guess is not provided as input, nor is it passed to the guess function.
• For game 5, the target word is apple, the 1st guess is invalid (not in the dictionary), and the game ends immediately. Note that the sample program does not automatically recognize this situation.
• For game 6, the target word is apple, guessed correctly on the 1st attempt.
• For game 7, the target word is cobra. Note that when guessing kraal, both as are silver. Note that since the sample program does not know what the target word is, the program needs to be terminated manually.

Constraints

For 100% of the data, $T = 1000$, num_scramble = 8869. Each target word is generated independently and uniformly at random from all words in the dictionary. These words are fully determined before calling the guess function and are not constructed dynamically based on the interaction with your program.

The interactive library itself uses no more than 1 second of time and no more than 16 MB of memory.

Hint

Since there is only 1 test case for this problem, runtime errors, timeouts, memory limit exceeded, etc., will result in a total score of 0. It is recommended to check carefully to avoid such errors.