在 A 里面找有 C 的 B

Problem Description

小 T 最近上班碰到了一个问题，怎么样才能用 Vscode 快速的在 A 里面找有 C 的 B。 他想要在代码库的一个文件 $A$ 中，找到有哪些在 $A$ 中使用到的函数 $B$ 间接地调用了小 T 所指定的语句 $C$。由于小 T 的需求比较简单，所以这里不考虑间接调用的函数中的调用关系，只需要看 $B$ 的声明中 $B'$ 是否包含 $C$ 即可。 手动处理这个问题还是有相当大的重复工作量的，但是你是一个经验丰富的SQL BOY/GIRL，你对小 T 说："闹麻了，这不就是把 A 里面包含的 B，和包含 C 的 B JOIN 一下就行了吗。" 虽然是的，但是这两张表哪来呢？ 为了圆你吹下的牛，现在你需要手写一个字符串解析器，用来在 A 里面找有 C 的 B。 接下来我们会给定一个长字符串 $A$，一个短字符串 $C$，以及 $n$ 个短字符串 $\{B_n\}$，以及其声明 $\{B'_n\}$。 我们定义一个字符串 $S$ 在字符串 $T$ 中当且仅当存在一个 $T$ 的子串 $p$ 满足：$S=p$。

Input

第一行输入一个正整数 $T$ ($1\le T\le 10$)，表示总共有 $T$ 组数据。 对于每一组测试数据，首先是一个正整数 $n$ ($1\le n \le 10^5$)。 接下来是两个由小写字母构成的字符串 $A$,$C$ ($1\le |A| \le 10^5$,$1\le |C| \le 10^4$) 接下来 $n$ 行，每行读入两个由小写字母构成的字符串 $B_i$,$B'_i$ ($1\le |B_i|\le 10^4,1\le |B_i'|\le 10^5$) 每组数据中有额外限制如下：$\sum |B_i| \le 10^5,\sum |B_i'|\le 5\times 10^5$

Output

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

Sample Input

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

Sample Output

1 2 4
1 2 5

Source

2024“钉耙编程”中国大学生算法设计超级联赛（2）