有 $n$ 个购买计划，第 $i$ 个计划形如：
- 花费 $a_i$ 的价钱购买一个物品；
- 花费 $b_i$ 的价钱购买两个物品。
两个选项不能同时选择，每个计划最多能执行一次。给定 $q$ 次操作：
1 p x y：$a_p \leftarrow x, b_p \leftarrow y$2 l r k：只能执行 $i \in [l, r]$ 中的计划，希望购买 $k$ 个物品，花费的最少的价钱是多少
输入格式
一行两个整数 $n, q$
$n$ 行两个整数 $a_i, b_i$
$q$ 行操作，格式同上
输出格式
对每个询问操作输出一行一个整数
样例
见下发文件
数据范围
$1 \le n, q \le 1 \times 10^5, 1 \le a_i < b_i \le 10^9, 0 \le l \le r < n, 1 \le k \le 2(r - l + 1)$
子任务
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| 1 | $1 \le n, q \le 14$ | 5 |
| 2 | $1 \le n, q \le 300$ | 5 |
| 3 | $1 \le n, q \le 2 \times 10^3$ | 15 |
| 4 | $1 \le n, q \le 1 \times 10^5, l = 0$，保证没有 $1$ 操作 | 15 |
| 5 | 保证没有 $1$ 操作 | 10 |
| 6 | $1 \le n, q \le 8 \times 10^4$ | 20 |
| 7 | 无 | 30 |