Fibonacci Additions codeforces solution – Java, Python, C++

Fibonacci addition is an operation on an array 𝑋X of integers, parametrized by indices 𝑙l and 𝑟r. Fibonacci addition increases 𝑋𝑙Xl by 𝐹1F1, increases 𝑋𝑙+1Xl+1 by 𝐹2F2, and so on up to 𝑋𝑟Xr which is increased by 𝐹𝑟𝑙+1Fr−l+1.

𝐹𝑖Fi denotes the 𝑖i-th Fibonacci number (𝐹1=1F1=1𝐹2=1F2=1𝐹𝑖=𝐹𝑖1+𝐹𝑖2Fi=Fi−1+Fi−2 for 𝑖>2i>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𝑛,𝑞3105,1𝑀𝑂𝐷109+71≤n,q≤3⋅105,1≤MOD≤109+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𝐴𝑖<𝑀𝑂𝐷0≤Ai<MOD).

The third line also contains 𝑛n numbers — array 𝐵B (0𝐵𝑖<𝑀𝑂𝐷0≤Bi<MOD).

The next 𝑞q lines contain character 𝑐c and two numbers 𝑙l and 𝑟r (1𝑙𝑟𝑛1≤l≤r≤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.

Examples
input

Copy
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

Copy
YES
NO
NO
NO
YES
input

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

Copy
NO
NO
YES
Note

Explanation of the test from the condition:

  • Initially 𝐴=[2,2,1]A=[2,2,1]𝐵=[0,0,0]B=[0,0,0].
  • After operation “A 1 3”: 𝐴=[0,0,0]A=[0,0,0]𝐵=[0,0,0]B=[0,0,0] (addition is modulo 3).
  • After operation “A 1 3”: 𝐴=[1,1,2]A=[1,1,2]𝐵=[0,0,0]B=[0,0,0].
  • After operation “B 1 1”: 𝐴=[1,1,2]A=[1,1,2]𝐵=[1,0,0]B=[1,0,0].
  • After operation “B 2 2”: 𝐴=[1,1,2]A=[1,1,2]𝐵=[1,1,0]B=[1,1,0].
  • After operation “A 3 3”: 𝐴=[1,1,0]A=[1,1,0]𝐵=[1,1,0]B=[1,1,0].

 

Leave a Comment