Magic Donut Game

Albert plays the Magic Donut Game on a donut-shaped board made of $N$ cells of equal size.

First, one cell is chosen as the "reference cell" and placed at the 12 o'clock position. Then the integers $V_1, V_2, \dots, V_N$ are written into the cells in clockwise order. The figure below shows the case $N = 7$, $V = [2, 0, 2, 4, 9, 9, 9]$. The arrow marks the reference cell.

Next, $M$ instruction cards are drawn in order, and each card's instruction is carried out. Each card has three integers. For the $i$-th card, the integers are called $S_i, X_i, Y_i$ in that order. There are five kinds of instructions, and the first integer $S_i$ decides which one applies ($S_i \in \{1, 2, 3, 4, 5\}$).

• $S_i = 1$: Rotate the board counterclockwise by $X_i$ cells. $Y_i$ is always $0$.
• $S_i = 2$: Rotate the board clockwise by $X_i$ cells. $Y_i$ is always $0$.
• $S_i = 3$: Flip the board over the axis through 12 o'clock and 6 o'clock. $X_i$ and $Y_i$ are always $0$.
• $S_i = 4$: Starting from the reference cell and moving clockwise, add $Y_i$ to each of the next $X_i$ cells.
• $S_i = 5$: Starting from the reference cell and moving clockwise, add up the values in the next $X_i$ cells and record the sum on a memo. The $j$-th recorded value is called $O_j$.

For example, take $M = 9$, $S = [1, 4, 5, 5, 3, 5, 2, 4, 5]$, $X = [2, 4, 3, 5, 0, 3, 2, 4, 3]$, and $Y = [0, 3, 0, 0, 0, 0, 0, 2, 0]$. The steps are shown in the table below.

Board state	Description
	The board at the start. The arrowed cell is the reference cell.
	After card 1, the board is rotated counterclockwise by 2 cells.
	After card 2, 3 is added to each of 4 cells.
	Card 3 sums the values of 3 cells: $5 + 7 + 12 = 24$, so $O_1 = 24$. The board does not change.
	Card 4 sums the values of 5 cells: $5 + 7 + 12 + 12 + 9 = 45$, so $O_2 = 45$. The board does not change.
	After card 5, the board is flipped. The reference cell stays at 12 o'clock.
	Card 6 sums the values of 3 cells: $5 + 0 + 2 = 7$, so $O_3 = 7$. The board does not change.
	After card 7, the board is rotated clockwise by 2 cells.
	After card 8, 2 is added to each of 4 cells.
	Card 9 sums the values of 3 cells: $14 + 9 + 7 = 30$, so $O_4 = 30$. The board does not change.

There are four type 5 cards, so $O = [24, 45, 7, 30]$.

The first line contains the number of test cases $T$.

The first line of each test case contains $N$ and $M$, separated by a space. The second line contains the $N$ elements of array $V$. The third line contains the $M$ elements of array $S$. The fourth line contains the $M$ elements of array $X$. The fifth line contains the $M$ elements of array $Y$. All values on each line are separated by spaces.

For each test case, print the elements of array $O$ on one line, separated by spaces. Since the values can become very large, print each element of $O$ modulo $10^9 + 7$.

• $1 \le T \le 10$
• $3 \le N \le 250,000$
• $3 \le M \le 123,456$
• For each $i$ with $1 \le i \le N$: $0 \le V_i \le 10^9$
• For each $j$ with $1 \le j \le M$: $S_j \in \{1, 2, 3, 4, 5\}$. If $S_j = 3$, then $X_j = 0$. If $S_j \neq 3$, then $1 \le X_j \le N$. If $S_j \neq 4$, then $Y_j = 0$. If $S_j = 4$, then $1 \le Y_j \le 10^9$.
• For each $j$ with $1 \le j \le M$: $1 \le V_j \le 10^9$
• At least one element of $S$ equals $5$. So the output array $O$ is never empty.