有 $n$ 个购买计划，第 $i$ 个计划形如：

1. 花费 $a_i$ 的价钱购买一个物品；
2. 花费 $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)$

子任务