题目描述
给定一个长度为 n 的非负整数序列 a1,a2,⋯,an,你需要支持以下三种类型的操作:
- 给定 l,r,满足 1≤l≤r≤n,将 al,al+1,⋯,ar 依次修改为 al2,al+12,⋯,ar2。
- 给定 l,r,x,满足 1≤l≤r≤n,0≤x<2017,将 al,al+1,⋯,ar 分别修改为 x。
- 给定 l,r,满足 1≤l≤r≤n,统计 al,al+1,⋯,ar 在模 2017 意义下有多少个互不相同的数字。
现在按时间顺序给出 m 个操作,你需要给出第三种操作的结果。
输入格式
第一行包含一个正整数 T,表示有 T 组数据。
接下来依次给出每组测试数据。对于每组测试数据:
第一行包含两个正整数 n 和 m。
第二行包含 n 个非负整数,表示 a1,a2,⋯,an。
接下来 m 行按时间顺序描述所有操作。每行表示一个操作,第一个整数是 s ,表示这是第 s 种操作,其他参数紧跟其后。
输出格式
对于每个第三种操作,输出一行一个正整数表示答案。
样例输入
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
数据范围与约定
约 10 组数据满足 n≥103 或 m≥103。
对于 100% 的数据,T≤200,1≤n,m≤105,0≤ai<2017,1≤s≤3。
题目来源
鸣谢Tangjz提供试题