After Abu Ishaq got rid of the weeds, his enemies became jealous of him because of his success in cucumber farming and decided to destroy one of his fields.

Abu Ishaq Farm as a table
1
x
n
is 1×n whose houses from left to right are from 1 to
n
n are numbered and at home
i
i om of it
a
i
a
i
​
 Cucumbers are planted. His farm
q
It operates for q days. At the beginning of each day, the number of cucumbers in the house
i
i th
b
i
b
i
​
 and at the end of each day, one of the following two things happens:

Abu Ishaq needs to calculate his profit and asks you for the total number of cucumbers in the houses of the interval.
[
l
,
r
]
Asks [l,r].

Enemies of Abu Ishaq house
x
They set fire to x Ohm and this fire starts advancing from both sides with equal speed and does not stop until it reaches an alarm; After the fire reaches each house, the number of cucumbers in it is halved (its correct component value is desired). Note that when one side of the fire reaches an alarm, the fire is immediately extinguished from both sides (pay attention that the house where the alarm is located does not catch fire). After the fire of Abu Ishaq, an alarm went off in his house
x
puts x. The whole process of advancing the fire is done in one day and does not drag on to the following days.

At first only in houses
0
0 and
n
+
1
There are n+1 alarms (one before the first house of the farm and one after the last house) and the rest of the houses are without alarms. For each occurrence of type one, output the total number of cucumbers.

input
In the first line, two numbers
n
n and
q
q is the number of houses in Abu Ishaq's farm and the number of days the farm operates, respectively.

In the second line
n
n is the number that is the number
i
i om, equal to
a
i
a
i
​
 is

In the third line as well
n
n is the number that is the number
i
i om, equal to
b
i
b
i
​
 Or the growth rate of the house
i
i is th

Then in each line of
q
q Next line first
t
t or the same type of event that has one of the following two states:

If
t
=
1
If t=1, then the event is of the first type, and in the continuation of the same line, two numbers
l
l and
r
r is given as input.
If
t
=
2
If t=2, then the event is of the second type, and in the continuation of the same number line
x
x is given as an input.
Quantity is guaranteed
x
x for each of
q
q days are different.
1
≤
n
≤
100

000
1≤n≤100 000
1
≤
q
≤
300

000
1≤q≤300 000
1
≤
l
,
r
,
x
≤
n
1≤l,r,x≤n
1
≤
a
i
,
b
i
≤
1

000

000
1≤a
i
​
 ,b
i
​
 ≤1 000 000

output
Output the requested value on one line for each occurrence of the first type.

Example
Sample entry 1
7 4
10 10 10 10 10 10 10
1 3 4 2 3 2 4
2 2
1 1 4
2 4
1 3 7
Plain text
Sample output 1
40
77
Plain text
Early farm cucumbers
[
10
,
10
,
10
,
10
,
10
,
10
,
10
]
is [10,10,10,10,10,10,10].

At the beginning of the first day, cucumbers have grown and the farm is in the form of
[
11
,
13
,
14
,
12
,
13
,
12
,
14
]
[11,13,14,12,13,12,14] comes out, at the end of the first day, the second house caught fire, as a result of the fire, it progressed to reach an alarm (on this day, the fire preceded the house alarm
0
0m stops) as a result of the amount of cucumbers in the houses
1
,
2
,
3
1,2,3 is halved and the farm at the end of the day is
[
5
,
6
,
7
,
12
,
13
,
12
,
14
]
[5,6,7,12,13,12,14] comes out.

At the beginning of the second day with the growth of cucumbers in the field
[
6
,
9
,
11
,
14
,
16
,
14
,
18
]
[6,9,11,14,16,14,18] comes out. Then add up the number of cucumbers in the houses
1
,
2
,
3
,
4
We output 1,2,3,4.

On the third day, like the previous days, we have after growth
[
7
,
12
,
15
,
16
,
19
,
16
,
22
]
[7, 12, 15, 16, 19, 16, 22] and with the fire of the fourth house and before reaching the first alarm from one side, the number of cucumbers in the houses
3
,
4
,
5
3, 4, 5 will be halved and the farm will be
[
7
,
12
,
7
,
8
,
9
,
16
,
22
]
[7,12,7,8,9,16,22] comes out. The fourth day will be spent in the same way.   c++