Naval Battle Survival

This problem is based on the CEOI 2024 Day1 T1 "Naval battle" task.

The Czech Navy commander, recently promoted to Grand Admiral, faces the dramatic possibility of his navy being abolished. In order to prove the importance of his navy, he has learned that a massive naval battle involving four nations is about to occur. Although the Czech Navy lacks ships and ports, the commander hopes that by seizing enemy warships the battle can be tilted in his favor. The key question is: which ships will survive the battle?

Battle Rules:

• Before the battle, the i-th ship is located at coordinates \((x_i, y_i)\), where both \(x_i\) and \(y_i\) are even integers. Each ship belongs to one of the four fleets: North, South, East, or West.
• The battle consists of rounds. In each round:
  1. Every ship simultaneously moves one cell in the direction of its fleet:
     • North fleet: \(y\) decreases by 1 \(\rightarrow y-1\).
     • South fleet: \(y\) increases by 1 \(\rightarrow y+1\).
     • East fleet: \(x\) increases by 1 \(\rightarrow x+1\).
     • West fleet: \(x\) decreases by 1 \(\rightarrow x-1\).
  2. If two or more ships occupy the same cell after moving, they collide and sink immediately; those ships are removed from the battle.
• The battle stops as soon as a round finishes in which no collisions occur. The surviving ships are those still on the map at that time.

Your task is to simulate the battle and determine the final positions of the surviving ships.

inputFormat

The first line contains an integer \(n\) (the number of ships).

Each of the following \(n\) lines contains two space-separated integers \(x_i\) and \(y_i\) (the initial coordinates of a ship, both even), followed by a character \(d\) that represents the fleet direction. \(d\) is one of:

• 'N' for the North fleet,
• 'S' for the South fleet,
• 'E' for the East fleet,
• 'W' for the West fleet.

outputFormat

Output the number of surviving ships on the first line. Then, for each surviving ship, output a line containing two space-separated integers representing its final \(x\) and \(y\) coordinates.

The survivors should be listed in the same order as they appear based on the simulation (i.e. in the order in which they survive through the rounds).

sample

4
0 0 N
0 2 S
2 0 W
2 2 E

4
0 -1
0 3
1 0
3 2