F. Прибавления Фибоначчи
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
One of my most productive days was throwing away 1,000 lines of code.
— Ken Thompson

Прибавление Фибоначчи — это операция на массиве $$$X$$$ целых чисел, параметризованная индексами $$$l$$$ и $$$r$$$. При применении этой операции к $$$X_l$$$ прибавляется $$$F_1$$$, к $$$X_{l + 1}$$$ прибавляется $$$F_2$$$, и так далее, вплоть до числа $$$X_r$$$, которое увеличивается на $$$F_{r - l + 1}$$$.

Здесь $$$F_i$$$ — это $$$i$$$-е число Фибоначчи ($$$F_1 = 1$$$, $$$F_2 = 1$$$, $$$F_{i} = F_{i - 1} + F_{i - 2}$$$ для $$$i > 2$$$), и все операции производятся по модулю $$$MOD$$$.

Вам даны массивы $$$A$$$ и $$$B$$$ одинаковой длины. Мы просим вас применить к этим массивам несколько операций прибавления Фибоначчи с разными параметрами. После каждой операции вы должны сообщить, равны ли массивы $$$A$$$ и $$$B$$$ (по модулю $$$MOD$$$).

Входные данные

В первой строке вводится 3 числа $$$n$$$, $$$q$$$ и $$$MOD$$$ ($$$1 \le n, q \le 3\cdot 10^5, 1 \le MOD \le 10^9+7$$$) — длина массивов, количество операций и модуль, по которому выполняются все операции.

Во второй строке находится $$$n$$$ чисел — массив $$$A$$$ ($$$0 \le A_i < MOD$$$).

В третей строке находится $$$n$$$ чисел — массив $$$B$$$ ($$$0 \le B_i < MOD$$$).

В последующих $$$q$$$ строках находится символ $$$c$$$ и два числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — параметры операции. Символ $$$c$$$, равный «A», означает, что прибавление Фибоначчи нужно применить к массиву $$$A$$$, равный «B» — к массиву $$$B$$$.

Выходные данные

После каждой операции выведите «YES» (без кавычек), если массивы равны, и «NO» иначе. Ответ можно выводить в любом регистре.

Примеры
Входные данные
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
Входные данные
5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2
Выходные данные
NO
NO
YES
Примечание

Пояснение к тесту из условия:

  • Изначально $$$A=[2,2,1]$$$, $$$B=[0,0,0]$$$.
  • После операции «A 1 3»: $$$A=[0,0,0]$$$, $$$B=[0,0,0]$$$ (сложение производится по модулю 3).
  • После операции «A 1 3»: $$$A=[1,1,2]$$$, $$$B=[0,0,0]$$$.
  • После операции «B 1 1»: $$$A=[1,1,2]$$$, $$$B=[1,0,0]$$$.
  • После операции «B 2 2»: $$$A=[1,1,2]$$$, $$$B=[1,1,0]$$$.
  • После операции «A 3 3»: $$$A=[1,1,0]$$$, $$$B=[1,1,0]$$$.