题目描述
N 個の文字列 S1,S2,…, SN が与えられます。 $ 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 ≤ i ≤ M に対して、1 ≤ Ki ≤ N かつ 1 ≤ Li ≤ Ri ≤ ∣SKi∣ である。
- すべての 1 ≤ i ≤ j ≤ M に対して、辞書順で SKi[Li, Ri] ≤ SKj[Lj, Rj] である。
1 以上 M 以下の整数 Q 個 x1,x2,…, xQ が与えられます。各 1 ≤ i ≤ Q に対して、(Kxi, Lxi, Rxi) としてあり得るものを 1 つずつ求めてください。なお、条件をみたす三つ組の列が必ず 1 つ以上存在することが証明できます。条件をみたす三つ組が複数存在する場合、どれを出力しても構いません。また、異なる xi の間で、条件をみたす三つ組の列が共通のものである必要もありません。
辞書順とは 2 つの文字列 S, T が以下の条件のいずれかをみたすとき、かつそのときに限り、辞書順で S ≤ T であると言います。 - ∣S∣ ≤ ∣T∣ かつ S = T[1, ∣S∣] である。
- ある 1≤ k≤ min(∣S∣, ∣T∣) が存在し、1≤ i≤ k−1 について、S と T の i 文字目は等しく、S の k 文字目は T の k 文字目よりアルファベット順で真に小さい。
输入格式
入力は以下の形式で標準入力から与えられる。
N S1 S2 ⋮ SN Q x1 x2 … xQ
输出格式
Q 行出力せよ。i 行目には、条件をみたす (Kxi, Lxi, Rxi) としてあり得るものを空白区切りで出力せよ。 条件をみたす三つ組が複数存在する場合、どれを出力してもよい。
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 ≤ N ≤ 105
- 1 ≤ ∣ Si∣ ≤ 105
- $ \displaystyle\sum_{i=1}^N\ \lvert\ S_i\rvert\leq\ 10^5 $
- 1 ≤ Q ≤ 2× 105
- $ 1\ \leq\ x_1\ <\ x_2\ <\ \cdots\ <\ x_Q\ \leq\ \displaystyle\sum_{i=1}^N\ \frac{|S_i|(|S_i|+1)}{2} $
- N,Q,x1,x2,…,xQ は整数
- Si は英小文字のみからなる文字列
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) $ が考えられます。 この順で並べた時の (Ki,Li, Ri) に対応する SKi[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) も正解となります。
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) が考えられます。 出力する (Kxi, Lxi, Rxi) について、xi 番目の要素が (Kxi, Lxi, Rxi) であるような条件をみたす列は異なる i の間で共通のものである必要が **ない**、 すなわち、「任意の 1≤ i≤ Q について xi 番目の要素が (Kxi, Lxi, Rxi) である」 ような列は **必ずしも存在する必要がない** ことに注意してください。