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$.

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.

见题面 Input 部分

见题面 Output 部分

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]$.