113. Airplane!
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're flying an airplane, but you forgot to forgot to refill the fuel tank before you trip. Therefore, you must decide which airport to land at based on a number of factors: proximity, available runway space, and direction. If an airport has no available spaces, you cannot go there. If an airport is too far away, you cannot go there.

Input

You will receive 3 lines of input, the first being n number of airports, the second being how many miles you can fly, and the third being the direction of the wind (N,S,W,E,NW,NE,SW,SE). Then you will receive n lines of input consisting of 3 variables separated by spaces: the number of available runway spaces, the distance to the airport in miles, and the direction you must fly to get to the airport.

Output

You will output a number that represents which airport you should fly to.

Example
Input
2
20
S
1 20 S
1 20 N
Output
1
Note

If you are flying with the wind direction, the amount of fuel you need to use is halved. If you are flying against the wind direction, it takes two times as much fuel to get to the airport.