33415번 - 타일 마스터의 시련

문제

메이플스토리의 새로운 지역, "리버스 시티"에서는 마법 타일이 $N$ x $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 300000; N \times M \le 1000000$)

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

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

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

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

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

이어지는 $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이면 그렇지 않은 것을 의미한다.

제한

힌트