codeforces#P1634F. Fibonacci Additions
Fibonacci Additions
Description
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 > 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$.
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 < MOD$).
The third line also contains $n$ numbers — array $B$ ($0 \le B_i < 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$.
After each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.
Input
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 < MOD$).
The third line also contains $n$ numbers — array $B$ ($0 \le B_i < 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$.
Output
After each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.
Samples
3 5 3
2 2 1
0 0 0
A 1 3
A 1 3
B 1 1
B 2 2
A 3 3
YES
NO
NO
NO
YES
5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2
NO
NO
YES
Note
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]$.