Wowo's Sequence

Problem Background

Original problem: CF1634F

Some meaningless strengthening has been applied.

Problem Description

Wowo has two sequences $A$ and $B$, both of length $n$, and will perform $q$ operations.

In each operation, he first chooses one of the sequences ($A$ or $B$), then chooses an interval $[l, r]$ ($1 \le l \le r \le n$), and adds the Fibonacci sequence to that interval element-wise.

In other words, he adds $1$ to the $l$-th element, $1$ to the $(l+1)$-th element, $2$ to the $(l+2)$-th element, $3$ to the $(l+3)$-th element, and so on, up to adding $\operatorname{Fib}(r-l+1)$ — the $(r-l+1)$-th Fibonacci number — to the $r$-th element.

At the end of each operation Wowo becomes very curious. He wants to know whether $A$ and $B$ are now equal. Since he gets dizzy looking at long numbers, you only need to tell whether $A$ and $B$ are equal modulo $M$.

Input Format

The first line contains three integers $n, q, M$, the sequence length, the total number of operations, and the modulus.

The second and third lines each contain $n$ integers, the initial values of $A$ and $B$.

The next $q$ lines each contain a character $c$ and two integers $l, r$, describing one operation. See the samples for details.

Output Format

Output $q$ lines, each containing the string Yes or No, indicating whether the two sequences are equal modulo $M$ at that moment.

Sample Input 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

Sample Output 1

Yes
No
No
No
Yes

Sample Input 2

5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2

Sample Output 2

No
No
Yes

Constraints

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le q \le 10^6$, $1 \le M \le 10^9+7$, and for $1 \le i \le n$, $0 \le |A_i|, |B_i| \le 10^9$.