By Felipe Rasinhas, IME Brazil
During his last visit to planet Tatooine, Han Solo was captured by Jabba, the Hutt's mercenaries and was taken to his palace. Jabba, knowing that Solo was still not able to pay his debts, proposed a deal. Both would to play a game of Intergalactic Nim, and if Han won, he would be clear of his debts, otherwise, his debt would double.
Intergalactic Nim is a variation of the well known game of Nim, where stones are arranged in columns and on each turn a player must remove one or more stones from one of the columns. The player that is unable to make a move is considered the loser. On Intergalactic Nim one of the players (in this case Jabba) picks a number N and the stones are arranged in N columns, with the i-eth column having i stones (First column with 1 stone, second column with 2 stones, and so on).
Having great knowledge in these kinds of games, and knowing that who makes the first move (in this case Jabba) is more likely to win the game, Han proposed a little change to the game. He would be able to pick three integers A, B and K and add K stones to every column between columns A and B (inclusive). Jabba accepted the proposal but added a limitation, Jabba's counselor would consider Q possible operations of this type and Solo would have to apply each of these operations independently to the original game. Since Han is not accompanied by his fellow friend Chewbacca (that usually helps him in these situations), he asked you to help him beat Jabba.
The input consists of several test cases and ends with EOF.
The first line of a test case consists of two integers N (1 <= N <= 1018) and Q (Q <= 105), the number picked by Jabba, and the number of operations suggested by the counselor.
The next Q lines consist in 3 integers A, B (1 < = A <= B <= N) and K (-A <= K <= 1018) describing each operation selected by the counselor.
For each test case, the output consists of Q lines containing the winner of the game (considering both players play optimally) for each one of the operations suggested.
|Sample Input||Sample Output|
4 6 5
3 6 -2
1 1 8