J 喜欢弹电吉他，尤其是著名的 Gibson SG Standard 吉他。他总是用他的 Gibson SG Standard 创作音乐。

他创作的曲子由若干音符组成。形式上，曲子可以看作是一个仅由小写字母组成的字符串。不同的字母代表不同的音符。曲子的子串被称为乐句（phrase）。

起初，J 有一个长度为 $n$ 的曲子。为了创作新音乐，J 有三种操作：

• 1 c：在当前曲子的末尾插入一个音符 $c$。
• 2：删除当前曲子开头的音符。
• 3 t：查询乐句 $t$ 在当前曲子中出现的次数。

现在，J 正忙于他的新专辑，并邀请你一起创作音乐。你能帮帮他吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。对于每个测试用例：

第一行包含一个长度为 $n$ ($1 \le n \le 10^5$) 的字符串 $S$，表示初始曲子。

下一行包含一个整数 $m$ ($1 \le m \le 10^5$)，表示操作数量。

接下来的 $m$ 行，第 $i$ 行包含一个操作，格式为 1 c'、2 或 3 t'。

定义上一次的查询结果为 $lastans$。初始时，$lastans = 0$。

• 对于 1 c'，实际操作的字符为 $c = ((c' - 'a') \oplus lastans) \pmod{26} + 'a'$。
• 对于 3 t'，实际操作的字符串 $t$ 的每一位为 $t_i = ((t'_i - 'a') \oplus lastans) \pmod{26} + 'a'$。

保证 $c'$ 是一个小写字母，$t'$ 是一个仅由小写字母组成的字符串。所有测试用例中 $t$ 的长度之和不超过 $5 \times 10^6$。

注意，字符串 $S$ 可能会被删为空串。但保证此时不会有类型为 2 的操作。

输出格式

对于每个 3 t 查询，输出一行一个整数，表示答案。

样例

输入 1

1
abcbaba
5
3 ab
3 c
1 a
2
3 da

输出 1

2
3
1