A Simple Problem with Integers
如果能发现对每个数多次操作后结果会存在循环节，就可以知道线段树该维护什么了。

void init() {
	for(int i = 1; i < 2018; i++) {
		int p = i;
		for(int j = 0; j < 15; j++) {
			cc[i][j] = p;
			p = p*p%2018;
		}
	}
}

循环节并不是从开始就存在的，可能从第四位开始也可能从第三位开始，然后循环节的长度为6.
我们对于每次更新先暴力更新叶子节点，当叶子节点进入循环节之后我们就标记一下。如果一个区间的左右区间都被标记，也就是说对左右区间我们已经知道循环节了，我们可以合并两个循环节成一个大区间的循环节。
然后我们就可以快速查找区间信息了。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
int Case = 1;
int n, m;
struct node{
	int l, r;
	int mid() {
		return (l+r)/2;
	}
	ll flag, pos, lz, sum;
	int val[7];
}tr[maxn<<2];
int cc[3000][20];
void init() {
	for(int i = 1; i < 2018; i++) {
		int p = i;
		for(int j = 0; j < 15; j++) {
			cc[i][j] = p;
			p = p*p%2018;
		}
	}
}
int num[maxn];
void pushup(int rt) {
	if(tr[rt<<1].flag && tr[rt<<1|1].flag) {
		tr[rt].flag = 1;
		tr[rt].pos = 0;
		for(int i = 0; i < 6; i++) {
			tr[rt].val[i] = tr[rt<<1].val[(tr[rt<<1].pos+i)%6] + tr[rt<<1|1].val[(tr[rt<<1|1].pos+i)%6];
		}
	}
	tr[rt].sum = tr[rt<<1].sum + tr[rt<<1|1].sum;
}

void build(int rt, int l, int r) {
	tr[rt].l = l;tr[rt].r = r;
	tr[rt].flag = tr[rt].pos = tr[rt].lz = tr[rt].sum = 0;
	if(l == r) {
		scanf("%lld", &tr[rt].sum);
		for(int i = 0; i < 6; i++) {
			tr[rt].val[i] = cc[tr[rt].sum][i+4];
		}
		return;
	}
	int mid = tr[rt].mid();
	build(rt<<1, l, mid);
	build(rt<<1|1, mid+1, r);
	pushup(rt);
}

void pushdown(int rt) {
	if(tr[rt].lz) {
		ll &x = tr[rt].lz;
		tr[rt<<1].lz = (tr[rt<<1].lz+x)%6;
		tr[rt<<1|1].lz = (tr[rt<<1|1].lz+x)%6;
		tr[rt<<1].sum = tr[rt<<1].val[tr[rt<<1].pos = (tr[rt<<1].pos+x)%6];
		tr[rt<<1|1].sum = tr[rt<<1|1].val[tr[rt<<1|1].pos = (tr[rt<<1|1].pos+x)%6];
		x = 0;
	}
}

void update(int rt, int l, int r) {
	if(tr[rt].l == l && r == tr[rt].r) {
		if(tr[rt].flag) {
			tr[rt].lz = (tr[rt].lz+1)%6;
			tr[rt].sum = tr[rt].val[tr[rt].pos = (tr[rt].pos+1)%6];
			return;
		}
		if(l == r) {
			num[l]++;
			tr[rt].sum = tr[rt].sum*tr[rt].sum%2018;
			if(num[l] == 4) tr[rt].flag = 1;
			return;
		}
	}
	pushdown(rt);
	int mid = tr[rt].mid();
	if(r <= mid) update(rt<<1, l, r);
	else if(l > mid)update(rt<<1|1, l, r);
	else update(rt<<1, l, mid), update(rt<<1|1, mid+1, r);
	pushup(rt);
}

ll query(int rt, int l, int r) {
	if(tr[rt].l == l && tr[rt].r == r) {
		return tr[rt].sum;
	}
	pushdown(rt);
	int mid = tr[rt].mid();
	if(r <= mid) return query(rt<<1, l, r);
	else if(l > mid) return query(rt<<1|1, l, r);
	else return query(rt<<1, l, mid) + query(rt<<1|1, mid+1, r);
}

void solve() {
	static int T = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) num[i] = 0;
    build(1, 1, n);
    scanf("%d", &m);
    printf("Case #%d:\n", ++T);
    for(int i = 1; i <= m; i++) {
    	char op[2];int l, r;scanf("%s%d%d", op, &l, &r);
    	if(op[0] == 'C') update(1, l, r);
    	else printf("%lld\n", query(1, l, r));
    }
    return;
}

int main() {
	init();
    scanf("%d", &Case);
    while(Case--) {
        solve();
    }
    return 0;
}