Arithmancy (Medium)
Contest: Helvetic Coding Contest 2024 online mirror (teams allowed, unrated)
Difficulty rating: 3100
Tags: interactive

The only difference between the versions of this problem is the maximum value of $$$n$$$.

Professor Vector is preparing to teach her Arithmancy class. She needs to prepare $$$n$$$ distinct magic words for the class. Each magic word is a string consisting of characters X and O. A spell is a string created by concatenating two magic words together. The power of a spell is equal to the number of its different non-empty substrings. For example, the power of the spell XOXO is equal to 7, because it has 7 different substrings: X, O, XO, OX, XOX, OXO and XOXO.

Each student will create their own spell by concatenating two magic words. Since the students are not very good at magic yet, they will choose each of the two words independently and uniformly at random from the $$$n$$$ words provided by Professor Vector. It is therefore also possible that the two words a student chooses are the same. Each student will then compute the power of their spell, and tell it to Professor Vector. In order to check their work, and of course to impress the students, Professor Vector needs to find out which two magic words and in which order were concatenated by each student.

Your program needs to perform the role of Professor Vector: first, create $$$n$$$ distinct magic words, and then handle multiple requests where it is given the spell power and needs to determine the indices of the two magic words, in the correct order, that were used to create the corresponding spell.

Interaction format:
This is an interactive problem.

First, your program should read a single integer $$$n$$$ ($$$1 \le n \le 30$$$), the number of magic words to prepare. Then, it should print $$$n$$$ magic words it has created, one per line. The magic words must be distinct, each magic word must have at least 1 and at most $$$30\cdot n$$$ characters, and each character must be either X or O. We will denote the $$$i$$$-th magic word you printed as $$$w_i$$$ ($$$1 \le i \le n$$$).

Then, your program should read a single integer $$$q$$$ ($$$1 \le q \le 1000$$$), the number of students in the class. Then, it should repeat the following process $$$q$$$ times, one per student.

For the $$$j$$$-th student, it should first read a single integer $$$p_j$$$, the power of their spell. It is guaranteed that this number is computed by choosing two indices $$$u_j$$$ and $$$v_j$$$ independently and uniformly at random between 1 and $$$n$$$ inclusive, concatenating $$$w_{u_j}$$$ and $$$w_{v_j}$$$, and finding the number of different non-empty substrings of the resulting string. Then, your program must print the numbers $$$u_j$$$ and $$$v_j$$$, in this order ($$$1 \le u_j, v_j \le n$$$).

Note that it is not enough to find any two magic words that concatenate into a spell with the given power. You must find the exact words used by the student in the exact order.

Remember to flush the output stream after printing all magic words and after printing $$$u_j$$$ and $$$v_j$$$ for each student.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Example input:
2


2
15

11

Example output:
XOXO
X


1 1

2 1

Editorial:
Now we need to find 30 words, so manually solving on paper is out of question. However, "just trying" still works: what we can do is to keep generating random words until we find 30 that have all 900 corresponding spell powers different. Depending on how you fast is your computation of the spell power you can either do this during the time limit, or precompute locally and then just submit a solution that prints the precomputed words.
To make sure that we have to precompute only once instead of 30 times (for $$$n=1$$$, $$$n=2$$$, ...), we can find 30 words such that the $$$i$$$-th word has length $$$30\cdot i$$$. This way the first $$$n$$$ words from this list give a valid answer to the problem for any $$$n<=30$$$.
To compute the spell power, we can either use the naive approach of taking all substrings, sorting them and finding unique ones, some optimization thereof (for example, if the words are randomly generated, the chances that sufficiently long substrings coincide are vanishingly small and can be ignored), or the asymptotically optimal approach using any of the suffix data structures (the suffix array, or the suffix automaton, or the suffix tree).