RMT Subway Simulation

This problem is adapted from the CCC 2017 Senior T5 "RMT" problem. In the RMT subway system there are \(N\) stations numbered from 1 to \(N\) and \(M\) subway lines numbered from 1 to \(M\). Each station belongs to exactly one subway line and every line contains at least one station. For every subway line, the stations lie on a circular route: if a station has number \(S\) then the next station on the same line is the one with the next larger number, and if \(S\) is the largest-numbered station on its line, then the next station is the smallest-numbered station on that line.

At the start of the test, each station \(i\) hosts a train carrying \(A_i\) volunteers. Throughout the test, the volunteers remain in their train.

There are \(Q\) operations. Each operation is one of the following two types:

• Query: Given two integers \(l\) and \(r\), report the total number of volunteers in the trains currently located at stations \(l\) through \(r\) (inclusive).
• Move: Given an integer \(x\), run (move) all subway trains on line \(x\). When a move is executed on a line, every train on that line moves to the next station on that line. More precisely, if a train originally started at station \(s\) (which belongs to a particular line with stations \(L = [L_0, L_1, \dots, L_{k-1}]\) in increasing order) and the line has been moved a total of \(t\) times, then that train is currently at station \(L_{(j+t) \bmod k}\) where \(L_j = s\).

Your task is to process the operations and output the results of the queries.

inputFormat

The input begins with a line containing three integers \(N\), \(M\) and \(Q\) (number of stations, number of lines, and number of operations).

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) where \(A_i\) is the number of volunteers on the train at station \(i\) initially.

Then \(M\) lines follow. Each of these lines describes one subway line. The line starts with an integer \(k\) (the number of stations on that line) followed by \(k\) integers in strictly increasing order representing the station numbers on that line. These stations form a circular route.

Finally, \(Q\) lines follow, each describing an operation. An operation is either:

• "Q l r" - a query asking for the total number of volunteers on stations \(l\) through \(r\) (inclusive).
• "M x" - a move operation on line \(x\).

outputFormat

For each query operation, output the total number of volunteers on the trains located between the given station indices (inclusive). Each answer should be printed on a new line.

sample

5 2 5
1 2 3 4 5
3 1 3 5
2 2 4
Q 1 5
M 1
Q 2 4
M 2
Q 1 3

15
7
10