← 返回题目列表

AtCoder · codefestival_2016_qualB_e

E. 词典编序混乱

中文机器翻译题面 查看原题

分数: 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