C. Multiply Then Plus
time limit per test
6 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

Example
Input
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
Output
6
9
4
7