配点 : $600$ 点

問題文

$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$ の間で、条件をみたす三つ組の列が共通のものである必要もありません。

制約

• $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
• $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})$ としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。

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\leq i\leq 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