In this task you are given $n$ lines, and have to answer a total of $q$ queries of three types.

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

Initially all lines are inactive.

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