# 描述

You have $N$ integers $A_1, A_2, … , A_N$. You are asked to write a program to receive and execute two kinds of instructions:

1. C a b means performing $A_i = (A_i^2 \mod 2018)$ for all $A_i$ such that $a ≤ i ≤ b$.
2. Q a b means query the sum of $A_a, A_{a+1}, …, A_b$. Note that the sum is not taken modulo $2018$.

## 输入描述

The first line of the input is $T$($1≤ T ≤ 20$), which stands for the number of test cases you need to solve.

The first line of each test case contains $N$ ($1 ≤ N ≤ 50000$).The second line contains $N$ numbers, the initial values of $A_1, A_2, …, A_n$. $0 ≤ A_i < 2018$. The third line contains the number of operations $Q$ ($0 ≤ Q ≤ 50000$). The following $Q$ lines represents an operation having the format “C a b” or “Q a b”, which has been described above. $1 ≤ a ≤ b ≤ N$.

## 输出描述

For each test case, print a line “Case #t:” (without quotes, t means the index of the test case) at the beginning.
You need to answer all Q commands in order. One answer in a line.

# 思路

• $2018$这个数非常特殊，每个数平方取模最大周期是$6$。
• 维护一个含六个数的序列的线段树。进入循环之后，每次更新相当于序列移位，可以用lazy标记维护。
• 在进入循环之前，最多会有五次修改，所以维护一个修改次数，在区间的修改次数不足五次时暴力递归到叶子结点即可。

0%