A La Vega Roulette is like a normal Roulette. It is a circular shape with numbers written down on the edge so that they fill up the whole circumference line. It differs from the well-known Roulette in two aspects. First, all numbers have the same color. Second, there is a marker right at the top of the center of the Roulette.

Natalia and Luis are bored and decided to play "Battle of the Spins" with a La Vega Roulette. On her first turn, a player rotates the La Vega Roulette such that the first number is below the marker. Then, she spins the Roulette and writes down the number that landed on the marker. She also records the position of the Roulette. In subsequent turns, the player must first rotate the Roulette back to the position where it ended in her previous turn, spin, sum the new marked number to her current sum and record again the position.

After both players take a turn then a decision must be made to whether continue playing or announce verdict. Let's say the sum of Player 1 and Player 2 are S1 and S2, respectively. If S1 - S2 > K, Player 1 wins and the game is over. If S2 - S1 > K, then Player 2 wins. However, if S1 - S2 = 0, the game is a draw and ends immediately. If none of the previous conditions apply, the game continues.

You are given the amount of numbers by which the La Vega Roulette spun after each player's turn. Please output the result of the battle.

Input

The first input line contains two space-separated integers N (2 ≤ N ≤ 10³), the size of the list of numbers along the La Vega Roulette's circumference and K (100 ≤ K ≤10⁵), the threshold. Then there's a second line with N space-separated 32-bit integers. Each of these integers represent the i^th number written down on the circumference. Then there are many lines. Each of these lines contain two space-separated integers Spin1 and Spin2 (1 ≤ Spin1, Spin2 ≤ 10⁵). Each represent the amount of numbers by which the La Vega Roulette rotated in Player 1's and Player 2's turns, respectively. It is guaranteed that there are sufficient lines to reach a verdict.

Output

Please output the answer to this problem. If Player 1 wins, write "P1". If Player 2 wins, write "P2". If there's a draw, write "BAD LUCK".

Example

Input:
6 120
6 5 1 80 10 50
3 2
2 5

Output:
P1

Note: In this test case, both players start at the first position. After the first round, Player 1 writes down 80 and Player 2 writes down 1. Because S1 - S2 and S2 - S1 are not zero and neither greater than K = 120, the game takes another round.

After the second round, Player 1 writes down 50 and Player 2 writes down 5. Now S1 = 80 + 50 = 130 and S2 = 1 + 5 = 6. Because S1 - S2 = 124 > 120, Player 1 wins and the game is over.