{"raw_statement":[{"iden":"problem statement","content":"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}$.  \nFor 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$.\nA 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:\n\n*   The $M$ elements are pairwise distinct.\n*   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}|$.\n*   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.\n\nYou 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.\nWhat 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:\n\n*   $|S| \\leq |T|$ and $S = T[1, |S|]$.\n*   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$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq \\lvert S_i\\rvert \\leq 10^5$\n*   $\\displaystyle\\sum_{i=1}^N \\lvert S_i\\rvert\\leq 10^5$\n*   $1 \\leq Q \\leq 2\\times 10^5$\n*   $1 \\leq x_1<x_2<\\cdots<x_Q \\leq \\displaystyle\\sum_{i=1}^N \\frac{|S_i|(|S_i|+1)}{2}$\n*   $N,Q,x_1,x_2,\\ldots,x_Q$ are integers.\n*   $S_i$ is a string consisting of lowercase English letters."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S_1$\n$S_2$\n$\\vdots$\n$S_N$\n$Q$\n$x_1$ $x_2$ $\\ldots$ $x_Q$"},{"iden":"sample input 1","content":"2\nabab\ncab\n2\n5 14"},{"iden":"sample output 1","content":"1 3 4\n2 1 1\n\nWe have $M=16$. One possible sequence of triples that satisfies the conditions is $((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))$. The corresponding sequence of $S_{K_i}[L_i, R_i]$ for these $(K_i,L_i, R_i)$ in this order is (`a`, `a`, `a`, `ab`, `ab`, `ab`, `aba`, `abab`, `b`, `b`, `b`, `ba`, `bab`, `c`, `ca`, `cab`).\nNote that the sequence satisfies the conditions even if we swap the $5$\\-th element $(1,3,4)$ with the $4$\\-th or $6$\\-th one, so $(K_{x_1}, L_{x_1}, R_{x_1})=(1,1,2), (2,2,3)$ will also be accepted."},{"iden":"sample input 2","content":"3\na\na\nba\n2\n1 2"},{"iden":"sample output 2","content":"1 1 1\n1 1 1\n\nWe have $M=5$. The sequence of triples that satisfies the conditions can be  \n$(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)$, for example.\nNote that, for $(K_{x_i}, L_{x_i}, R_{x_i})$ that you print, the conforming sequence whose $x_i$\\-th element is $(K_{x_i}, L_{x_i}, R_{x_i})$ does **not** have to be common among different $i$; in other words, there does **not necessarily have to exist** a sequence whose \"$x_i$\\-th element is $(K_{x_i}, L_{x_i}, R_{x_i})$ for all $1\\leq i\\leq Q$.\""},{"iden":"sample input 3","content":"10\ngxgpuamkx\nszhkbpphykin\nezplvfja\nmopodotkrj\nrimlvumuar\nnexcfyce\neurgvjyos\ndhvuyfvt\nnrdyluacvra\nggwnpnzij\n6\n74 268 310 380 455 489"},{"iden":"sample output 3","content":"3 1 2\n4 4 5\n4 3 7\n9 6 6\n6 6 6\n2 2 12"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}