Background

Description

给定$n\ (1<=n<=10^6)$个橘子摊，每一个橘子摊只卖一个种类的橘子，然后输入一个 $m\ (1<=n<=10^6)$ 表示询问次数，然后输入n个橘子摊的橘子种类 $C(1<=C<=20)$ 和橘子数量 $a \ (0<=a<=1e6)$， 每次询问我们输入一个op表示对应的操作，有三种操作，如下：

• $op == 1$ ，输入 $l,r,k$ 表示区间 $[l,r]$ 位置的橘子摊的摊主都进货 $k \ (0<=k<= 10^6)$ 个橘子
• $op == 2$ ，输入 $l,r$ 表示查询区间 $[l,r]$ 的橘子有多少 不同的 种类（注意：橘子数量为0的摊也算种类）
• $op == 3$ ，输入 $l,r$ 表示查询区间 $[l,r]$ 的橘子摊的橘子总个数，由于总数较大，请 $mod \ 10^9+7$ 输出

对于不同的操作按要求输出即可

Format

Input

第 $1$ 行输入两数 $n、m$ 表示橘子摊的数量以及询问次数

第 $2$ 行到第 $n+1$ 每行输入两个数 $C$ 和 $A$ 分别表示橘子的种类以及橘子数量

第 $n+2$ 行到第 $n+m+1$ 行每行输入一个 $op$ ,如果 $op == 1$ 那么本行继续输入 $l,r,k$，否则本行继续输入 $l,r$

Output

对于 $op==2$ 以及 $op==3$ 操作的查询结果输出

Samples

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

1
3
6
3

Limitation

5s, 2048KiB for each test case.