题目描述

小 T 最近上班碰到了一个问题，怎么样才能用 Vscode 快速的在 $A$ 里面找有 $C$ 的 $B$。

他想要在代码库的一个文件 $A$ 中，找到有哪些在 $A$ 中使用到的函数 $B$ 间接地调用了小 T 所指定的语句 $C$。由于小 T 的需求比较简单，所以这里不考虑间接调用的函数中的调用关系，只需要看 $B$ 的声明中 $B′$ 是否包含 $C$ 即可。

手动处理这个问题还是有相当大的重复工作量的，但是你是一个经验丰富的SQL BOY/GIRL，你对小 T 说："闹麻了，这不就是把 $A$ 里面包含的 $B$，和包含 $C$ 的 $B$ $\text{JOIN}$ 一下就行了吗。"

虽然是的，但是这两张表哪来呢？

为了圆你吹下的牛，现在你需要手写一个字符串解析器，用来在 $A$ 里面找有 $C$ 的 $B$。

接下来我们会给定一个长字符串 $A$，一个短字符串 $C$，以及 $n$ 个短字符串 $\{B_n\}$，以及其声明 $\{B′_n\}$。

我们定义一个字符串 $S$ 在字符串 $T$ 中当且仅当存在一个 $T$ 的子串 $p$ 满足：$S=p$。

输入格式

第一行输入一个正整数 $T$ ($1≤T≤10$)，表示总共有 $T$ 组数据。

对于每一组测试数据，首先是一个正整数 $n$ ($1≤n≤10^5$)。

接下来是两个由小写字母构成的字符串 $A,C$ ($1≤|A|≤10^5,1≤|C|≤10^4$)

接下来 $n$ 行，每行读入两个由小写字母构成的字符串 $B_i,B′_i$ ($1≤|B_i|≤10^4,1≤|B′_i|≤10^5$)

每组数据中有额外限制如下：$∑|B_i|≤10^5,∑|B′_i|≤5×10^5$

输出格式

对于每一组测试数据，输出一行整数 $i$ 满足 $B_i$ 在 $A$ 中，同时 $B′_i$ 中包含 $C$，相邻的整数之间用空格分割，注意行末不保留空格。

假如答案集合为空，则输出一个空行。

输入样例

2
5
abcde a
a a
b a
c b
d a
e c
5
aaabbbccc xyz
ab xxxyzzzzyy
bccc aaaaxyza
abbbb xxxxyyz
aaaabbbcccc x
a xyzzzzzzzzz

输出样例

1 2 4
1 2 5