分数: 1100 点
问题陈述
有 N 仅限小写字母字符串。 i- 第一个字符串是 S_i。每根弦都是独一无二的。
提供以下问题的答案 Q 查询如下。 i-th 查询具有以下格式:
查询:一个整数 k_i 和一个字符串 p_{i,1}p_{i,2}...p_{i,26} 是由排列 {
给出了a,b,...,z}。输出字符串的序列 S_{k_i} 其中 N 当文字序列为时按字典顺序排列的字符串 p_{i,1}<p_{i,2}<...<p_{i,26}.
约束
- 1 ≦ N,Q ≦ 100000
- 1 ≦ |S_i| (1 ≦ i ≦ N)
- S_i (1 ≦ i ≦ N) 是一串小写字母。
- 总和 |S_i| 不超过 400000.
- 每 S_i 是独一无二的。
- 1 ≦ k_i ≦ N (1 ≦ i ≦ Q)
- 对于所有 1 ≦ i ≦ Q, p_{i,1}p_{i,2}...p_{i,26} 是一个排列
abcd...z.
输入
输入由以下形式的标准输入提供。
N
S_1
:
S_N
Q
k_1 p_{1,1}p_{1,2}...p_{1,26}
:
k_Q p_{Q,1}p_{Q,2}...p_{Q,26}
输出
输出 Q 行。
上线 i,对于 i-第一个查询,输出一个整数,表示字符串的顺序 S_{k_i} 其中 N 按字典顺序排列的字符串。
示例输入 1
5 aa abbaa abbba aaab aaaaaba 5 1 abcdefghijklmnopqrstuvwxyz 2 bacdefghijklmnopqrstuvwxyz 3 abcdefghijklmnopqrstuvwxyz 4 bacdefghijklmnopqrstuvwxyz 5 abcdefghijklmnopqrstuvwxyz
示例输出 1
1 2 5 4 2
当文字序列为 a < b,按字典顺序对输入字符串进行排序会产生 aa, aaaaaba, aaab, abbaa, abbba。查询的答案 1, 3,和 5 因此 1, 5,和 2。
当文字序列为 b < a,按字典顺序对输入字符串进行排序会产生 abbba, abbaa, aa, aaab, aaaaaba。查询的答案 2 和 4 因此 2 和 4。
示例输入 2
8 abrakatabra abadaba abracadabra atcoder grand contest ababa a 6 3 abcdefghijklmnopqrstuvwxyz 6 qwertyuiopasdfghjklzxcvbnm 8 poiuytrewqlkjhgfdsamnbvcxz 2 qazwsxedcrfvtgbyhnujmikolp 1 plokmijnuhbygvtfcrdxeszwaq 4 mnbvcxzasdfghjklpoiuytrewq
示例输出 2
4 8 2 3 4 7