問題文
N 個の文字列 S1,S2,ldots,SN が与えられます。 M=displaystylesumi=1Nfrac∣Si∣(∣Si∣+1)2 とおきます。
また、文字列 S と整数 L,R に対し、SL,R で S の L 文字目から R 文字目までの文字からなる部分文字列を表します。
整数の三つ組からなる長さ M の列 ((K1,L1,R1),(K2,L2,R2),ldots,(KM,LM,RM)) は以下の条件をみたします:
- M 個の要素は相異なる。
- すべての 1leqileqM に対して、1leqKileqN かつ 1leqLileqRileq∣SKi∣ である。
- すべての 1leqileqjleqM に対して、辞書順で S_{K_i}Li,Ri \\leq S_{K_j}Lj,Rj である。
1 以上 M 以下の整数 Q 個 x1,x2,ldots,xQ が与えられます。各 1leqileqQ に対して、(Kxi,Lxi,Rxi) としてあり得るものを 1 つずつ求めてください。なお、条件をみたす三つ組の列が必ず 1 つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる xi の間で、条件をみたす三つ組の列が共通のものである必要もありません。
辞書順とは 2 つの文字列 S,T が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で SleqT であると言います。
- ∣S∣leq∣T∣ かつ S = T1,∣S∣ である。
- ある 1leqkleqmin(∣S∣,∣T∣) が存在し、1leqileqk−1 について、S と T の i 文字目は等しく、S の k 文字目は T の k 文字目よりアルファベット順で真に小さい。
制約
- 1leqNleq105
- 1leqlvertSirvertleq105
- displaystylesumi=1NlvertSirvertleq105
- 1leqQleq2times105
- 1leqx1<x2<cdots<xQleqdisplaystylesumi=1Nfrac∣Si∣(∣Si∣+1)2
- N,Q,x1,x2,ldots,xQ は整数
- Si は英小文字のみからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N
S1
S2
vdots
SN
Q
x1 x2 ldots xQ
出力
Q 行出力せよ。i 行目には、条件をみたす (Kxi,Lxi,Rxi) としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。
入力例 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) が考えられます。 この順で並べた時の (Ki,Li,Ri) に対応する S_{K_i}Li,Ri の列は、(a
, a
, a
, ab
, ab
, ab
, aba
, abab
, b
, b
, b
, ba
, bab
, c
, ca
, cab
)となります。
なお、5 番目の要素 (1,3,4) を、4 番目や 6 番目の要素と入れ替えた列も条件をみたすため、 (Kx1,Lx1,Rx1)=(1,1,2),(2,2,3) も正解となります。
入力例 2
出力例 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) が考えられます。
出力する (Kxi,Lxi,Rxi) について、xi 番目の要素が (Kxi,Lxi,Rxi) であるような条件をみたす列は異なる i の間で共通のものである必要が ない、 すなわち、「任意の 1leqileqQ について xi 番目の要素が (Kxi,Lxi,Rxi) である」 ような列は 必ずしも存在する必要がない ことに注意してください。
入力例 3
出力例 3