[Lydsy2017年4月月赛]平方计数器

时间限制:40s      空间限制:128MB

题目描述

给定一个长度为n的非负整数序列a_1,a_2,?,a_n,你需要支持以下三种类型的操作:
1.给定l,r,满足1≤l≤r≤n,将a_l,a_(l+1),?,a_r依次修改为a_l^2,a_(l+1)^2,?,a_r^2。
2.给定l,r,x,满足1≤l≤r≤n,0≤x<2017,将a_l,a_(l+1),?,a_r分别修改为x。
3.给定l,r,满足1≤l≤r≤n,统计a_l,a_(l+1),?,a_r在模2017意义下有多少个互不相同的数字。
现在按时间顺序给出m个操作,你需要给出第三种操作的结果。


输入格式

第一行包含一个正整数T,表示有T组数据,满足T≤200。
接下来依次给出每组测试数据。对于每组测试数据:
第一行包含两个正整数n和m,满足1≤n,m≤10^5。
第二行包含n个非负整数,表示a_1,a_2,?,a_n,满足0≤a_i<2017。
接下来m行按时间顺序描述所有操作。每行表示一个操作,第一个整数是s,表示这是第s种操作,满足1≤s≤3,其他参数紧跟其后。
约10组数据满足n≥10^3或m≥10^3。


输出格式

对于每个第三种操作,输出一行一个正整数表示答案。


样例输入

1
5 6
1 2 3 4 5
3 1 5
1 1 4
1 2 3
3 2 4
2 3 5 4
3 1 5

样例输出

5
2
3

提示

没有写明提示


题目来源

鸣谢Tangjz提供试题