마법의 도넛 게임

Albert는 균등한 크기의 $N$ 개의 칸으로 구성된 도넛 모양의 게임 보드를 이용한 마법의 도넛 게임 놀이를 즐겨한다.

우선 도넛 모양의 게임 보드의 칸 중 하나를 "기준 칸"으로 삼아 12시 방향에 놓이도록 한 후, 각 칸에는 시계 방향 순으로 $V\_1, V\_2, \dots, V\_N$ 의 정수 값을 적어넣는다. 예를 들어 아래 그림은 $N = 7, V = \[2, 0, 2, 4, 9, 9, 9]$ 인 경우를 나타내며 "기준 칸"은 화살표로 강조되어있다.

이후, 지시 사항이 적힌 카드 $M$ 장을 순서대로 뽑아 카드에 적힌 지시 사항을 수행한다 - 각 카드에는 3개의 정수가 적혀있는데, 편의상 $i$ 번째 카드에 적힌 3개의 정수를 순서대로 $S\_i, X\_i, Y\_i$ 라 하자. 총 다섯 종류의 지시 사항이 있으며, 각 카드에 적힌 첫 번째 정수 ($S\_i$)의 값이 지시 사항의 내용을 결정한다 (즉, $S\_i \in \\{1, 2, 3,4, 5\\}$).

• $1$ $X\_i$ $0$ : 게임 보드를 반시계 방향으로 $X\_i$ 칸만큼 돌린다. 이 경우 항상 $Y\_i = 0$ 이 적혀있다.
• $2$ $X\_i$ $0$ : 게임 보드를 시계 방향으로 $X\_i$ 칸만큼 돌린다. 이 경우 항상 $Y\_i = 0$ 이 적혀있다.
• $3$ $0$ $0$ : 게임 보드를 12시-6시 축을 기준으로 뒤집는다. 이 경우 항상 $X\_i = Y\_i = 0$ 이 적혀있다.
• $4$ $X\_i$ $Y\_i$ : 게임 보드의 기준칸부터 시작하여 시계 방향으로 총 $X\_i$ 개의 칸에 적힌 값을 각각 $Y\_i$ 씩 증가시킨다.
• $5$ $X\_i$ $0$ : 게임 보드의 기준칸부터 시작하여 시계 방향으로 총 $X\_i$ 개의 칸에 적힌 값을 모두 더하여 메모지에 기록한다 (메모지에 $j$ 번째로 적은 값을 $O\_j$ 라 하자).

예를 들어 $M = 9$ 이고 $S = \[1, 4, 5, 5, 3, 5, 2, 4, 5]$, $X = \[2, 4, 3, 5, 0, 3, 2, 4, 3]$, $Y = \[0, 3, 0, 0, 0, 0, 0, 2, 0]$ 이라 하자.

게임 보드 상태	설명
	게임을 시작할 때의 게임 보드 상태이다.화살표로 표시된 칸이 "기준칸" 현재 시점의 기준칸이다.
	1번 카드를 뽑은 후 게임 보드를 반시계 방향으로 2칸 돌린 이후의 게임 보드 상태이다.
	2번 카드를 뽑은 후 4개의 칸에 각각 3씩 더한 이후의 게임 보드 상태이다.
	3번 카드를 뽑아 총 3개의 칸에 적힌 값을 모두 더하면 $5 + 7 + 12 = 24$가 되므로 $O\_1 = 24$ 이다.게임 보드의 상태는 변화가 없다.
	4번 카드를 뽑아 총 5개의 칸에 적힌 값을 모두 더하면 $5 + 7 + 12 + 12 + 9= 45$가 되므로 $O\_2 = 45$ 이다.게임 보드의 상태는 변화가 없다.
	5번 카드를 뽑아 게임 보드를 뒤집은 이후의 게임 보드 상태이다. 12시 방향을 가리키는 기준칸은 위치가 변하지 않음에 유의하자.
	6번 카드를 뽑아 총 3개의 칸에 적힌 값을 모두 더하면 $5 + 0 + 2 = 7$이 되므로 $O\_3 = 7$ 이다.게임 보드의 상태는 변화가 없다.
	7번 카드를 뽑은 후 게임 보드를 시계 방향으로 2칸 돌린 이후의 게임 보드 상태이다.
	8번 카드를 뽑은 후 4개의 칸에 각각 2씩 더한 이후의 게임 보드 상태이다.
	9번 카드를 뽑아 총 3개의 칸에 적힌 값을 모두 더하면 $14 + 9 + 7 = 30$이 되므로 $O\_4 = 30$ 이다.게임 보드의 상태는 변화가 없다.

이 때 5번 종류의 지시사항이 적힌 카드는 총 4장이므로 $O = \[24, 45, 7, 30]$ 가 된다.

입력으로 $N, M, V, S, X, Y$ 값이 주어졌을 때, 위 놀이를 마친 후 메모지에 적힌 값들을 구해보자 (즉, $O\_1, O\_2, \dots$ 값을 구하면 된다).

입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트의 첫 줄에는 $N, M$이 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $V$ 의 원소인 $N$ 개의 정수가 공백으로 구분되어 주어진다. 셋째 줄에는 배열 $S$ 의 원소인 $M$ 개의 정수가 공백으로 구분되어 주어진다. 넷째 줄에는 배열 $X$ 의 원소인 $M$ 개의 정수가 공백으로 구분되어 주어진다. 다섯째 줄에는 배열 $Y$ 의 원소인 $M$ 개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답이 되는 배열 $O$ 의 값을 공백으로 구분하여 각 줄에 출력한다. 단, 이 값이 매우 커질 수 있으므로 $O$ 의 각 원소를 $10^9 + 7$ 로 나눈 나머지를 출력한다.

• $1 \le T \le 10$

• $3 \le N \le 250,000$

• $3 \le M \le 123,456$

• $1 \le i \le N$ 인 각 $i$에 대하여: $0 \le V\_i \le 10^9$

• $1 \le j \le M$ 인 각 $j$에 대하여:

  • $S\_j \in \\{1, 2, 3, 4, 5\\}$
  • $S\_j = 3$ 인 경우 $X\_j = 0$ 이고, $S\_j \neq 3$ 인 경우 $1 \le X\_j \le N$
  • $S\_j \neq 4$ 인 경우 $Y\_j = 0$ 이고, $S\_j = 4$ 인 경우 $1 \le Y\_j \le 10^9$

• $1 \le V\_i \le 10^9$

• 입력으로 주어진 배열 $S$ 에서 최소 1개의 원소는 $S\_j = 5$ 임이 보장된다 - 즉, 출력해야 하는 배열 $O$ 가 비어있는 경우는 입력으로 주어지지 않는다.