问题陈述

给定 $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$ 个介于 $1$ 和 $M$（包含）之间的整数 $x_1,x_2,\\ldots, x_Q$。对于每个 $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$ 个字符。

约束条件

• $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})$，满足条件的序列并不需要在不同的 $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