102807: [AtCoder]ABC280 Ex - Substring Sort

Problem Statement

You are given $N$ strings $S_1,S_2,\ldots, S_N$. Let $M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$.
For a string $S$ and integers $L$ and $R$, let us denote by $S[L, R]$ the substring consisting of the $L$-th through $R$-th characters of $S$.

A sequence of triples of integers $((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M))$ of length $M$ satisfies the following conditions:

• The $M$ elements are pairwise distinct.
• For all $1 \leq i \leq M$, it holds that $1 \leq K_i \leq N$ and $1 \leq L_i \leq R_i \leq |S_{K_i}|$.
• For all $1 \leq i \leq j \leq M$, it holds that $S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j]$ in the lexicographical order.

You are given $Q$ integers $x_1,x_2,\ldots, x_Q$ between $1$ and $M$, inclusive. For each $1 \leq i \leq Q$, find a possible instance of $(K_{x_i}, L_{x_i}, R_{x_i})$. We can prove that there always exists a sequence of triples that satisfies the conditions. If multiple triples satisfy the conditions, print any of them. In addition, among different $x_i$'s, the conforming sequence of triples does not have to be common.

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq \lvert S_i\rvert \leq 10^5$
• $\displaystyle\sum_{i=1}^N \lvert S_i\rvert\leq 10^5$
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq x_1<x_2<\cdots<x_Q \leq \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}$
• $N,Q,x_1,x_2,\ldots,x_Q$ are integers.
• $S_i$ is a string consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line should contain an instance of conforming $(K_{x_i}, L_{x_i}, R_{x_i})$, separated by spaces. If multiple triples satisfy the conditions, print any of them.

Sample Input 1

2
abab
cab
2
5 14

Sample Output 1

1 3 4
2 1 1

We have $M=16$. One possible sequence of triples that satisfies the conditions is $((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))$. The corresponding sequence of $S_{K_i}[L_i, R_i]$ for these $(K_i,L_i, R_i)$ in this order is (a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab).

Note that the sequence satisfies the conditions even if we swap the $5$-th element $(1,3,4)$ with the $4$-th or $6$-th one, so $(K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3)$ will also be accepted.

Sample Input 2

3
a
a
ba
2
1 2

Sample Output 2

1 1 1
1 1 1

We have $M=5$. The sequence of triples that satisfies the conditions can be
$(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2)$ or $(2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2)$, for example.

Note that, for $(K_{x_i}, L_{x_i}, R_{x_i})$ that you print, the conforming sequence whose $x_i$-th element is $(K_{x_i}, L_{x_i}, R_{x_i})$ does not have to be common among different $i$; in other words, there does not necessarily have to exist a sequence whose "$x_i$-th element is $(K_{x_i}, L_{x_i}, R_{x_i})$ for all $1\leq i\leq Q$."

Sample Input 3

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

Sample Output 3

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

问题描述

给你$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 \leq i \leq M$，有$1 \leq K_i \leq N$且$1 \leq L_i \leq R_i \leq |S_{K_i}|$。
• 对于所有的$1 \leq i \leq j \leq M$，在字典序中有$S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j]$。

给你$Q$个介于$1$和$M$之间的整数$x_1,x_2,\ldots, x_Q$。对于每个$1 \leq i \leq Q$，找出一个可能的$(K_{x_i}, L_{x_i}, R_{x_i})$实例。我们可以证明，总存在一个满足条件的三元组序列。如果有多组满足条件的三元组，输出其中任意一组。此外，对于不同的$x_i$，满足条件的三元组序列不必相同。

约束

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

输入

输入通过标准输入给出以下格式：

$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})$实例，用空格分隔。 如果有多组满足条件的三元组，输出其中任意一组。

样例输入1

2
abab
cab
2
5 14

样例输出1

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)$也将被接受。

样例输入2

3
a
a
ba
2
1 2

样例输出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$-th元素是$(K_{x_i}, L_{x_i}, R_{x_i})$的序列
在不同的$i$之间不需要是相同的； 换句话说，不一定存在这样一个序列 “对于所有$1\leq i\leq Q$，该序列的第$x_i$个元素是$(K_{x_i}, L_{x_i}, R_{x_i})$”。

样例输入3

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

样例输出3

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