402199: GYM100694 I Goat in the Field

Goat Tanya accidentally got out of the garden and found herself in the field. The goat got confused since she haven't been here before so she decided to walk straight in the certain direction. The field consists of the infinite number of 1 × 1 cells, and each of these cells is connected with four other cells by their sides. In a single turn the goat moves to the adjacent cell in her movement direction.

Shepherds have noticed the disappearence and try to catch the goat. Every shepherd in his turn can move in any direction by one or two cells, but he can't change the direction during the turn. They also can just stand in their cells instead of moving. The goat is catched if some shepherd at the end of his turn is located in the goat's cell. At the beginning no shepherd is located in the same cell as the goat.

Tanya and shepherds move in rotation — the goat moves first, and then the shepherds move in the same order as in the input. Your task is to find which shepherd will be the first to catch the goat.

The first line contains two integers x, y (|x|, |y| ≤ 1000) — the initial coordinates of the goat.

The second line contains a string s which determines the goat's movement direction. s can be one of the four following strings (the quotes are for clarity):

• «LEFT» — the goat moves to the left, x coordinate decreases by 1,
• «RIGHT» — the goat moves to the right, x coordinate increases by 1,
• «UP» — the goat moves to the top, y coordinate increases by 1,
• «DOWN» — the goat moves to the bottom, y coordinate decreases by 1.

The third line contains one integer n (1 ≤ n ≤ 1000) — the number of shepherds.

The i-th of the n following lines contains a string () of lowercase Latin letters, and two integers x_i, y_i (|x_i|, |y_i| ≤ 1000) — the name of the i-th shepherd and his initial coordinates. It's guaranteed that all names are distinct.

Output a single string — the name of the shepherd which will catch the goat first.

0 0
LEFT
3
andrew -10 0
denis 10 0
ilia 0 10

andrew

10 2
UP
3
danila 5 4
sashac 11 1
sashab 12 10

sashac

0 0
UP
2
mike 2 1
constantine 0 1

mike