题目描述

维护两个字符串集合 $S,T$，一开始 $S$ 和 $T$ 里都只有一个空串，编号都为 $1$，要求支持操作：

• 1 i c ，在 $S_i$ 的末尾加入一个字符 $c$，加入 $S$。
• 2 0 i c ，在 $T_i$ 的开头加入一个字符 $c$，加入 $T$。
• 2 1 i c，在 $T_i$ 的末尾加入一个字符 $c$，加入 $T$。
• 3 i j ，把 $T_i$ 和 $T_j$ 拼起来，加入 $T$。
• 4 i j，询问 $T_i$ 在 $S_j$ 中的出现次数，如果其中任意一个串是空串，那么答案是 $0$。

输入格式

第一行一个整数 $q$，表示操作次数。
接下来每行一个操作，格式见题目描述。

输出格式

对于每个询问操作 $4$，输出一行一个整数表示答案。

18
1 1 a
1 2 a
1 3 b
1 2 b
1 5 a
1 5 b
2 1 1 a
3 2 2
2 0 3 b
2 1 2 b
3 2 5
3 5 2
4 7 6
4 5 6
4 3 4
4 2 4
4 2 7
4 2 6

1
1
1
2
1
2

数据规模与约定

对于 $100\%$ 的数据，$1\leq q\leq 3\times 10^5$，$c$ 是小写字母，$1$ 操作个数不超过 $10^5$，$3$ 操作个数不超过 $3\times 10^4$，$4$ 操作个数不超过 $10^5$。