타일 마스터의 시련

메이플스토리의 새로운 지역, "리버스 시티"에서는 마법 타일이 $N \times M$ 크기의 격자판을 이루고 있다. 각 타일의 앞면에는 빛의 문양, 뒷면에는 어둠의 문양이 새겨져 있으며, 모든 타일은 초기 상태에서 빛의 문양이 위를 향하고 있다.

모험가 여러분은 두 가지 마법 스크롤을 사용하여 타일을 뒤집을 수 있다. 스크롤은 사용해도 사라지지 않으며, 한 스크롤을 여러번 사용할 수 있다.

빛의 스크롤: $S$ 가지 종류의 빛의 스크롤이 존재하며, $i$ 번째 빛의 스크롤을 사용하면 연속한 $A_i$ 개의 행을 선택하여 해당 행에 놓인 모든 타일을 뒤집을 수 있다.
어둠의 스크롤: $T$ 가지 종류의 어둠의 스크롤이 존재하며, $i$ 번째 어둠의 스크롤을 사용하면 연속한 $B_i$ 개의 열을 선택하여 해당 열에 놓인 모든 타일을 뒤집을 수 있다.

모험가 여러분이 스크롤을 적절히 사용하여 모든 타일이 빛의 문양이 위를 향하도록 만들 수 있는 타일의 초기 상태를 아름다운 패턴이라 정의한다.

지역의 수호자, 타일 마스터는 시간의 흐름에 따라 타일의 문양을 조작하며 모험가에게 시련을 부여한다. 시각 $0$ 에는 모든 타일이 빛의 문양이 위를 향하고 있다. $1$ 이상 $Q$ 이하인 $i$ 에 대해 시각 $i$ 가 되면 타일 마스터는 $sx_i$ , $sy_i$ , $ex_i$ , $ey_i$ 를 선택하고, $sx_i \le x \le ex_i$ 와 $sy_i \le y \le ey_i$ 를 만족하는 모든 정수 $x$ , $y$ 에 대해 $x$ 행 $y$ 열에 위치한 타일을 모두 뒤집는다.

이제, 모험가 여러분은 각 시각 $i$ 에 대해, 해당 시각의 타일 상태를 시작 상태로 할 때 스크롤을 적절히 사용하여 모든 타일이 빛의 문양이 위를 향하게 만들 수 있는지, 즉 타일 상태가 아름다운 패턴인지 판별하는 프로그램을 작성하라.

입력 형식

첫 줄에 격자판의 크기를 나타내는 두 정수 $N$ 과 $M$ 이 공백으로 구분되어 주어진다. ( $1 \le N, M \le 300\,000;$ $N \times M \le 1\,000\,000$ )

그다음 줄에 빛의 스크롤 종류의 수를 나타내는 정수 $S$ 가 주어진다. ( $1 \le S \le N$ )

그다음 줄에 각 빛의 스크롤 특성값을 나타내는 $S$ 개의 서로 다른 정수 $A_1, A_2, \cdots, A_S$ 가 공백으로 구분되어 주어진다. ( $1 \le A_i \le N$ )

그다음 줄에 어둠의 스크롤 종류의 수를 나타내는 정수 $T$ 가 주어진다. ( $1 \le T \le M$ )

그다음 줄에 각 어둠의 스크롤 특성값을 나타내는 $T$ 개의 서로 다른 정수 $B_1, B_2, \cdots, B_T$ 가 공백으로 구분되어 주어진다. ( $1 \le B_i \le M$ )

그다음 줄에 시간의 길이를 나타내는 정수 $Q$ 가 주어진다. ( $1 \le Q \le 300\,000$ )

이어지는 $Q$ 개의 줄의 $i$ 번째 줄에는 시각 $i$ 에 타일 마스터가 타일의 문양을 조작하는 방법을 나타내는 네 정수 $sx_i$ , $sy_i$ , $ex_i$ , $ey_i$ 가 공백으로 구분되어 주어진다. ( $1 \le sx_i \le ex_i \le N;$ $1 \le sy_i \le ey_i \le M$ )

출력 형식

첫 줄에 정답을 나타내는 길이 $Q$ 의 문자열을 출력한다. 이 문자열은 Y와 N으로만 이루어져 있어야 한다. $i$ 번째 문자가 Y이면 시각 $i$ 에 타일 상태가 아름다운 패턴인 것이고, N이면 그렇지 않은 것을 의미한다.

예제

입력

6 8 1 4 2 6 7 4 1 1 4 8 1 5 6 8 1 3 4 4 5 3 6 4

