CF1970D3 Arithmancy (Hard)

在这道问题中，不同版本的唯一区别是 $ n $ 的最大值。 Vector 教授正忙着为她的算术课准备材料。她需要准备 $ n $ 个不同的魔法词。这些魔法词是由 X 和 O 组成的字符串。一个咒语是由两个魔法词组合而成的字符串，其威力由这个咒语中所有不同非空子串的数量决定。例如，XOXO 这个咒语的威力是 7，因为它有 7 种不同的子串：X、O、XO、OX、XOX、OXO 和 XOXO。 每位学生将从这些魔法词中挑选两个，拼接在一起形成自己的咒语。由于学生们对魔法尚不熟练，这两个词是从 Vector 教授准备的 $ n $ 个词中独立随机选择的，因此有可能选择的是同一个词。然后，学生会计算他们咒语的威力，并告诉 Vector 教授。为了更出色地评价学生的工作，Vector 教授希望能够精确地辨别出学生使用了哪两个魔法词，并且知道它们的顺序。 你的任务是扮演 Vector 教授的角色：首先，生成 $ n $ 个不同的魔法词，然后根据学生给出的咒语威力，确定他们使用了哪两个魔法词及其顺序。

这是一个交互式问题。 首先，你会读取一个整数 $ n $（$ 1 \le n \le 1000 $），表示需要准备的魔法词的数量。接着，你需要输出 $ n $ 个不同的魔法词，每行一个。每个魔法词的长度至少是 1，最多为 $ 30 \cdot n $ 个字符，而字符只能是 X 或 O。我们用 $ w_i $ 来表示你输出的第 $ i $ 个魔法词（$ 1 \le i \le n $）。 接下来，你会读取一个整数 $ q $（$ 1 \le q \le 1000 $），表示班级里有多少个学生。然后，对于每个学生，重复以下过程 $ q $ 次： 对于第 $ j $ 个学生，程序会读取一个整数 $ p_j $，代表他们咒语的威力。这一咒语的威力是随机选取两个 1 到 $ n $ 之间的索引 $ u_j $ 和 $ v_j $，然后组合 $ 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 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.

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