Description

TA Penguin07 wants to play a game with N people. Initially, these N people are lined up and numbered from 1 to N.

TA Penguin07 will issue K commands, commands i is represented as a pair of integers (T_i, A_i, B_i), and is the following operation:

• If T_i = 1, the person with number A_i have to kill min(C, B_i) people behind them. Here, C represents the number of people remaining behind them at the moment of the command.
• If T_i = 2, the person with number A_i have to kill min(C, B_i) people in front of them. In this case, C represents the number of people remaining in front of them at the moment of the command.

However, Penguin07 has poor eyesight and cannot clearly see who has been killed from the long line. So, after each command issued by Penguin07, you need to tell Penguin07 who was killed.

If the command is invalid (that person has already been killed or there is no one been killed), you should output "Penguin07 QQ" (with no quotes).

Input

The first line contains two positive integers, N and K.

The following K lines, each line represents a command in the format of three integers: (T_i, A_i, B_i).

Constraints

• Testcases 1 ~ 4: T_i = 1, B_i = 1
• Testcases 5 ~ 6: satisfy no additional constraints.
• For all test cases: 1 ≤ N, K ≤ 2 * 10⁶, 1 ≤ T_i ≤ 2, 1 ≤ B_i ≤ 10⁹, 1 ≤ A_i ≤ N

Output

Remember to print a ‘\n’ at the end of the output.

Do not include any spaces at the end of line.

Hint

The test data for this problem is quite large, so if you're using C++ to solve it should include IO optimization in your program.

IO Optimization usage

remember to replace endl with '\n'.

#include<iostream>
...

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    /* write your code here*/
    
} 

Sample Input  Download

Sample Output  Download

Tags

Discuss