题目描述

$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]$ である。

$1$ 以上 $M$ 以下の整数 $Q$ 個 $x_1,x_2,\ldots,\ x_Q$ が与えられます。各 $1\ \leq\ i\ \leq\ Q$ に対して、$(K_{x_i},\ L_{x_i},\ R_{x_i})$ としてあり得るものを $1$ つずつ求めてください。なお、条件をみたす三つ組の列が必ず $1$ つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる $x_i$ の間で、条件をみたす三つ組の列が共通のものである必要もありません。

辞書順とは $2$ つの文字列 $S,\ T$ が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で $S\ \leq\ T$ であると言います。 - $|S|\ \leq\ |T|$ かつ $S\ =\ T[1,\ |S|]$ である。

• ある $1\leq\ k\leq\ \min(|S|,\ |T|)$ が存在し、$1\leq\ i\leq\ 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

3
a
a
ba
2
1 2

1 1 1
1 1 1

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\ \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$ は英小文字のみからなる文字列

Sample Explanation 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)$ も正解となります。

Sample Explanation 2

$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\leq\ i\leq\ Q$ について $x_i$ 番目の要素が $(K_{x_i},\ L_{x_i},\ R_{x_i})$ である」 ような列は **必ずしも存在する必要がない** ことに注意してください。