beecrowd | 1696

Brincando Com Operadores

Por Anderson Silva, ICMC - USP BR Brazil

Timelimit: 3

Rusa e Sanches são amigos na escola primária. Este mês eles estão aprendendo como somar e subtrair números inteiros. O professor de matemática deles deu um bom exercício para praticarem estes novos operadores. O exercício é um jogo (para aumentar o interesse dos alunos). É necessário que dois alunos joguem juntos, e como Rusa e Sanches estão sempre fazendo as tarefas juntos, dessa vez não será diferente. O professor deu a eles várias sequências e os movimentos que eles podem realizar são:

- Primeiro jogador: Gerar uma nova sequência com a soma do primeiro e segundo números, do terceiro e quarto, do quinto e sexto, etc.

- Segundo jogador: Gerar uma nova sequência com a subtração do primeiro e segundo números (nessa ordem), do terceiro e quarto, do quinto e sexto, etc.

Se o tamanho da sequência for ímpar, o último número não deve ser modificado. Os jogadores alternam jogadas. O jogo continua até que reste apenas um número, chamado último número. Se ele é ímpar, o primeiro jogador vence. Caso contrário, o segundo vence. Como você pode ver o jogo é previsível, eles não podem alterar o resultado final dado uma sequência inicial. Entretanto, o professor também pediu para eles calcularem o último número da sequência depois de uma substituição num elemento da sequência inicial. Haverá várias substituições, e para cada uma eles tem que jogar novamente. Estas substituições são cumulativas. Ambos precisam aprender a somar e subtrair. Então, no primeiro caso de teste, Rusa será o primeiro jogador e Sanches, o segundo. No segundo caso de teste, eles trocam de ordem, i.e., Sanches é o primeiro jogador e Rusa, o segundo. No terceiro eles mudam de novo, e assim por diante. O professor deu muitas sequências para Rusa e Sanches. Eles já estão chateados do exercício porque eles já aprenderam a lição. Eles precisam terminar todos jogos até o final da semana e eles estão pedindo a você para ajudar com isso.

Por exemplo, vamos assumir que a sequência inicial é (4, 2, 3, 5, 1, 6, 10, 2). Então, os movimentos são: (4, 2, 3, 5, 1, 6, 10, 2) → (6, 8, 7, 12) → (-2, -5) → (-7). O último número é -7, e o vencedor é Rusa, porque -7 é impar, e este é o primeiro caso de teste. Vejamos um segundo exemplo, vamos assumir que a sequência inicial é (4, 2, 3). Então, os movimentos são: (4, 2, 3) → (6, 3) → (3). O último número é 3, e o vencedor é Sanches, porque 3 é impar e este é o segundo caso de teste.

Entrada

A primeira linha conterá um número T (1 ≤ T ≤ 100), quantos casos de teste seguem. Para cada caso de teste, a primeira linha conterá um número N (1 ≤ N ≤ 104) e Q (0 ≤ Q ≤ 104), o número de inteiros na sequência inicial e o número de substituições, respectivamente. A próxima linha contém N inteiros da sequência S1, S2, …, SN (-104Si ≤ 104). As próxima Q linhas contém A (1 ≤ AN ) e B (-104B ≤ 104), que significa que o elemento SA da sequência inicial é substituído por B (SA = B).

Saída

Para cada caso de teste imprima Q + 1 linhas. Na primeira linha, imprima o último número do jogo e o vencedor da sequência inicial e nas próximas Q linhas, o útimo número e o vencedor depois de cada substituição.

Exemplo de Entrada Exemplo de Saída

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