题目背景

原题链接：HDU4578.

题目描述

现有 $n$ 个正整数 $a_1, a_2, \cdots, a_n$，初始值均为 $0$。

要对它们做 $m$ 次操作，每次操作可以分为以下四种：

1. 对 $a_x$ 到 $a_y$ 的所有整数加上 $c$。
   • 形式化地，对于每个整数 $k \in [x,y]$，执行操作 $a_k \leftarrow a_k+c$。
2. 对 $a_x$ 到 $a_y$ 的所有整数乘上 $c$。
   • 形式化地，对于每个整数 $k \in [x,y]$，执行操作 $a_k \leftarrow a_k \times c$。
3. 将 $a_x$ 到 $a_y$ 的所有整数都改为 $c$。
   • 形式化地，对于每个整数 $k \in [x,y]$，执行操作 $a_k \leftarrow c$。
4. 询问从 $a_x$ 到 $a_y$ 的所有整数的 $p$ 次方和，并对 $10007$ 取模；其中 $p$ 满足 $1\le p \le 3$。
   • 形式化地，求出 $[(a_x)^p + (a_{x+1})^p + \cdots + (a_y)^p] \mod 10007$ 的值。

请你实现一种高效的数据结构支持以上操作。

输入格式

输入的第一行包含两个正整数 $n,m$ 分别表示被操作数的个数、操作次数。

接下来 $m$ 行，每行表示一次操作，格式如下：

• 1 x y c，表示上述操作 $1$，即区间 $[x,y]$ 都加上 $c$。
• 2 x y c，表示上述操作 $2$，即区间 $[x,y]$ 都乘上 $c$。
• 3 x y c，表示上述操作 $3$，即区间 $[x,y]$ 都赋值为 $c$。
• 4 x y p，表示上述操作 $4$，求出区间 $[x,y]$ 所有数的 $p$ 次方和对 $10007$ 取模的值。

输出格式

对于每个操作 $4$ 均输出一行，表示询问的答案。注意对 $10007$ 取模。

5 5
3 3 5 7
1 2 4 4
4 1 5 2
2 2 5 8
4 3 5 3

307
7489

数据范围

对于 $100\%$ 的数据，$1 \le n,m \le 1 \times 10^5$，$1 \le x \le y \le n$，$1 \le c \le 10000$，$1 \le p \le 3$。

注意事项：对于查询操作与修改操作，各有 $20\%$ 的数据不随机。