battle — CEOI contest
Task type: batch | Time limit: 3 s | Memory limit: 1024 MB | Difficulty: 21
Algorithms: data structures, simulation, tree map, priority queue, implementation, linked list

# Naval battle

Ondra has recently been promoted to Grand admiral of the Czech Navy.
However, when he finally started thinking he had a secure job,
the government announced budget cuts including dissolution of the Navy.

So Ondra decided to show the government how important the Czech Navy is.
He knows from his spies about an upcoming naval battle of four great fleets.
If he could win it, it would surely make enough of a demonstration.

Unfortunately, the Czech Navy has neither warships nor sea ports. But if
Ondra's spies took over some ships he might have a chance.
If only he knew which ships will survive the battle…

A naval battle goes as follows: Initially ship $i$ starts on square
$(x_i, y_i)$, where both $x_i$ and $y_i$ are even. Additionally,
the ship belongs to one of the four fleets: Northern, Southern, Eastern or Western.
Then the battle proceeds in steps. In each step:
- First, each ship simultaneously moves one square in the direction corresponding to its fleet.
- If two or more ships now occupy the same square, they sink and disappear from the map.

The battle ends when no crashes are possible anymore. A _surviving ship_ is a ship that remains on the map after the end of the battle.

A ship moves according to the direction of its fleet.
The movement in each direction changes its coordinates as follows:
- Northern — decreases the $y$ coordinate by 1
- Southern — increases the $y$ coordinate by 1
- Eastern — increases the $x$ coordinate by 1
- Western — decreases the $x$ coordinate by 1

## Input
The first line of inputs contains an integer $N$. Then $N$ lines follow, each
containing $x_i$, $y_i$, and $d_i$, separated by spaces. The integers $x_i$ and $y_i$ are the coordinates of the $i$-th ship.
The character $d_i$ is either `N`, `S`, `E` or `W`, describing the direction of the $i$-th ship's fleet.

No two ships initially have the same coordinates.
That is, for ships $i$ and $j$ ($i \neq j$) either $x_i \neq x_j$ or $y_i \neq y_j$.

## Output
For each _surviving ship_, output a single line containing the integer
$i$ ($1 \leq i \leq N$) — the number of the ship.
You can output the numbers of _surviving ships_ in any order.

If there are no _surviving ships_, the output should be empty.

## Examples

### Example 1
Input:
```
7
0 6 E
0 8 E
2 4 E
4 2 S
6 0 S
6 2 S
6 4 S
```
Output:
```
7
```

<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>

The battle will initially look like this:
![](battle-sample1-v2.svg)

And then it proceeds as follows:
- During step 2, ships 3 and 4 will collide at $(4, 4)$.
- During step 6, ships 1 and 5 will collide at $(6, 6)$.
  At the same time 2 and 6 will collide at $(6, 8)$.
The only _surviving ship_ will be number 7.

### Example 2
Input:
```
5
4 0 S
0 2 E
2 2 E
4 4 N
6 6 W
```
Output:
```
5
2
```
![](battle-sample2.svg)

During the second step, ships 1, 3 and 4 will collide at $(2, 4)$. Ships 2 and 5 will survive.

## Constraints
- $2 \leq N \leq 2 \cdot 10^5$
- $0 \leq x_i, y_i \leq 10^9$ (for each $i$ such that $1 \leq i \leq N$) and $x_i, y_i$ are even.

## Subtasks
1. (6 points) $N = 2$
2. (12 points) $N \leq 100$, $x_i, y_i \leq 100$ (for each $i$ such that $1 \leq i \leq N$)
3. (8 points) $N \leq 100$, $x_i, y_i \leq 10^5$ (for each $i$ such that $1 \leq i \leq N$)
4. (11 points) $N \leq 200$
5. (9 points) $N \leq 5\,000$
6. (30 points) $d_i$ is either `S` or `E` (for each $i$ such that $1 \leq i \leq N$)
7. (24 points) _no additional constraints_


Starter code: