Ex - Substring Sort Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

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

辞書順とは 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

Score : 600 points

Problem Statement

You are given N strings S_1,S_2,\ldots, S_N. Let M = \displaystyle\sum_{i=1}^N \frac{|S_i|(|S_i|+1)}{2}.
For a string S and integers L and R, let us denote by S[L, R] the substring consisting of the L-th through R-th characters of S.

A sequence of triples of integers ((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M)) of length M satisfies the following conditions:

  • The M elements are pairwise distinct.
  • For all 1 \leq i \leq M, it holds that 1 \leq K_i \leq N and 1 \leq L_i \leq R_i \leq |S_{K_i}|.
  • For all 1 \leq i \leq j \leq M, it holds that S_{K_i}[L_i, R_i] \leq S_{K_j}[L_j, R_j] in the lexicographical order.

You are given Q integers x_1,x_2,\ldots, x_Q between 1 and M, inclusive. For each 1 \leq i \leq Q, find a possible instance of (K_{x_i}, L_{x_i}, R_{x_i}). We can prove that there always exists a sequence of triples that satisfies the conditions. If multiple triples satisfy the conditions, print any of them. In addition, among different x_i's, the conforming sequence of triples does not have to be common.

What is the lexicographical order? Two strings S and T are said to be S \leq T in the lexicographical order if and only if one of the following conditions is satisfied:
  • |S| \leq |T| and S = T[1, |S|].
  • There exists 1\leq k\leq \min(|S|, |T|) such that the i-th characters of S and T are the same for all 1\leq i\leq k-1, and the k-th character of S is alphabetically strictly smaller than that of T.

Constraints

  • 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 are integers.
  • S_i is a string consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N
Q
x_1 x_2 \ldots x_Q

Output

Print Q lines. The i-th line should contain an instance of conforming (K_{x_i}, L_{x_i}, R_{x_i}), separated by spaces. If multiple triples satisfy the conditions, print any of them.

Sample Input 1

2
abab
cab
2
5 14

Sample Output 1

1 3 4
2 1 1

We have M=16. One possible sequence of triples that satisfies the conditions is ((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)). The corresponding sequence of S_{K_i}[L_i, R_i] for these (K_i,L_i, R_i) in this order is (a, a, a, ab, ab, ab, aba, abab, b, b, b, ba, bab, c, ca, cab).

Note that the sequence satisfies the conditions even if we swap the 5-th element (1,3,4) with the 4-th or 6-th one, so (K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3) will also be accepted.

Sample Input 2

3
a
a
ba
2
1 2

Sample Output 2

1 1 1
1 1 1

We have M=5. The sequence of triples that satisfies the conditions can be
(1,1,1), (2,1,1), (3,2,2), (3,1,1), (3,1,2) or (2,1,1), (3,2,2), (1,1,1), (3,1,1), (3,1,2), for example.

Note that, for (K_{x_i}, L_{x_i}, R_{x_i}) that you print, the conforming sequence whose x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) does not have to be common among different i; in other words, there does not necessarily have to exist a sequence whose "x_i-th element is (K_{x_i}, L_{x_i}, R_{x_i}) for all 1\leq i\leq Q."

Sample Input 3

10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489

Sample Output 3

3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12