CauchySheep has created a simple water problem.

There are $n$ water tanks with the same base area arranged in a row. Adjacent tanks share a partition, and the height of the partition between the $i$-th tank and the $(i+1)$-th tank is $b_i$. The heights of the leftmost and rightmost partitions can be considered infinite. Initially, all water in the tanks is at rest, and the initial water level of the $i$-th tank is $a_i$. You need to maintain the following two types of operations:

• Given $x$ and $h$, drill a small hole at height $h$ in the partition between the $x$-th tank and the $(x+1)$-th tank. After this, the water levels in some tanks will change; you should wait until these tanks return to a state of rest.
• Given $x$, query the current water level of the $x$-th tank.

Please complete this water-filled problem!

Input

The first line contains two integers $n$ and $q$, representing the number of tanks and the number of operations, respectively.

The second line contains $n$ space-separated real numbers $a_i$, representing the initial water levels.

The third line contains $n-1$ space-separated real numbers $b_i$, representing the initial partition heights.

The next $q$ lines each describe an operation:

• 1 x h represents the first type of operation, guaranteed $1 \le x \lt n$. Note that $h$ is a real number.
• 2 x represents the second type of operation, guaranteed $1 \le x \le n$.

All real numbers in the input have at most seven decimal places.

Output

For each operation of the second type, output the answer on a new line.

On the last line, output $n$ space-separated real numbers representing the water level of each tank after all operations are completed.

An absolute error within $10^{-7}$ is acceptable.

Note that you should ensure your output contains only real numbers (or integers), otherwise we cannot guarantee that the checker will run correctly.

Examples

Input 1

5 10
3 1 3 1 10
10 10 10 10
1 1 1
2 1
2 2
1 3 5
1 4 5
2 3
2 4
2 5
1 2 0
2 1

Output 1

2.00000000
2.00000000
4.00000000
5.00000000
5.00000000
2.66666667
2.66666667 2.66666667 2.66666667 5.00000000 5.00000000

Input 2

5 2
6.62 5.02 1.49 4.35 4.01
7.83 7.10 5.90 7.93
1 3 2.91
1 4 2.17

Output 2

6.62000000 5.02000000 3.28333333 3.28333333 3.28333333

Subtasks

In this problem, we use an ideal model. That is, we assume the volume of water remains constant and ignore surface tension, friction, etc. You can assume that the water level changes after drilling a hole follow common sense. You can assume that for two adjacent water levels $a_i, a_{i+1}$, and a hole of height $h$ in the partition between them (or an initial partition height $h$), if $a_i > h$ and $a_i > a_{i+1}$, water will flow from $i$ to $i+1$. Symmetrically, if $a_{i+1} > h$ and $a_{i+1} > a_i$, water will flow from $i+1$ to $i$. Water flowing from $x$ to $y$ means $a_x$ decreases continuously and $a_y$ increases continuously, while their sum remains constant.

Friendly reminder from the problem setter: Please handle precision errors caused by floating-point operations carefully.

For all test data, $1 \le n, q \le 100000$, $0 \le a_i, h \le 100$, and for $1 \le i < n$, $b_i \ge \max(a_i, a_{i+1})$. All real numbers in the input have at most seven decimal places.

• Subtask 1 (1 point): $1 \le n, q \le 10$;
• Subtask 2 (10 points): $1 \le n, q \le 300$;
• Subtask 3 (10 points): $1 \le n, q \le 2000$, for $i > 1$, $a_i = 0$;
• Subtask 4 (10 points): $1 \le n, q \le 2000$;
• Subtask 5 (30 points): For $i > 1$, $a_i = 0$;
• Subtask 6 (39 points): No special restrictions.