Fibonacci Additions

题意翻译

## 题目描述 对于一个数组 $X$，有如下操作：对于区间 $[l,r]$，给 $X_l$ 加上 $F_1$，给 $X_{l+1}$ 加上 $F_2$，以此类推，并且给 $X_r$ 加上 $F_{r-l+1}$。然后将区间 $[l,r]$ 内每个数对 $MOD$ 取模。$F$ 数组是这样一个数组：$F_1=1$，$F_2=1$，当 $i>2$ 时 $F_i=F_{i-1}+F_{i-2}$。 已知两个长度相同的数组 $A$，$B$，给出若干次操作，每次操作后你需要求出取模过后的数组 $A$，$B$ 是否相等。 ## 输入格式 第一行包含三个整数 $n$，$q$，$MOD$，分别表示该数组数字的个数、操作的总个数和模数。 第二行包含 $A$ 数组的 $n$ 个数。 第三行包含 $B$ 数组的 $n$ 个数。 接下来 $q$ 行，每行包含一个字符 $c$，两个数字 $l$，$r$。如果 $c$ 是`A`，表示在 $A$ 数组上操作。如果 $c$ 是`B`，表示在 $B$ 数组上操作。 ## 输出格式 共有 $q$ 行，每次操作后，如果取模过后的数组 $A$，$B$ 相同，则输出一行 `YES`，否则输出一行 `NO`。

题目描述

One of my most productive days was throwing away 1,000 lines of code. — Ken Thompson 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.

输入输出样例

输入样例 #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

输出样例 #1

YES
NO
NO
NO
YES

输入样例 #2

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

输出样例 #2

NO
NO
YES

说明

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