問題文

$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$ 文字目よりアルファベット順で真に小さい。

制約

• $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$ 番目の要素が $(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