Problem8282--ABC280 —— Ex - Substring Sort

8282: ABC280 —— Ex - Substring Sort

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 2StatisticsShowOff!

Description

You are given $N$ strings $S_1,S_2,…,S_N$. Let $M=\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),…,(K_M,L_M,R_M))$ of length M satisfies the following conditions:
  • The M elements are pairwise distinct.
  • For all $1≤i≤M$, it holds that $1≤K_i≤N$ and $1≤L_i≤R_i≤∣S_{K_i}∣$.
  • For all $1≤i≤j≤M$, it holds that $S_{K_i}[L_i,R_i]≤S_{K_j}[L_j,R_j]$ in the lexicographical order.
You are given $Q$ integers $x_1,x_2,…,x_Q$ between $1$ and $M$, inclusive. For each $1≤i≤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.

Input

The input is given from Standard Input in the following format:
$N$
$S_1$
$S_2$
$⋮$
$S_N$
$Q$
$x_1\ x_2\ …\ x_Q$

Output

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.

Constraints

$1≤N≤10^5$
$1≤∣S_i∣≤10^5$
$\sum_{i=1}^N ∣S_i∣≤10^5$
$1≤Q≤2×10^5$
$1≤x_1<x_2<⋯<x_Q≤\sum_{i=1}^N \frac{∣S_i∣(∣S_i∣+1)}{2}$
$N,Q,x_1,x_2,…,x_Q$ are integers.
$S_i$ is a string consisting of lowercase English letters.

Sample 1 Input 

2
abab
cab
2
5 14

Sample 1 Output 

1 3 4
2 1 1
We 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).
Note that the sequence satisfies the conditions even if we swap the 5-th element (1,3,4) with the 4-th or 66-th one, so $(K_{x_1},L_{x_1},R_{x_1})=(1,1,2),(2,2,3)$ will also be accepted.

Sample 2 Input 

3
a
a
ba
2
1 2

Sample 2 Output 

1 1 1
1 1 1
We have M=5. The sequence of triples that satisfies the conditions can be
(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)

Sample 3 Input 

10
gxgpuamkx
szhkbpphykin
ezplvfja
mopodotkrj
rimlvumuar
nexcfyce
eurgvjyos
dhvuyfvt
nrdyluacvra
ggwnpnzij
6
74 268 310 380 455 489

Sample 3 Output 

3 1 2
4 4 5
4 3 7
9 6 6
6 6 6
2 2 12

Source/Category

 
Submit