Woburn Challenge 2018-19 Round 2 - Senior Division

The IMF (Impossible Mission Force) has dispatched their best agent, Ethan Hunt, to recover a recently stolen microchip. This microchip contains critical Canadian governmental secrets, such as the Prime Minister's favourite colour, and must be recovered before its captors have time to download its data!

Ethan has tracked the microchip down to an underground base in Saskatchewan. Upon infiltrating it, he's found himself in the middle of a gigantic, square room. When viewed from above, the room can be represented as a square on a 2D plane, with its bottom-left corner at coordinates $(0,0)$ and its top-right corner at coordinates $(1000000,1000000)$. Ethan has lowered himself down into the room, and is standing at coordinates $(X_E,Y_E)$ ($1\le X_E,Y_E\le 999999$).

There are $N$ $(0\le N\le 100000)$ vertical lasers extending across the entire room, the $i$-th of which is a line segment from coordinates $(V_i,0)$ to $(V_i,1000000)$ ($1\le V_i\le 999999$). There are also $M$ ($0\le M\le 100000$) horizontal lasers extending across the entire room, the $i$-th of which is a line segment from coordinates $(0,H_i)$ to $(1000000,H_i)$ ($1\le H_i\le 999999$). All vertical lasers have distinct $V$ values, all horizontal lasers have distinct $H$ values, and no laser goes directly through Ethan's location (in other words, no $V$ value is equal to $X_E$, and no $H$ value is equal to $Y_E$).

Ethan was hoping to simply find the stolen microchip, but he's been greeted by a more troubling sight: there are $C$ ($1\le C\le 100000$) microchips strewn about the room! The $i$-th microchip is at coordinates $(X_i,Y_i)$ ($1\le X_i,Y_i\le 999999$). No two microchips are at the same location, no microchip is at Ethan's location, and no laser goes directly through any microchip's location.

One of these $C$ microchips must be the real one, with the rest being decoys, but they all look identical! Unfortunately, Ethan will only have time to go grab at most one of them before getting out of there. To make matters even worse, Ethan may not pass through any lasers on his way to pick up the microchip of his choice, as they'd trigger an alarm. He'll need to weigh his options and choose his plan of action carefully!

For each microchip, determine whether or not Ethan would be able to reach its location from $(X_E,Y_E)$ by following any continuous path on the $2D$ plane (not necessarily a straight line segment), without leaving the confines of the room and without passing through any of the $N+M$ lasers.

Subtasks

In test cases worth $5/13$ of the points, each integer in the input is no greater than $10$.
In test cases worth another $5/13$ of the points, $N\le 2000$, $M\le 2000$, and $C\le 2000$.

Input Specification

The first line of input consists of two space-separated integers, $X_E$ and $Y_E$.
The next line consists of three space-separated integers, $N$, $M$, and $C$.
$N$ lines follow, the $i$-th of which consists of a single integer, $V_i$, for $i=1\dots N$.
$M$ lines follow, the $i$-th of which consists of a single integer, $H_i$, for $i=1\dots M$.
$C$ lines follow, the $i$-th of which consists of two space-separated integers, $X_i$ and $Y_i$, for $i=1\dots C$.

Output Specification

Output $C$ lines with a single character per line, either Y if Ethan would be able to reach the $i$-th microchip, or N otherwise, for $i=1\dots C$.

Sample Input

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

Sample Output

N
Y
N
N
Y

Sample Explanation

The room is illustrated below, with lasers indicated in red, Ethan's location in green, and the microchips in blue. Note that most of the x-coordinates and y-coordinates on the plane (from around $10$ to around $999997$) have been collapsed together.

Ethan would only be able to reach the $2$nd or $5$th microchip.