B. MLG 360 No Scope
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Edward isn't just a gamer — he's the gamer. The man, the myth, the MLG legend. His KD ratio is higher than your GPA, his scope sensitivity defies the laws of physics, and his Wi-Fi connection? Blessed by the gods of low latency themselves.

He's dropped into a digital warzone — a chaotic grid where enemies spawn like lag spikes in a ranked match. There are $$$N$$$ poor souls scattered across the map, blissfully unaware that Edward "NoScopeKing420" is about to go absolutely feral.

He locks in. His avatar faces one of eight sacred gamer directions: North, Northeast, East, Southeast, South, Southwest, West, or Northwest.

He will perform this MLG move by spinning 360 degrees, and then firing his rifle. His rifle will shoot a bullet that travels straight in the direction he is facing after he turns 360 degrees, and will hit the first entity it encounters. Please find out which poor soul Edward hits.

Input

The first line contains $$$n, e_x, e_y$$$, the amount of enemies, and the $$$x, y$$$ coordinates that Edward is at. $$$1 \leq n, e_x, e_y \leq 10^5$$$

The second line contains $$$s$$$ a string representing the direction Edward is facing. This string will be in full caps, matching one of the directions specified in the statement.

The next $$$n$$$ lines will contains $$$2$$$ integers each $$$x_i, y_i$$$ representing the coordinates of the $$$i$$$th enemy. $$$1 \leq x_i, y_i \leq 10^5$$$

Output

Output $$$2$$$ integers, $$$x, y$$$, the coordinates of the enemy Edward hit. Output $$$-1$$$ if Edward does not hit anyone.

Examples
Input
1 1 1
NORTHEAST
3 3
Output
3 3
Input
2 1 1
NORTHEAST
3 4
4 3
Output
-1
Input
1 1 1
NORTH
1 1
Output
1 1
Note

Input
1 1 1
NORTHEAST
3 3
  • There is one enemy.
  • Edward's position is $$$(1, 1)$$$.
  • Edward is facing NORTHEAST, meaning the bullet travels diagonally upward to the right, increasing both $$$x$$$ and $$$y$$$ equally.

The bullet travels along the line: [ (1, 1) , (2, 2) , (3, 3) ... ] The only enemy is located at $$$(3, 3)$$$, which lies directly along this path.

—


Input
2 1 1
NORTHEAST
3 4
4 3
  • There are two enemies.
  • Edward's position is $$$(1, 1)$$$.
  • Edward is facing NORTHEAST, so the bullet moves along the diagonal line $$$y = x$$$.

The bullet's path is: [ (1, 1) , (2, 2) , (3, 3) , (4, 4) ... ]

Check the enemies: $$$$$$ (3, 4): \text{ not on } y = x \qquad (4, 3): \text{ not on } y = x $$$$$$

Neither enemy lies on Edward's line of fire, so he hits no one.

—

Aftermath

As the smoke clears and the echoes of the shot fade, Edward lowers his rifle. In the first match, he lands a perfect 360 no-scope — chat goes wild, airhorns blast, and the killfeed lights up. In the second? A clean miss. The enemies live to tell the tale, but only barely. Somewhere, a dubstep remix begins to play as Edward reloads, ready for the next highlight reel moment.