Agent 47 is on an important mission and needs to finish an assignment (kill the target) at a casino. Now the target is playing a card game, where the shuffling of cards are done in a unique way. Suppose, there are N numbered cards and initially all cards are facing down placed in a stack with 1 being at the top and N at the bottom of the stack. The dealer performs the following steps for one shuffling move :

1. First the dealer picks A cards from the top of the stack.
2. Then the dealer picks B cards from the top of the stack.
3. Puts the A cards back on the top of the stack as a block.
4. Picks C cards from the top.
5. Places all the B cards that were picked in the second move, card by card back onto the top of stack.
6. Puts C cards on the top of stack as a block.

Now, agent 47 wants to play the game too, but to ensure his victory in the game he requests Diana to find out the final order of the cards in the stack after the dealer performs all the moves. Help 47!!!

Note: taking a block of cards from the top of the deck does not change their order. The entire block is removed in a single move and not card by card. The only exception is the fifth move, where you return cards one by one to the top.

Input:

• The first line of input contains an integer T (no. of test cases).
• Each test case contains two integers N and M, where N is the number of cards and M are the number of moves that a dealer makes.
• Next M lines contains 3 integers A,B and C respectively, representing a single move as described above.

Output:

For each test case print a new line which contains the order of the stack of cards separated by " "( spaces) .

Constraints:

• 1<=T<=5
• 1<=N,M<=10⁵

Note: It is guaranteed that the combination of A,B,C will be valid.