ktt

【题目描述】

现有$n$个一次函数形成的一个序列， 序列上每个位置都是$a_i\times x_i+b_i$。

你需要支持以下操作：

1 l r k：将区间$l$到$r$的$x_i$增加$k$，其中$k>0$。

2 l r：询问区间$l$到$r$的最大值。

共有$m$个操作。

【输入格式】

第一行两个整数$n,m$。

接下来$n$行，每行两个整数$a_i,b_i$。

接下来$m$行，每行一个操作，如【题目描述】。

【输出格式】

对于每个询问，一行一个正整数表示答案。

【输入样例】

5 3
2 1
3 1
2 2 
1 5
4 1
2 1 5
1 1 5 2
2 1 5

【输出样例】

5
9

【数据范围与约定】

$1\leq n,m\leq 10^5,1\leq a_i,b_i\leq 10^9,1\leq k_i\leq 100$。

【提示】

本题没有验题人，std是出题人用从过了的使用ktt的题目中封装起来的ktt写的，如果出错请联系出题人。