题目描述

给定一个长度为 $n$ 的非负整数序列 $a_1,a_2,\cdots ,a_n$，你需要支持以下三种类型的操作：

1. 给定 $l,r$，满足 $1\le l\le r\le n$，将 $a_l,a_{l+1},\cdots ,a_r$ 依次修改为 $a_l^2,a_{l+1}^2,\cdots ,a_r^2$。
2. 给定 $l,r,x$，满足 $1\le l\le r\le n,0 \le x < 2017$，将 $a_l,a_{l+1},\cdots ,a_r$ 分别修改为 $x$。
3. 给定 $l,r$，满足 $1\le l\le r\le n$，统计 $a_l,a_{l+1},\cdots ,a_r$ 在模 $2017$ 意义下有多少个互不相同的数字。 现在按时间顺序给出 $m$ 个操作，你需要给出第三种操作的结果。

输入格式

第一行包含一个正整数 $T$，表示有 $T$ 组数据。

接下来依次给出每组测试数据。对于每组测试数据：

第一行包含两个正整数 $n$ 和 $m$。

第二行包含 $n$ 个非负整数，表示 $a_1,a_2,\cdots ,a_n$。

接下来 $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\ge 10^3$ 或 $m\ge 10^3$。
对于 $100\%$ 的数据，$T\le 200$，$1\le n,m\le 10^5$，$0\le a_i<2017$，$1\le s\le 3$。

题目来源

鸣谢Tangjz提供试题