← 返回题目列表

AtCoder · abc280_h

Ex. 子串排序

中文机器翻译题面 查看原题

分数: 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] 组成的子字符串 L-th 通过 R第一个字符 S.

整数三元组序列 ((K_1, L_1, R_1), (K_2, L_2, R_2), \ldots, (K_M, L_M, R_M)) 长度 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] 按字典顺序排列。

你被给予 Q 整数 x_1,x_2,\ldots, x_Q 之间 1 和 M,包括在内。 对于每个 1 \leq i \leq Q,找到一个可能的实例 (K_{x_i}, L_{x_i}, R_{x_i})。 我们可以证明,总是存在满足条件的三元组序列。 如果多个三元组满足条件,则打印其中任何一个。 此外,不同之间 x_i的,三元组的一致序列不必是公共的。

字典顺序是什么? 两个字符串 S 和 T 据说是 S \leq T 按字典顺序排列当且仅当满足以下条件之一:
  • |S| \leq |T| 和 S = T[1, |S|].
  • 存在 1\leq k\leq \min(|S|, |T|) 这样 i第一个字符 S 和 T 对所有人来说都是相同的 1\leq i\leq k-1,以及 k- 第一个字符 S 按字母顺序严格小于 T.

约束

  • 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-th 行应包含符合条件的实例 (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))。 对应的序列为 S_{K_i}[L_i, R_i] 对于这些 (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-th 或 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) or (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; 换句话说,确实有 不一定必须存在 一个序列 谁的“x_i第一个元素是 (K_{x_i}, L_{x_i}, R_{x_i}) 对于所有人 1\leq i\leq Q."


示例输入 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