分数: 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