Uolevi is playing a game where his goal is to get from the lowest floor to the highest floor. The game consists of n floors, and each of them is infinitely wide. Uolevi can move left or right on the current floor, or jump upward to the next floor at any point of the game. It is not possible to move downward to the previous floor.

At the beginning Uolevi has w units of energy. Uolevi uses one unit of energy when moving one unit left or right and k units of energy when jumping up. If Uolevi runs out of energy, he can't move anymore. Some floors provide an energy drink at some coordinate. After drinking an energy drink, Uolevi gains more energy. Uolevi starts on floor 1, x-coordinate q, and his goal is to get to any x-coordinate of floor n. Your task is to find out if it is possible to win the game.

Input

The first line of the input contains four integers, n, q, w and k. n is the number of floors, q is the initial x-coordinate of Uolevi, w is the initial amount of energy Uolevi has and k is the amount of energy jumping up costs. Then follow n lines. If floor i doesn't have an energy drink, line i contains single integer, 0. If there is an energy drink on floor i, line i contains three integers, 1, x_i and e_i. x_i is the x-coordinate of the energy drink, and e_i is the amount of energy it provides.

Output

Output 10-4 if Uolevi can win the game, and QAQ if Uolevi can't win the game.

Constraints

• 2 \le n \le 10^5
• 1 \le q \le 10^5
• 1 \le w \le 10^9
• 1 \le k \le 10^4
• 1 \le x_i \le 10^5
• 1 \le e_i \le 10^9

Examples

Input:

10 3 7 2
1 5 3
0
1 1 4
0
1 5 5
1 3 2
1 3 6
1 6 2
1 1 1
0

Output:

10-4

Input:

3 4 4 3
0
1 3 2
1 2 5

Output:

QAQ