Multiply Then Plus
Description
Given $n$ pairs $(a_1,b_1),(a_2,b_2),\dots,(a_n,b_n)$, you need to perform $q$ operations. Each operation has one of the following forms:
- "1 $k$ $a$ $b$" ($1\leq k\leq n$, $1 \leq a,b \leq 10^9$): Modify the $k$-th pair into $(a,b)$.
- "2 $x$ $l$ $r$" ($1 \leq x \leq 10^9$, $1\leq l\leq r\leq n$): Find the maximum value of $a_i\times x+b_i$, where $l\leq i\leq r$.
The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 500\,000$) denoting the number of pairs and the number of operations.
Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq 10^9$), denoting the $i$-th pair.
Each of the next $q$ lines describes an operation in the format shown above.
For each query, print a single line containing an integer denoting the answer.
Input
The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 500\,000$) denoting the number of pairs and the number of operations.
Each of the following $n$ lines contains two integers $a_i$ and $b_i$ ($1 \leq a_i,b_i \leq 10^9$), denoting the $i$-th pair.
Each of the next $q$ lines describes an operation in the format shown above.
Output
For each query, print a single line containing an integer denoting the answer.
3 5
2 3
1 5
3 1
2 1 1 3
2 3 1 2
1 3 1 1
2 3 3 3
2 2 1 3
6
9
4
7