출력

YNNY

예제 설명

시각 $1$ 의 타일 상태는 첫 번째 빛의 스크롤으로 $1$ , $2$ , $3$ , $4$ 행을 뒤집어 모든 타일이 빛의 문양이 위로 향하도록 만들 수 있다.

시각 $4$ 의 타일 상태는 첫 번째 빛의 스크롤으로 $1$ , $2$ , $3$ , $4$ 행을 뒤집은 후, 첫 번째 어둠의 스크롤으로 $3$ , $4$ , $5$ , $6$ , $7$ , $8$ 열을 뒤집어 모든 타일이 빛의 문양이 위로 향하도록 만들 수 있다.

시각 $2$ 와 $3$ 의 타일 상태는 스크롤을 어떻게 사용해도 모든 타일이 빛의 문양이 위로 향하도록 만드는 것이 불가능하다.

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.

종류 1: 14점

$A_1 = 1;$ $B_1 = 1$

종류 2: 8점

$N, M \le 500;$ $N \times M \times Q \le 10\,000\,000$

종류 3: 38점

$N, M \le 2\,000$

종류 4: 15점

$N = 1$ 또는 $M = 1$

종류 5: 25점

추가적인 제한 조건이 없음.

해설

편의를 위해, 빛의 문양이 위를 향하는 타일을 $0$ , 어둠의 문양이 위를 향하는 타일을 $1$ 로 표현하자. 아름다운 패턴은 스크롤을 사용하여 모든 타일을 $0$ 으로 만들 수 있는 격자판의 상태를 뜻한다.

$N$ 행 $M$ 열의 격자판에서 각 타일의 상태를 $W_{i,j}$ 로 정의하자. 여기서 $W_{i,j} = 0$ 이면 $i$ 행 $j$ 열의 타일이 빛의 문양을 위로 향하고 있음을, $W_{i,j} = 1$ 이면 어둠의 문양이 위로 향하고 있음을 나타낸다. 타일을 뒤집는 연산은 타일의 상태를 $0$ 과 $1$ 사이에서 전환하는 것이므로, 모든 연산은 $\bmod\,2$ 로 생각할 수 있다. 타일의 상태 변화를 추적하기 위해, 누적 합과 유사한 개념인 변환값 배열 $w_{i,j}$ 를 정의하자: $w_{i,j} = W_{i,j} - W_{i-1,j} - W_{i,j-1} + W_{i-1,j-1} \pmod{2}$

단, $W_{i,0}$ 과 $W_{0,j}$ 는 모두 $0$ 으로 간주한다. 이렇게 정의하면, $W_{i,j}$ 는 다음과 같이 표현할 수 있다: $W_{i,j} = \sum_{1 \le x \le i,\ 1 \le y \le j} w_{x,y} \pmod{2}$

타일 마스터가 $[sx, ex] \times [sy, ey]$ 범위의 타일을 뒤집는 연산은 $w$ 배열에서 다음과 같은 변화를 일으킨다:

\begin{align*} w_{sx, sy} &\leftarrow w_{sx, sy} + 1 \pmod{2} \\ w_{sx, ey+1} &\leftarrow w_{sx, ey+1} - 1 \pmod{2} \\ w_{ex+1, sy} &\leftarrow w_{ex+1, sy} - 1 \pmod{2} \\ w_{ex+1, ey+1} &\leftarrow w_{ex+1, ey+1} + 1 \pmod{2} \end{align*}

따라서, 모든 타일에 대한 $w_{i,j}$ 값을 관리함으로써 타일의 상태 변화를 추적할 수 있다.

빛의 스크롤의 사용은 $sy = 1, ey = M$ 인 경우로 생각할 수 있고, 어둠의 스크롤의 사용은 $sx = 1, ex = N$ 인 경우로 볼 수 있다. 따라서, 스크롤을 사용하여 모든 타일을 $0$ 으로 만들기 위해서는 $w_{i,j}$ 에 대해 다음이 성립해야 함을 의미한다:

모든 $1 < i \le N$ , $1 < j \le M$ 에 대해 $w_{i,j} = 0$ 이어야 한다.
$w_{i,1}$ 과 $w_{1,j}$ 는 스크롤을 통해 조작할 수 있으므로, 적절한 스크롤 사용으로 $0$ 으로 만들 수 있어야 한다.

