多次进行加法运算是一项耗时的任务，因此你想制造一个机器人。该机器人内存中应有一个长度为 $N$ 的字符串 $S = S_1S_2 \dots S_N$，代表加法指令。字符串中的每个字符 $S_i$ 要么是 'A'，要么是 'B'。

你需要对机器人执行 $Q$ 条指令，每条指令属于以下类型之一：

• $1 \ L \ R$：机器人应翻转 $L \le i \le R$ 范围内的所有字符 $S_i$。翻转字符意味着如果它之前是 'B'，则将其变为 'A'；如果它之前是 'A'，则将其变为 'B'。
• $2 \ L \ R \ A \ B$：机器人应调用 $f(L, R, A, B)$ 并返回两个整数，定义如下面的伪代码所示：

function f(L, R, A, B):
FOR i from L to R
if S[i] = ’A ’
A = A + B
else
B = A + B
return (A, B)

你需要实现机器人的预期行为。

输入格式

输入的第一行包含两个整数：$N$ 和 $Q$ ($1 \le N, Q \le 100\,000$)，分别代表机器人内存中的字符数和指令数。下一行包含一个长度为 $N$ 的字符串 $S$（每个字符均为 'A' 或 'B'），代表机器人内存中的初始字符串。接下来的 $Q$ 行，每行包含一条以下类型的指令：

• $1 \ L \ R$ ($1 \le L \le R \le N$)
• $2 \ L \ R \ A \ B$ ($1 \le L \le R \le N; 0 \le A, B \le 10^9$)

保证至少有一条第二类型的指令。

输出格式

对于输入中出现的每一条第二类型指令，按顺序输出一行，包含两个整数（用单个空格分隔），分别为 $f(L, R, A, B)$ 返回的 $A$ 和 $B$ 的值。由于输出可能很大，你需要将结果对 $1\,000\,000\,007$ 取模。

样例

样例输入 1

5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000

样例输出 1

11 3
0 1000000000

说明

对于第一条指令，调用 $f(L, R, A, B)$ 的过程如下：

• 初始时，$A = 1$ 且 $B = 1$。
• 在 $i = 1$ 结束时，$A = 2$ 且 $B = 1$。
• 在 $i = 2$ 结束时，$A = 2$ 且 $B = 3$。
• 在 $i = 3$ 结束时，$A = 5$ 且 $B = 3$。
• 在 $i = 4$ 结束时，$A = 8$ 且 $B = 3$。
• 在 $i = 5$ 结束时，$A = 11$ 且 $B = 3$。

因此，$f(L, R, A, B)$ 将返回 $(11, 3)$。

对于第二条指令，字符串 $S$ 将被更新为 “ABBBB”。

对于第三条指令，$A$ 的值始终为 $0$，$B$ 的值始终为 $1\,000\,000\,000$。 因此，$f(L, R, A, B)$ 将返回 $(0, 1\,000\,000\,000)$。