Background

$[Noon - 12:13$ $P.M.]$

$Curtis$ $Nishikino$ saw everyone preparing so seriously for the party, so this cute girl also became a volunteer!

Problem Description

$Curtis$ $Nishikino$ came to the energy center of the kite festival, where everyone is preparing for the party. There are a total of $N$ devices here. Of course, due to changes in the plan, devices may be added or removed at any time. However, the total number of devices will not exceed $10^4$. Keeping track of the number of devices at any time is also one of the volunteer's jobs.

Each device has some attributes. For example, for device $i$, for each attribute it has (say attribute $j$), there is a given value, denoted as $value_{ij}$. But attributes are shared, which means that even if a device does not have a certain attribute, it only makes its value for that attribute equal to $0$. The number of attributes is $M$. Note that the attribute indices range from $0$ to $M-1$.

Now the volunteers are trying to connect a consecutive segment of devices together, with the following effect:

• For devices from $j$ to $k$, the final value of attribute $i$ is $\sum_{p=j}^{k}value_{pi}$.

The volunteers need $Curtis$'s help, but doing the calculations is too troublesome. $Curtis$ $Nishikino$ also hopes you can help her.

Input Format

The first line contains two integers $n$ and $m$.

In the next $n$ lines, the first integer is $k_i$, meaning device $i$ has $k_i$ attributes. Then there are $2\times k$ integers, $x_j$ and $y_j$, meaning $value_{ix_j}=y_j$.

Then there is an integer $q$, meaning there are $q$ operations. Each operation is one of the following:

$I$ $x$: Insert a device after device $x$. The next line contains its description, the same as initialization.

$D$ $x$: Discard the $x$-th device.

$QA$: Query the total number of devices.

$QS$ $l$ $r$: Query the effect of connecting devices $l$ to $r$.

The input is guaranteed to be valid.

Output Format

For each $QA$, output one integer on a single line.

For each $QS$, output $m$ integers on one line. If the value of attribute $i$ is $0$, output $0$ at that position.

Note！

After completing all operations, please output one extra line: "end" (without the double quotes).

4 4
4 0 1 1 2 2 2 3 1
2 0 1 2 1
0
2 1 2 3 1
5
QA
I 2 
2 1 1 3 2
QS 2 4
QA
QS 1 1

4
1 1 1 2
5
1 2 2 1
end

Hint

For $15\%$ of the testdata, $0 < N \le 10^3\ , \ 0<M \le 10\ , \ 0 < q \le 10^3$.

For an additional $5\%$ of the testdata, $0<N \le 10^4\ , \ 0<M \le 200\ , \ 0 < q \le 10^4$, and it is guaranteed that there are no $QS$ operations.

For $100\%$ of the testdata, $0<N \le 10^4\ ,\ 0<M \le 200\ , \ 0<q\le10^4$.

Translated by ChatGPT 5