Problem1875--Collective Mindsets (hard)

1875: Collective Mindsets (hard)

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Heidi got one brain, thumbs up! But the evening isn't over yet and one more challenge awaits our dauntless agent: after dinner, at precisely midnight, the N attendees love to play a very risky game...

Every zombie gets a number ni (1≤ni≤N) written on his forehead. Although no zombie can see his own number, he can see the numbers written on the foreheads of all N-1 fellows. Note that not all numbers have to be unique (they can even all be the same). From this point on, no more communication between zombies is allowed. Observation is the only key to success. When the cuckoo clock strikes midnight, all attendees have to simultaneously guess the number on their own forehead. If at least one of them guesses his number correctly, all zombies survive and go home happily. On the other hand, if not a single attendee manages to guess his number correctly, all of them are doomed to die!

Zombies aren't very bright creatures though, and Heidi has to act fast if she does not want to jeopardize her life. She has one single option: by performing some quick surgery on the brain she managed to get from the chest, she has the ability to remotely reprogram the decision-making strategy of all attendees for their upcoming midnight game! Can you suggest a sound strategy to Heidi which, given the rules of the game, ensures that at least one attendee will guess his own number correctly, for any possible sequence of numbers on the foreheads?

Given a zombie's rank R and the N-1 numbers ni on the other attendees' foreheads, your program will have to return the number that the zombie of rank R shall guess. Those answers define your strategy, and we will check if it is flawless or not.

Input

The first line of input contains a single integer T (1≤T≤50000): the number of scenarios for which you have to make a guess.

The T scenarios follow, described on two lines each:

  • The first line holds two integers, N (2≤N≤6), the number of attendees, and R (1≤R≤N), the rank of the zombie who has to make the guess.
  • The second line lists N-1 integers: the numbers on the foreheads of all other attendees, listed in increasing order of the attendees' rank. (Every zombie knows the rank of every other zombie.)
Output

For every scenario, output a single integer: the number that the zombie of rank R shall guess, based on the numbers ni on his N-1 fellows' foreheads.

Examples
Input
4
2 1
1
2 2
1
2 1
2
2 2
2
Output
1
2
2
1
Input
2
5 2
2 2 2 2
6 4
3 2 6 1 2
Output
5
2
Note

For instance, if there were N=2 two attendees, a successful strategy could be:

  • The zombie of rank 1 always guesses the number he sees on the forehead of the zombie of rank 2.
  • The zombie of rank 2 always guesses the opposite of the number he sees on the forehead of the zombie of rank 1.

Source/Category

 
[Submit] [Status]