F. Fibonacci Additionstime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputOne of my most productive days was throwing away 1,000 lines of code.— Ken ThompsonFibonacci 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.InputThe 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.OutputAfter each operation, print "YES" (without quotes) if the arrays are equal and "NO" otherwise. Letter case does not matter.ExamplesInput
3 5 3
2 2 1
0 0 0
A 1 3
A 1 3
B 1 1
B 2 2
A 3 3
Output
YES
NO
NO
NO
YES
Input
5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2
Output
NO
NO
YES
NoteExplanation 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].
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 
['brute force', 'data structures', 'hashing', 'implementation', 'math', '*2700']