마법의 도넛 게임

시간 제한2초메모리 제한512 MB

요약

원형 보드에서 회전, 뒤집기, 구간 더하기 명령을 수행하고, 기준 칸부터 X칸의 합을 구할 때마다 그 값을 10^9+7로 나눈 나머지로 출력합니다.

난이도: 보통10점 중 6점
유형: 세그먼트 트리, 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

Albert는 같은 크기의 $N$ 개 칸으로 이루어진 도넛 모양 게임 보드로 마법의 도넛 게임을 즐긴다.

먼저 칸 하나를 "기준 칸"으로 정해 12시 방향에 놓는다. 그다음 시계 방향 순서대로 각 칸에 정수 $V_1, V_2, \dots, V_N$ 을 적는다. 아래 그림은 $N = 7$ , $V = [2, 0, 2, 4, 9, 9, 9]$ 인 경우이며, 화살표가 기준 칸을 가리킨다.

이후 지시 사항이 적힌 카드 $M$ 장을 순서대로 뽑아 카드의 지시를 수행한다. 각 카드에는 정수 3개가 적혀 있으며, $i$ 번째 카드의 정수를 차례로 $S_i, X_i, Y_i$ 라 한다. 지시 사항은 다섯 종류이고, 첫 번째 정수 $S_i$ 가 지시 내용을 정한다 ( $S_i \in \{1, 2, 3, 4, 5\}$ ).

$S_i = 1$ : 보드를 반시계 방향으로 $X_i$ 칸 돌린다. $Y_i$ 는 항상 $0$ 이다.
$S_i = 2$ : 보드를 시계 방향으로 $X_i$ 칸 돌린다. $Y_i$ 는 항상 $0$ 이다.
$S_i = 3$ : 12시와 6시를 잇는 축을 기준으로 보드를 뒤집는다. $X_i$ 와 $Y_i$ 는 항상 $0$ 이다.
$S_i = 4$ : 기준 칸부터 시계 방향으로 총 $X_i$ 개 칸에 적힌 값을 각각 $Y_i$ 씩 증가시킨다.
$S_i = 5$ : 기준 칸부터 시계 방향으로 총 $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]$ 이 된다.

입력

첫 줄에 테스트 케이스의 수 $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 j \le M$ 인 각 $j$ 에 대하여: $1 \le V_j \le 10^9$
배열 $S$ 의 원소 중 적어도 하나는 $S_j = 5$ 이다. 따라서 출력해야 하는 배열 $O$ 가 비어 있는 입력은 주어지지 않는다.

예제1

예제 1

입력

3
7 9
2 0 2 4 9 9 9
1 4 5 5 3 5 2 4 5
2 4 3 5 0 3 2 4 3
0 3 0 0 0 0 0 2 0
6 9
2 0 2 4 0 0
1 4 5 5 3 5 2 4 5
2 4 3 5 0 3 2 4 3
0 3 0 0 0 0 0 2 0
6 5
3 1 4 1 5 9
1 2 3 4 5
1 3 0 4 4
0 0 0 1 0

예상 출력

24 45 7 30
15 20 7 21
15