AT_abc280_h [ABC280Ex] Substring Sort

给定 $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]$（按字典序比较）。 给定 $Q$ 个整数 $x_1, x_2, \ldots, x_Q$，其中 $1 \leq x_1 < x_2 < \cdots < x_Q \leq 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|)$，对于所有 $1 \leq i \leq k-1$，$S$ 和 $T$ 的第 $i$ 个字符相等，且 $S$ 的第 $k$ 个字符在字母表中严格小于 $T$ 的第 $k$ 个字符。

输入按以下格式从标准输入给出。 > $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 \leq N \leq 10^5$ - $1 \leq |S_i| \leq 10^5$ - $\displaystyle\sum_{i=1}^N |S_i| \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$ 仅由小写英文字母组成 ### 样例解释 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]$ 为（`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 $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$ 对应的三元组来自同一个满足条件的序列。 由 ChatGPT 4.1 翻译