子串排序

题目描述

给定 $N$ 个字符串 $S_1,S_2,\ldots, S_N$。

令 $M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$。

对于字符串 $S$ 和整数 $L, R$,用 $S[L, R]$ 表示由 $S$ 的第 $L$ 个到第 $R$ 个字符构成的子串。

一个长度为 $M$ 的三元组序列 $((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M))$ 满足以下条件:

• 这 $M$ 个元素两两不同。
• 对所有 $1 \le i \le M$,满足 $1 \le K_i \le N$ 且 $1 \le L_i \le R_i \le |S_{K_i}|$。
• 对所有 $1 \le i \le j \le M$,按字典序有 $S_{K_i}[L_i, R_i] \le S_{K_j}[L_j, R_j]$。

给定 $Q$ 个介于 $1$ 和 $M$ 之间(含两端)的整数 $x_1,x_2,\ldots, x_Q$。对于每个 $1 \le i \le Q$,求满足条件的三元组序列中第 $x_i$ 个元素 $(K_{x_i}, L_{x_i}, R_{x_i})$ 的一个可行取值。可以证明总是存在满足条件的三元组序列。若存在多个满足条件的三元组,输出其中任意一个即可。此外,对于不同的 $x_i$,所对应的满足条件的三元组序列不必相同。

什么是字典序?

两个字符串 $S$ 和 $T$ 满足字典序 $S \le T$,当且仅当满足以下条件之一:

• $|S| \le |T|$ 且 $S = T[1, |S|]$。
• 存在 $1 \le k \le \min(|S|, |T|)$,使得对所有 $1 \le i \le k-1$,$S$ 和 $T$ 的第 $i$ 个字符相同,并且 $S$ 的第 $k$ 个字符在字母顺序上严格小于 $T$ 的第 $k$ 个字符。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$
$Q$
$x_1$ $x_2$ $\ldots$ $x_Q$

输出格式

输出 $Q$ 行。第 $i$ 行输出满足条件的 $(K_{x_i}, L_{x_i}, R_{x_i})$ 的一个实例,用空格分隔。 若存在多个满足条件的三元组,输出其中任意一个即可。

样例

2
abab
cab
2
5 14

1 3 4
2 1 1

有 $M=16$。满足条件的三元组序列的一个例子是 $((1,1,1), (1,3,3), (2,2,2), (1,1,2), (1,3,4), (2,2,3), (1,1,3), (1,1,4), (1,2,2), (1,4,4), (2,3,3), (1,2,3), (1,2,4), (2,1,1), (2,1,2), (2,1,3))$。 这些 $(K_i,L_i, R_i)$ 按此顺序对应的 $S_{K_i}[L_i, R_i]$ 序列为 (a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab)。

注意,即使将第 $5$ 个元素 $(1,3,4)$ 与第 $4$ 个或第 $6$ 个元素交换,序列仍然满足条件, 因此输出 $(K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3)$ 也会被接受。

3
a
a
ba
2
1 2

1 1 1
1 1 1

有 $M=5$。满足条件的三元组序列可以是 $(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2)$ 或 $(2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2)$, 等等。

注意,对于所输出的 $(K_{x_i}, L_{x_i}, R_{x_i})$,对应的以第 $x_i$ 个元素为 $(K_{x_i}, L_{x_i}, R_{x_i})$ 的满足条件序列在所有的 $i$ 之间不必相同; 换言之,不一定存在一个序列,使得对所有 $1 \le i \le Q$,该序列的「第 $x_i$ 个元素是 $(K_{x_i}, L_{x_i}, R_{x_i})$」。

10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489

3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12

数据范围

• $1 \le N \le 10^5$
• $1 \le \lvert S_i \rvert \le 10^5$
• $\displaystyle\sum_{i=1}^N \lvert S_i \rvert \le 10^5$
• $1 \le Q \le 2\times 10^5$
• $1 \le x_1 \lt x_2 \lt \cdots \lt x_Q \le \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$
• $N, Q, x_1, x_2, \ldots, x_Q$ 是整数。
• $S_i$ 是由小写英文字母组成的字符串。

提示

答案不唯一,输出任意合法解即可。