← 返回题目列表

Codeforces · 1970/D3

D3. 算术占卜(难)

中文机器翻译题面 查看原题

此问题的各个版本之间的唯一区别是 $$$n$$$ 的最大值。

Vector教授正在准备教她的算术占卜课。她需要准备 $$$n$$$ 不同的 魔语 为班级。每个魔法词都是由字符组成的字符串 X 和 O。一个 咒语 是通过将两个魔术词连接在一起创建的字符串。的 电源 咒语的 等于其不同非空子串的数量。例如,咒语的威力 XOXO 等于 7,因为它有 7 个不同的子字符串: X, O, XO, OX, XOX, 氧化 和 XOXO.

每个学生将通过连接两个魔法词来创建自己的咒语。由于学生们还不太擅长魔术,所以他们会从Vector教授提供的$$$n$$$个单词中独立且统一地随机选择两个单词中的每一个。因此,学生选择的两个单词也有可能是相同的。然后每个学生将计算他们的咒语的力量,并将其告诉矢量教授。为了检查他们的工作,当然也为了给学生留下深刻的印象,Vector 教授需要找出每个学生连接的是哪两个魔术词以及连接的顺序。

你的程序需要扮演 Vector 教授的角色:首先,创建 $$$n$$$ 不同的魔法词,然后处理多个请求,其中它被赋予法术强度,并且需要以正确的顺序确定两个魔法词的索引,用于创建相应的法术。

互动

这是一个交互问题。

首先,你的程序应该读取单个整数 $$$n$$$ ($$$1 \le n \le 1000$$$),即要准备的魔术词的数量。然后,它应该打印它创建的 $$$n$$$ 魔术词,每行一个。魔法词必须是不同的,每个魔法词必须至少有 1 个且最多 $$$30\cdot n$$$ 个字符,并且每个字符必须是 X or O。我们将您打印的第 $$$i$$$ 魔术字表示为 $$$w_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$$$ 后刷新输出流。

示例

输入
复制

2


2
15

11

输出
复制

XOXO
X


1 1

2 1