斐波那契加法是对整数数组 $$$X$$$ 的运算,由索引 $$$l$$$ 和 $$$r$$$ 参数化。斐波那契加法将 $$$X_l$$$ 增加 $$$F_1$$$,将 $$$X_{l + 1}$$$ 增加 $$$F_2$$$,依此类推,直到 $$$X_r$$$ 增加 $$$F_{r - l + 1}$$$。
$$$F_i$$$ 表示第 $$$i$$$ 个斐波那契数($$$F_1 = 1$$$、$$$F_2 = 1$$$、$$$F_{i} = F_{i - 1} + F_{i - 2}$$$ for $$$i > 2$$$),并且所有操作均以模进行$$$MOD$$$。
给定两个长度相同的数组 $$$A$$$ 和 $$$B$$$。我们将要求您使用不同的参数对这些数组执行几次斐波那契加法,每次操作后您必须报告数组 $$$A$$$ 和 $$$B$$$ 是否等于对 $$$MOD$$$ 取模。
输入
第一行包含 3 个数字 $$$n$$$、$$$q$$$ 和 $$$MOD$$$ ($$$1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$$$) — 数组的长度、运算次数以及所有运算执行的模数。
第二行包含 $$$n$$$ 数字 — 数组 $$$A$$$ ($$$0 \le A_i < MOD$$$)。
第三行还包含 $$$n$$$ 数字 — 数组 $$$B$$$ ($$$0 \le B_i < MOD$$$)。
接下来的 $$$q$$$ 行包含字符 $$$c$$$ 和两个数字 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 操作参数。如果$$$c$$$为“A”,则对数组$$$A$$$进行斐波那契加法运算,如果为“B”,则对$$$B$$$进行斐波那契加法运算。
输出
每次操作后,如果数组相等则打印“YES”(不带引号),否则打印“NO”。字母大小写无关紧要。
示例
输入 #1
3 5 3 2 2 1 0 0 0 A 1 3 A 1 3 B 1 1 B 2 2 A 3 3
输出 #1
YES NO NO NO YES
输入 #2
5 3 10 2 5 0 3 5 3 5 8 2 5 B 2 3 B 3 4 A 1 2
输出 #2
NO NO YES
注意
条件测试说明:
- 最初$$$A=[2,2,1]$$$,$$$B=[0,0,0]$$$。
- 运算“A 1 3”后:$$$A=[0,0,0]$$$,$$$B=[0,0,0]$$$(加法以 3 为模)。
- 操作“A 1 3”后:$$$A=[1,1,2]$$$,$$$B=[0,0,0]$$$。
- 操作“B 1 1”后:$$$A=[1,1,2]$$$,$$$B=[1,0,0]$$$。
- 操作“B 2 2”后:$$$A=[1,1,2]$$$,$$$B=[1,1,0]$$$。
- 操作“A 3 3”后:$$$A=[1,1,0]$$$,$$$B=[1,1,0]$$$。