CF1970D2 Arithmancy (Medium)

本题不同版本的区别仅在于 $n$ 的最大值。 Vector 教授在为她的算术课做准备，她需要准备 $n$ 个独特的魔法单词。每一个魔法单词都是由字符 X 和 O 组成的字符串。学生需要将两个魔法单词拼接在一起组成一个咒语，而咒语的力量（Power）定义为其所有不同的非空子串的数量。例如，咒语 XOXO 的力量为 7，因为它包括 7 个不同的子串：X, O, XO, OX, XOX, OXO 和 XOXO。 每位学生将独立随机地从 Vector 教授提供的 $n$ 个单词中挑选两个单词拼接形成自己的咒语，这意味着可能选择到两个完全相同的单词。然后学生计算出他们咒语的力量，并报告给 Vector 教授。为了检查学生们的计算结果并展示她的能力，Vector 教授需要知道每位学生拼接的具体是哪两个魔法单词以及它们的顺序。 你的任务就是扮演 Vector 教授：首先，创建 $n$ 个互不相同的魔法单词；接着，根据多次请求，通过已知的咒语力量来确定学生使用的两个单词索引及其顺序。

对于这个交互式问题，你的程序应先读取一个整数 $n$（$1 \le n \le 30$），表示需要准备的魔法单词数量。接着，输出 $n$ 个不同的魔法单词，每个单词占一行。这些单词必须彼此不同，每个单词长度在 1 到 $30 \cdot n$ 之间，每个字符必须是 X 或 O。第 $i$ 个输出的魔法单词记作 $w_i$（$1 \le i \le n$）。 然后，程序应读取一个整数 $q$（$1 \le q \le 1000$），表示学生人数。接下来，程序需要重复执行以下过程 $q$ 次，每次对应一个学生。 对于第 $j$ 个学生，程序首先读取一个整数 $p_j$，表示他们的咒语的力量。这个力量是通过随机独立选择两个索引 $u_j$ 和 $v_j$（它们在 1 到 $n$ 之间），将魔法单词 $w_{u_j}$ 和 $w_{v_j}$ 拼接后计算不同非空子串数量得到的。接着，程序需输出 $u_j$ 和 $v_j$，确保顺序正确（$1 \le u_j, v_j \le n$）。 请注意，你不仅需要找到两个能够产生给定力量的魔法单词，还必须精确找到学生实际选择的那两个单词及其顺序。 每次输出所有魔法单词以及每次输出 $u_j$ 和 $v_j$ 后，记得刷新输出流。

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.

- 1 ≤ n ≤ 30 - 1 ≤ q ≤ 1000 - 魔法单词长度在 1 到 $30 \cdot n$ 之间。 **本翻译由 AI 自动生成**