Playing With Operators
By Anderson Silva, ICMC - USP 
Brazil
By Anderson Silva, ICMC - USP Brazil
Rusa and Sanches are friends at the primary school. This month, they are learning how to sum and subtract integers numbers. Their math teacher gave a nice exercise to practice those new operators. The exercise is a game (to improve the interest of the pupils). It is necessary that the two pupils do it together and, as Rusa and Sanches are always doing tasks together, this one will not be different. The teacher gave them many integer sequences to play. For each sequence, their movements are the following:
- First Player: Generate a new sequence using the sum of the first and second numbers, third and fourth, fifth and sixth, etc.
- Second Player: Generate a new sequence using the subtraction of the first and second numbers (in this order), third and fourth, fifth and sixth, etc.
If the size of the sequence is odd, the last number should be left unchanged. The players alternate turns. The game lasts until there is only one number in the sequence, called the last number. If it is odd, then the first player wins, otherwise the second wins. As you can see the game is very predictable, they can't change the final result given an initial sequence. Moreover, the teacher also asked them to calculate the last number of the sequence after replacing one of the numbers in the initial sequence. There will be several replacements, and for each one they must play the game again. These replacements are cumulative.
Both of them need to learn how to add and subtract, thus on the first test case, Rusa will be the first player and Sanches the second. On the second test case, they change the order, i.e., Sanches is the first player and Rusa is the second. On the third one they swap again, and so on.
The teacher gave too many sequences to Rusa and Sanches. They are bored of that exercise because they already learned the lesson. They need to solve all the games until the end of the week and they are asking you to help them with that.
For example, let's assume that the initial sequence is (4, 2, 3, 5, 1, 6, 10, 2). Then, the movements are: (4, 2, 3, 5, 1, 6, 10, 2) → (6, 8, 7, 12) → (-2, -5) → (-7). The last number is -7, and the winner is Rusa, because -7 is odd, and it is the first test case.
Take a second example, let's assume that the initial sequence is (4, 2, 3). Then, the movements are: (4, 2, 3) → (6, 3) → (3). The last number is 3, and the winner is Sanches, because 3 is odd, and it is the second test case.
The first line will contain a number T (1 ≤ T ≤ 100), how many test case will follow. For each test case, the first line will contain a number N (1 ≤ N ≤ 104) and Q (0 ≤ Q ≤ 104), the number of integers in the sequence and the number of replacements in the initial sequence, respectively. The next line contain N integers of the sequence S1, S2, …, SN (-104 ≤ Si ≤ 104). The next Q lines contain 2 integers A (1 ≤ A ≤ N ) and B (-104 ≤ B ≤ 104), it means that the element SA of the initial sequence is replaced by B (SA = B).
For each test case, print Q + 1 lines. The first line should contain the last value and the winner of the initial sequence and the next Q lines the last value and the winner of the sequence after each replacement.
| Sample Input | Sample Output |
|
4 1 0 10 2 2 1 3 1 2 2 5 8 1 4 2 3 5 1 6 10 2 1 1 3 0 4 2 3 |
10 Sanches 4 Rusa 5 Sanches 7 Sanches -7 Rusa -10 Sanches 3 Sanches |