There are $n$ purchase plans. The $i$-th plan is as follows:

1. Spend $a_i$ to purchase one item;
2. Spend $b_i$ to purchase two items.

The two options cannot be chosen simultaneously, and each plan can be executed at most once. Given $q$ operations:

• 1 p x y: $a_p \leftarrow x, b_p \leftarrow y$
• 2 l r k: Only plans $i \in [l, r]$ can be executed. What is the minimum cost to purchase $k$ items?

Input

Two integers $n, q$ on the first line.

$n$ lines, each containing two integers $a_i, b_i$.

$q$ lines, each representing an operation as described above.

Output

For each query operation, output one integer per line.

Constraints

$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)$

Subtasks

Examples

Input 1

3 3
1 10
2 10
3 10
2 0 2 3
1 1 5 6
2 0 2 3

Output 1

6
7