CF1634F.Fibonacci Additions

One of my most productive days was throwing away 1,000 lines of code.

— Ken Thompson

Fibonacci addition is an operation on an array $X$ of integers, parametrized by indices $l$ and $r$. Fibonacci addition increases $X_l$ by $F_1$, increases $X_{l + 1}$ by $F_2$, and so on up to $X_r$ which is increased by $F_{r - l + 1}$.

$F_i$ denotes the $i$-th Fibonacci number ($F_1 = 1$, $F_2 = 1$, $F_{i} = F_{i - 1} + F_{i - 2}$ for $i \gt 2$), and all operations are performed modulo $MOD$.

You are given two arrays $A$ and $B$ of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays $A$ and $B$ are equal modulo $MOD$.

我最有成效的一天之一，是删掉了 1000 行代码。

— 肯·汤普森（Ken Thompson）

斐波那契加法（Fibonacci addition）是一种作用于整数数组 $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$，且当 $i > 2$ 时 $F_i = F_{i - 1} + F_{i - 2}$），所有运算均在模 $MOD$ 意义下进行。

给定两个等长的数组 $A$ 和 $B$。我们将要求你对这两个数组执行若干次参数不同的斐波那契加法操作；每次操作后，你都需要报告数组 $A$ 与 $B$ 在模 $MOD$ 意义下是否相等。

The first line contains 3 numbers $n$, $q$ and $MOD$ ($1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$) — the length of the arrays, the number of operations, and the number modulo which all operations are performed.

The second line contains $n$ numbers — array $A$ ($0 \le A_i \lt MOD$).

The third line also contains $n$ numbers — array $B$ ($0 \le B_i \lt MOD$).

The next $q$ lines contain character $c$ and two numbers $l$ and $r$ ($1 \le l \le r \le n$) — operation parameters. If $c$ is "A", Fibonacci addition is to be performed on array $A$, and if it is is "B", the operation is to be performed on $B$.

第一行包含三个数字 $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 \lt MOD$）。

第三行也包含 $n$ 个数字——数组 $B$（$0 \le B_i \lt MOD$）。

接下来的 $q$ 行每行包含一个字符 $c$ 和两个数字 $l$、$r$（$1 \le l \le r \le n$）——表示操作参数。若 $c$ 为 "A"，则对数组 $A$ 执行斐波那契加法；若 $c$ 为 "B"，则对数组 $B$ 执行该操作。

After each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.

每次操作后，如果两个数组相等，则输出 "YES"（不带引号），否则输出 "NO"。字母大小写不敏感。

Explanation of the test from the condition:

• Initially $A=[2,2,1]$, $B=[0,0,0]$.
• After operation "A 1 3": $A=[0,0,0]$, $B=[0,0,0]$ (addition is modulo 3).
• After operation "A 1 3": $A=[1,1,2]$, $B=[0,0,0]$.
• After operation "B 1 1": $A=[1,1,2]$, $B=[1,0,0]$.
• After operation "B 2 2": $A=[1,1,2]$, $B=[1,1,0]$.
• After operation "A 3 3": $A=[1,1,0]$, $B=[1,1,0]$.

根据题目的条件对测试样例进行解释：

• 初始时 $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]$。