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