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 $ 后，刷新输出流。

• $ 1 \le n \le 1000 $
• $ 1 \le q \le 1000 $
• 每个魔法词的长度在 1 到 $ 30 \cdot n $ 之间。

本翻译由 AI 自动生成