**Time limit:**2.00 s**Memory limit:**512 MB

- 1. Activate line with index $i$. It is guaranteed that the line is inactive.

- 2. Deactivate line with index $i$. It is guaranteed that the line is active.

- 3. What is the lowest value any active line has at a given $x$-coordinate? The value of line $i$ at point $x$ is $f_{i}(x) = a_{i} x + b_{i}$. It is guaranteed at least one line is active.

**Input**

The first line contains two integers $n, q$: the number of lines and the number of queries.

the second line contains $n$ integers $a_1, \dots, a_n$.

the third line contains $n$ intergets $b_1, \dots, b_n$.

$q$ lines follow, describing the queries. Each line contains two integers $t$ $v$: The query is of type $t$. If $t = 1$ or $t = 2$, $i = v$. If $t = 3$, $x = v$.

**Output**

Output the answer to each query of type $3$.

**Constraints**

- $1 \leq n, q \leq 4 \cdot 10^{5}$

- $-10^9 \leq x, a, b \leq 10^{9}$

- $1 \leq i \leq n$

**Example**

Input:

4 12

-1 -2 0 -1

-18 13 4 -14

1 1

3 9

2 1

1 2

3 7

1 4

1 3

1 1

2 1

3 -4

3 10

3 -9

Output:

-27 -1 -10 -24 -5