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_QOutput
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.
样例
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
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。