311326: CF1970D3. Arithmancy (Hard)

D3. Arithmancy (Hard)time limit per test10 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

This is an interactive problem.

First, your program should read a single integer $n$ ($1 \le n \le 1000$), 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.

ExampleInput

2


2
15

11

Output

XOXO
X


1 1

2 1

题目大意：
这个问题的不同版本之间唯一的区别是n的最大值。
Vector教授正在准备教授她的算术课。她需要为课程准备n个不同的魔法单词。每个魔法单词都是一个由字符X和O组成的字符串。一个咒语是通过将两个魔法单词连接在一起创建的。一个咒语的力量等于它的不同非空子字符串的数量。例如，咒语XOXO的力量等于7，因为它有7个不同的子字符串：X, O, XO, OX, XOX, OXO和XOXO。
每个学生将通过将两个魔法单词连接在一起来创建自己的咒语。由于学生还不擅长魔法，他们将独立且均匀地从Vector教授提供的n个单词中随机选择每个单词。因此，学生选择的两个单词也可能是相同的。然后，每个学生将计算他们的咒语的力量，并告诉Vector教授。为了检查他们的工作，当然还有打动学生，Vector教授需要找出每个学生连接的是哪两个魔法单词以及它们的顺序。
程序需要扮演Vector教授的角色：首先，创建n个不同的魔法单词，然后处理多个请求，其中给出了咒语的力量，并需要确定用于创建相应咒语的两个魔法单词的索引，以及正确的顺序。

输入输出数据格式：
输入：
第一行是一个整数n（1≤n≤1000），表示要准备的魔法单词的数量。
接下来n行，每行是一个魔法单词，由字符X和O组成，长度至少为1且最多为30*n。
然后是一个整数q（1≤q≤1000），表示班上的学生数量。
接下来q行，每行是一个整数p_j，表示第j个学生的咒语的力量。

输出：
对于每个学生，输出两个整数u_j和v_j（1≤u_j,v_j≤n），分别表示用于创建该学生咒语的两个魔法单词的索引，按正确的顺序。

示例：
输入：
2
XOXO
X
2
15
11

输出：
1 1
2 1题目大意： 这个问题的不同版本之间唯一的区别是n的最大值。 Vector教授正在准备教授她的算术课。她需要为课程准备n个不同的魔法单词。每个魔法单词都是一个由字符X和O组成的字符串。一个咒语是通过将两个魔法单词连接在一起创建的。一个咒语的力量等于它的不同非空子字符串的数量。例如，咒语XOXO的力量等于7，因为它有7个不同的子字符串：X, O, XO, OX, XOX, OXO和XOXO。 每个学生将通过将两个魔法单词连接在一起来创建自己的咒语。由于学生还不擅长魔法，他们将独立且均匀地从Vector教授提供的n个单词中随机选择每个单词。因此，学生选择的两个单词也可能是相同的。然后，每个学生将计算他们的咒语的力量，并告诉Vector教授。为了检查他们的工作，当然还有打动学生，Vector教授需要找出每个学生连接的是哪两个魔法单词以及它们的顺序。 程序需要扮演Vector教授的角色：首先，创建n个不同的魔法单词，然后处理多个请求，其中给出了咒语的力量，并需要确定用于创建相应咒语的两个魔法单词的索引，以及正确的顺序。 输入输出数据格式： 输入： 第一行是一个整数n（1≤n≤1000），表示要准备的魔法单词的数量。 接下来n行，每行是一个魔法单词，由字符X和O组成，长度至少为1且最多为30*n。 然后是一个整数q（1≤q≤1000），表示班上的学生数量。 接下来q行，每行是一个整数p_j，表示第j个学生的咒语的力量。 输出： 对于每个学生，输出两个整数u_j和v_j（1≤u_j,v_j≤n），分别表示用于创建该学生咒语的两个魔法单词的索引，按正确的顺序。 示例： 输入： 2 XOXO X 2 15 11 输出： 1 1 2 1