题目描述

小明的叔叔是一家工厂的厂长。叔叔的工厂有 $n$ 个车间，编号为 $1 \sim n$ 。

管理工厂是很麻烦的事情，特别是在多次调整机器以及员工之后，统计总生产量更是难事。

第 $i$ 个车间在刚开始的时候机器生产力为 $a_i$，有 $b_i$ 个员工，那么这个车间的生产力就为 $a_i$*$b_i$ 。

工厂的总生产力定义为所有车间的生产力之和。

接下来的 $m$ 天，每天叔叔就会调整一段区间的车间。

有两种调整：

第一种，是对于一段区间 $[l,\ r]$ 的每一个车间重新分配每个车间的工人数为 $x$ 。

第二种，是对于一段区间 $[l,\ r]$ 的每一个车间增加机器生产力 $x$ 。

现在，小明的叔叔想知道每天调整之后工厂的生产量变为多少。

输入格式

第一行两个整数 $n$ 和 $m$，表示车场数以及天数。

接下来 $n$ 行，每行描述一个车间。

第 $i+1$ 行描述第 $i$ 个车间，包括两个整数 $a_i$ 和 $b_i$，意义如题目所述。

接下来 $m$ 行，每一行表示一个修改操作。

Set l r x 表示对于一段区间 $[l,\ r]$ 的每一个车间重新分配每个车间的工人数为 $x$ 。

Add l r x 表示对于一段区间 $[l,\ r]$ 的每一个车间增加机器生产力 $x$ 。

数据范围

20% 的数据，$1 \le n, m \le 2000$

100% 的数据，$1 \le n , m \le 100000$ , $1 \le l \le r \le n$ , $1 \le x \le 10000$

输出格式

输出 $m$ 行。

第 $i$ 行表示第 $i$ 天调整后，工厂的总生产力。

样例

4 4
2 1
4 3
6 5
8 7
Set 1 3 2
Add 2 3 1
Add 3 3 2
Set 1 4 2

80
84
88
48