Problem I
Moving Porcelain

You have just started your bachelor’s degree and was lucky enough to get an apartment in some student housing not far from the university.

Today you’re moving your large collection of porcelain which you’re very protective of. You have $N$ types of different porcelain and you have $n_i$ amount of the $i^{\text{th}}$ type. The porcelain has been packed in $B$ boxes and because of old habit, you always pack the porcelain in the same order. How much there is room for in each box depends on the size of it, which varies massively, but you will always pack porcelain of the same type in the same box.

Your parents insist on helping with the move, but you’ve been hesitant to let them carry your porcelain, because your mom is notoriously clumsy. Despite her best efforts, she will drop some of the moving boxes, which will break the same amount, $k$ of each type of porcelain (you wonder how this is possible, but do not think about it for too long). When she drops a box, you will have to clean out all the broken porcelain and repack all the remaining pieces, including the porcelain in unbroken boxes – again in the same order as always. You always use new boxes, and since the box sizes varies, you’re not necessarily going to need the same amount of boxes, and the amount of porcelain types in each box also varies.

For good reason, you are worried about your porcelain collection. That is why you once in a while check the contents of a moving box and count the number of pieces.

Input

The first line of input contains two integers $N,P$, where $1\le N\le {10}^4$ is the amount of different types of porcelain you have in your collection, and $1\le P\le {10}^6$ is the amount of operations during the trip.

The second line will have $N$ integers, where $n_i$ defines how many pieces of the $i^{\text{th}}$ type that you have with $0\le i<N$. It is given that $1\le n_0,n_1,\dots n_{i-1},n_i\le {10}^9$.

The next $P$ lines contains a single operation which will have on of the following three formats.

• Repacking: A line will begin with an integer, if you repack your porcelain. The first integer $B$, defines how many boxes you’ve initially packed your porcelain into with $1\le B\le 5$. This is followed by $B$ integers, where $b_i$ defines how many different types of porcelain you’ve been able to fit in the $i^{\text{th}}$ box with $0\le i<B$.
  The sum of the integers $b_1,b_2,\dots ,b_i$ will always be equal to $N$.
  The third line of input will always be of this type.

• WHAM: A line will begin with a WHAM if your mom drops a box. The line ends with two integers $i$ and $k$. The first integer $i$ defines that your mom was carrying the $i^{\text{th}}$ box (the boxes are 0-indexed, because you’re a nerd). The second integer $k$ defines how many pieces of porcelain are broken of each type. It is guaranteed that your mom never breaks all or more pieces of one type of porcelain, $0<k<n_i$ for all porcelain in the dropped box.

• Mom?: A line will begin with Mom? followed by an integer $j$, if you want your mom to open the $j^{\text{th}}$ box, so you can count the amount of porcelain pieces in it.

Output

For each ‘Mom? $j$’ query print out a single line with the total amount of porcelain pieces in the $j^{\text{th}}$ box. As the numbers get very large, print the amount modulo ${10}^9+7$.

Sample 1 walkthrough

The first line of input defines that you have $8$ different types of porcelain, and the next line describes how much of each type you have. The total sum of porcelain pieces you have is:

The third line describes that you’ve packed it all into $4$ boxes:

• the $0^{\text{th}}$ box has the first three types of porcelain ($9+1+23=33$ pieces in total)

• the $1^{\text{st}}$ box has the next two types of porcelain ($10+17=27$ pieces in total)

• the $2^{\text{nd}}$ box has the next type of porcelain ($10$ pieces in total)

• the $3^{\text{rd}}$ and last box has the last two types of porcelain ($23+5=28$ pieces in total)

On the fourth line of input, your mom breaks box $1$, breaking $5$ of each type of porcelain in the box. There are now only $5$ pieces of the $4^{\text{th}}$ type of porcelain left and $12$ pieces of the $5^{\text{th}}$ type left. The following line says that you’ve packed the porcelain in $4$ boxes again, and the distribution of the types of porcelain is the same. The only change is in the $1^{\text{st}}$ box, that now only has $5+12=17$ pieces in total.

Sixth line of input is a ‘Mom? j’ query, so you will have to report back how many pieces of porcelain that are in the 1st box. This is 17.

Seventh line of input is also a ‘Mom? j’ query, so you will have to report back how many pieces of porcelain that are in the 0th box. This is 33.

Scoring

8 5
9 1 23 10 17 10 23 5
4 3 2 1 2
WHAM 1 5
4 3 2 1 2
Mom? 1
Mom? 0

17
33