타일 마스터가 타일의 문양을 조작할 때마다 바뀌는 $w_{i,j}$ 값이 $4$ 개이므로, 이 값들은 계속 들고 있을 수 있다. $1 < i \le N, 1 < j \le M$ 인 $i,j$ 에 대해 $w_{i,j} = 0$ 을 만족할 때, $w_{i,1}$ 과 $w_{1,j}$ 들의 값으로부터 아름다운 패턴인지 효율적으로 판단할 수 있으면 문제를 해결하는 데에 충분하다.

$i$ 번째 빛의 스크롤을 사용하면 $1 \le s \le N+1-A_i$ 을 만족하는 $s$ 를 하나 골라 $w_{s,1}$ 과 $w_{s+A_i,1}$ 에 1을 더하는 연산을 할 수 있다. $j$ 번째 어둠의 스크롤을 사용하면 $1 \le t \le M+1-B_j$ 을 만족하는 $t$ 를 하나 골라 $w_{1,t}$ 과 $w_{1,t+B_j}$ 에 1을 더하는 연산을 할 수 있다. 이를 통해 $w_{i,1}$ 과 $w_{1,j}$ 들을 모두 $0$ 으로 만들 수 있는지 확인하면 충분하다.

빛의 스크롤로 모든 $w_{i,1}$ 들을 $0$ 으로 만들 수 있는지, 그리고 어둠의 스크롤로 모든 $w_{1,j}$ 들을 $0$ 으로 만들 수 있는지 확인하면 충분하다. 빛의 스크롤로 모든 $w_{i,1}$ 들을 $0$ 으로 만들 수 있는지를 확인하는 방법은 다음과 같다.

$1$ 번부터 $N+1$ 번 까지 정점이 있고, $1 \le i \le S$ 에 대해 번호가 $A_i$ 만큼 차이나는 모든 정점 쌍을 간선으로 연결한 그래프를 생각해 보자. 그래프의 $i$ 번 정점에 있는 값을 $w_{i,1}$ 라고 할 때, 간선의 양 끝점의 값을 반전시키는 연산으로 모든 값을 $0$ 으로 만들 수 있으면 된다. 그리고 이는 각 컴포넌트에서 $w_{i,1}$ 의 합이 짝수인 것과 동치가 된다. 따라서, 그래프의 컴포넌트를 알면 각 컴포넌트 별 $w_{i,1}$ 의 값들의 합을 관리함으로써 문제를 해결할 수 있다.

다음과 같은 문제를 생각해보자: 그래프 $G$ 에 $1, 2, \ldots, n$ 번의 $n$ 개의 정점이 있을 때, 다음과 같은 쿼리들을 처리하며 disjoint set union 자료구조를 유지하여라.

$\text{Uni}(k, a, b)$ : $0 \le i < k$ 인 모든 $i$ 에 대해 $G$ 에 간선 $(a+i, b+i)$ 추가

$level = 0, 1, \ldots , \log n$ 인 그래프를 생각하자. $level = i$ 인 그래프에서 정점 $a$ 와 $b$ 가 같은 컴포넌트라는 것은 $G$ 에서 $0 \le t < 2^i$ 인 $t$ 에 대해 $a+t$ 와 $b+t$ 가 같은 컴포넌트임을 뜻한다. 그러면 $\text{Uni}(k,a,b)$ 쿼리는 처음에 $level = \lfloor \log k \rfloor$ 인 그래프에 간선을 추가하고, 높은 level의 그래프로부터 낮은 level의 그래프로 전파하는 방식으로 ( $level = i$ 인 그래프에서 간선 $(a,b)$ 가 추가되면 $level = i-1$ 인 그래프에 $(a,b), (a + 2^{i-1}, b+2^{i-1})$ 추가) Union find를 해주면 최종적으로 $level = 0$ 은 $G$ 와 동일한 컴포넌트 구조를 가지게 된다. 이 때 시간복잡도는 $\log n$ 개의 그래프에서 union find가 이루어지므로 모든 쿼리가 끝났을 때의 그래프의 연결 상태는 $O((n+Q) \log n \cdot \alpha(n))$ 시간에 효율적으로 계산된다. 빛의 스크롤에 관한 문제는 이 문제의 subproblem이므로, 그래프의 컴포넌트를 계산할 수 있다.

따라서, 처음에 주어진 $A_i$ 와 $B_i$ 들을 바탕으로 그래프의 컴포넌트를 계산해 놓으면 타일 마스터가 타일의 문양을 조작할 때마다 $w_{i,j}$ 들의 값의 변화를 관리하면서 그래프에서 모든 컴포넌트가 짝수 합을 가지는지까지 체크해주면 아름다운 패턴인지 아닌지를 판정할 수 있다.