Problem J
Spies vs. Spies

Spies vs. Spies is a large group game. Every team consists of exactly two players: a spy and a handler. The spies are placed at integer points $(x,y)$ in the playing field which we view as a Cartesian plane.

A turn consists of a team’s handler telling their team’s spy to look in one of the four cardinal directions: North (N), South (S), East (E), or West (W). Here, North is in the direction of the positive $y$-axis.

That team’s spy will look carefully in that direction from their location. All spies they see in that direction are eliminated. To be precise, when a spy $i$ at location $(x,y)$ looks in one of the four directions, they only see other spies that lie exactly on the straight line originating from $(x,y)$ and drawn in the direction that spy $i$ is looking. For example, if a spy at $(5,7)$ looks North (N) they only see other spies with coordinates $(5,y)$ where $y > 7$. The spies are eliminated in order from closest to farthest from spy $i$’s position.

You are reviewing the transcript of instructions that were given over a series of turns. Determine which spies were eliminated in each turn.

A depiction of the initial layout of the three spies and the results of each instruction. A grey circle indicates the spy has not yet been eliminated, a white circle indicates the spy has been on that turn or earlier.

Input

The first line consists of two integers $N$ ($1 \leq N \leq 300\, 000$) indicating the number of teams and $M$ ($1 \leq M \leq 300\, 000$) indicating the number of turns. Teams are numbered from $1$ to $N$.

Then $N$ lines follow, the $i$-th such line contains two integers $x_i, y_i$ ($-10^9 \leq x_i,y_i \leq 10^9$) indicating the position of the $i$-th team’s spy. No two spies will be at the same location.

Then $M$ lines follow. The $i$-th line contains one integer $t_i$ ($1 \leq t_i \leq N$) and a direction N, S, E, or W. This indicates the handler of team $t_i$ instructed their spy to look in that direction.

Output

Output a single line for each instruction. For the $i$-th line, if the spy for team $t_i$ was eliminated in a previous turn, output ignore. Otherwise, output the number of spies that were eliminated followed by the list of the team numbers of all spies that were eliminated, in the order their spies were eliminated.

3 6
0 0
1 2
1 0
1 N
3 W
1 E
2 S
2 E
3 N

0
1 1
ignore
1 3
0
ignore

5 4
0 0
1 0
2 0
3 0
4 0
5 N
4 E
3 W
4 W

0
1 5
2 2 1
1 3