Problem C
Cornflakes for Cthulhu

For reasons quite beyond the minds of mortals, the elder god Cthulhu has taken a great interest in the amount of cornflakes in specific areas near the corner of the universe. Since Cthulhu operates in much more than just $3$ dimensions, keeping track of all the cornflakes is a somewhat complex problem, and he has commanded that you, his most loyal follower, figure it out.

As part of this task, Cthulhu will give you a series of commands. There are two types of commands:

• Cthulhu will tell you that the amount of cornflakes at a specific point in the universe has either increased or decreased by some amount. While you are not sure how, it is possible for a position to contain a negative amount of Cornflakes. You have wisely decided not to ask Cthulhu about how this is possible.

• Cthulhu will ask you how many cornflakes there are within an area of the universe. This area will always be at the corner of the universe, meaning that it is an area between the point that is $0$ in all dimensions (where Cthulhu resides), and a coordinate given to you by Cthulhu.

Input

The first line of input contains two integers, $1 \leq k \leq 20$, the amount of dimensions in the universe and $2 \leq q \leq 200\, 000$, the number of commands from Cthulhu. On the next line follows $k$ integers, $d_1, \ldots , d_ k$, denoting the size of the universe in each dimension. The following $q$ lines consist of commands from Cthulhu. Each line starts with either the letter ’u’ or the letter ’q’.

A line starting with ’u’ is a command to update the amount of cornflakes at a specific coordinate in the universe, and is followed by $k$ integers $m_1,\ldots , m_ k$, the coordinate to be updated, then followed by an integer $-10^7 \leq a \leq 10^7$, the amount of Cornflakes added or subtracted from this position.

A line starting with ’q’ is a query asking about the amount of Cornflakes within a certain area of the universe, and is followed by $k$ integers $m_1, \ldots , m_ k$, the coordinate defining the area. Specifically, the query is asking for the sum of coordinate, in the universe $c_1, \ldots , c_ k$ where $0 \leq c_ i \leq m_ i$.

The universe will not contain more than $2 \leq p \leq 10^6$ positions. Coordinates will not be outside the universe, meaning that for any coordinate $m_1, \ldots , m_ n, 0 \leq m_ i < d_ i$

Output

2 10
3 3
u 0 0 1
u 1 1 2
u 1 2 3
u 2 0 4
u 0 1 5
q 2 2
q 0 1
q 1 0
q 2 1
q 0 2

15
6
1
12
6