Between country A and country B, there are $N$ islands arranged in a line, numbered from 1 to $N$. For each $i (1 \le i < N)$, island $i$ and island $i+1$ are connected by the $i$-th bridge. Additionally, the 0-th bridge connects country A to island 1, and the $N$-th bridge connects island $N$ to country B.

A truck is trying to transport cargo from country A to country B by crossing the 0, 1, $\cdots$, $N$-th bridges in order. When the truck reaches island $i$, it loads $A_i$ units of cargo. However, if $A_i$ is negative, it unloads $|A_i|$ units of cargo. Also, the $i$-th bridge has a strength of $B_i$, so the truck cannot cross the $i$-th bridge while carrying more than $B_i$ units of cargo. Note that $B_0=B_N=10^{2026}$.

Specifically, as the truck moves between the islands with cargo, the number of cargo units changes according to the following rules:

When visiting an island: If the truck arrives at island $i$ with $k$ units of cargo, the number of cargo units becomes $k + A_i$. If the truck attempts to unload more cargo than it is carrying, resulting in a negative number of cargo units, the truck stops immediately.

Just before crossing a bridge: If the truck is carrying more than $B_i$ units of cargo just before crossing bridge $i$, the excess cargo is discarded. In other words, if the truck is carrying $k$ units of cargo just before crossing the bridge, the number of cargo units becomes $\min(k, B_i)$.

You can perform the following operation 0 or more times to reinforce the bridges for successful cargo transport. Each operation costs 1.

• Choose $1 \le i < N$ and increase the strength of bridge $i$ by 1.

Process $Q$ queries of the following two types:

• 1 $x$ $y$: Update the value of $A_x$ to $A_x + y$. $(y \ge 1)$
• 2 $k$: Output the minimum reinforcement cost required for a truck starting with $k$ units of cargo to depart from country A and reach country B by crossing bridges 0, 1, $\cdots$, $N$ without stopping. If it is impossible for the truck to reach country B without stopping, output -1 instead. Each query of type 2 is independent, and any bridge reinforcements performed do not affect subsequent queries.

Input

The first line contains two space-separated integers $N$ and $Q$.

The second line contains $N$ space-separated integers $A_1, A_2, \cdots, A_N$.

The third line contains $N-1$ space-separated integers $B_1, B_2, \cdots, B_{N-1}$.

The next $Q$ lines each contain one query.

Output

Print the answer for each query of type 2 on a new line.

Constraints

• $2 \le N \le 3 \times 10^5$
• $1 \le Q \le 3 \times 10^5$
• $-10^9 \le A_i \le 10^9$
• $0 \le B_i \le 10^9$
• $1 \le x \le N$
• $1 \le y \le 10^9$
• $0 \le k \le 10^9$
• At least one query of type 2 is given

Scoring

Examples

Input 1

5 4
3 -4 2 -1 5
2 1 3 2
2 0
2 2
1 2 2
2 1

Output 1

-1
2
0

Note

For the first query in Example 1, it is impossible to prevent the truck from stopping even if bridge reinforcements are performed. Therefore, print -1.

For the second query, if reinforcements are made to the first bridge 2 times, the truck can safely transport the cargo. The change in the number of cargo items on the truck is as follows:

• Initially 2 items.
• When entering island 1, $2+3=5$ items.
• Just before crossing bridge 1, $\min(5,4) = 4$ items.
• When entering island 2, $4-4=0$ items.
• Just before crossing bridge 2, $\min(0, 1) = 0$ items.
• When entering island 3, $0+2=2$ items.
• Just before crossing bridge 3, $\min(2,3) = 2$ items.
• When entering island 4, $2-1=1$ items.
• Just before crossing bridge 4, $\min(1,2) = 1$ items.
• When entering island 5, $1+5=6$ items.