Được biết Hồng đang theo học chuyên đề xử lý dữ liệu lớn, Sơn đề nghị Hồng luyện tập với bài toán sau đây:

Cho một dãy ~h~ gồm ~n~ số nguyên ~h_0,h_1,\ldots,h_{n-1}~. Cần thực hiện ~q~ truy vấn, mỗi truy vấn thuộc một trong hai dạng:

1. Thêm một số nguyên ~x~ vào dãy ~h~.

2. Sắp xếp dãy ~h~ hiện tại theo thứ tự không giảm, sau đó tính tổng ~k~ phần tử có chỉ số ~i_0,i_1,\ldots,i_{k-1}~.

Các chỉ số trong truy vấn loại ~2~ sẽ được xác định bởi bốn thông số ~k, start, a, b~ theo công thức sau: $$i_j = \begin{cases} start \bmod size & \text{nếu } j = 0 \\ (i_{j-1}\cdot a + b) \bmod size & \text{nếu } j > 0 \end{cases}$$

với ~size~ là kích thước của dãy ~h~ hiện tại.

Input

Dòng đầu tiên gồm một số nguyên dương ~T~ (~T\le 5~) — số bộ dữ liệu. Mô tả của mỗi bộ dữ liệu như sau:

Dòng đầu tiên của mỗi bộ dữ liệu gồm hai số nguyên dương ~n, q~ (~n\le 100000~, ~q\le 20000~) — kích thước ban đầu của dãy ~h~ và số truy vấn.

Dòng tiếp theo của mỗi bộ dữ liệu gồm ~n~ số nguyên ~h_0,h_1,\ldots,h_{n-1}~ (~1\le h_i\le 10^9~).

Mỗi dòng trong ~q~ dòng cuối cùng của mỗi bộ dữ liệu bắt đầu bằng một chữ cái ~cmd~.

• Nếu ~cmd=\texttt{A}~, thì tiếp theo là một số nguyên ~x~ (~1\le x\le 10^9~) là số cần được thêm vào dãy ~h~.

• Nếu ~cmd=\texttt{B}~, thì tiếp theo là bốn số nguyên ~k, start, a, b~ (~1\le start, a,b\le 1000~, ~k\le 10000~) mô tả một truy vấn loại ~2~.

Output

Với mỗi bộ dữ liệu, in ra một dòng gồm đáp án của các truy vấn loại ~2~.

Scoring

Sample Input 1

2
2 3
42 13
B 2 2 1 1
A 17
B 5 2 5 6
10 13
42 13 7 11 5 666 13 17 20 6
B 3 6 7 8
B 13 1 11 9
A 23
B 13 1 11 9
A 23
A 8
B 3 3 3 3
B 7 17 9 11
A 12
B 1 8 3 5
A 31
A 28
B 77 17 11 13

Sample Output 1

55 160
64 1477 510 679 99 17 1236

Notes

Trong bộ dữ liệu đầu tiên, dãy ~h~ ban đầu sau khi sắp xếp là ~[13,42]~.

• Truy vấn đầu tiên cần tính tổng tại các chỉ số ~0,1~: ~13+42=55~.

• Truy vấn thứ hai cần thêm ~17~ vào dãy ~h~, sau khi sắp xếp ta được: ~[13,17,42]~.

• Truy vấn thứ ba cần tính tổng tại các chỉ số ~2,1,2,1,2~: ~42+17+42+17+42=160~.