#SWPU1. G.橘子的秘密

    ID: 6460 Type: Default 5000ms 256MiB Tried: 314 Accepted: 26 Difficulty: 6 Uploaded By: Tags>数据结构线段树SWPUACM选拔赛天梯赛校内选拔

G.橘子的秘密

Background

img

Description

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

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

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

Format

Input

11 行输入两数 nmn、m 表示橘子摊的数量以及询问次数

22 行到第 n+1n+1 每行输入两个数 CCAA 分别表示橘子的种类以及橘子数量

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

Output

对于 op==2op==2 以及 op==3op==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.