Problem L
Adding Up the Votes

Not super-parallel vote counting
Author: Santwybe, CC BY 3.0 license

That last point is of particular interest, because computer science researchers at KTH Royal Institute of Technology, the host of the SCC 2021-2022 finals, have been studying how to count votes as quickly as possible. Given a series of votes, it’s easy to determine if any of the candidates has won a majority of votes in linear time: you just count the votes one at a time and keep a tally for each candidate. Of course, centralized single-processor algorithms are so 2021. In these modern times, an algorithm is barely of interest unless it can be parallelized to more than a thousand processors.

Your task is to determine if there is a candidate that received a strict majority of the votes in an election that $N$ citizens participated in, and if so, who. At your disposal is a super-parallel processor that can perform the following operation almost instantly. Let, for each $i$ where $1 \le i \le N$, $c_ i$ be the candidate that the $i$’th citizen cast their vote for. You can provide a sequence of integers $a_1, a_2, \dots , a_ N$ ($1 \le a_ i \le N$) and the processor will tell you whether $c_ i = c_{a_ i}$ for each $1 \le i \le N$. Your score for the problem depends on how many times you use the processor (see the Scoring sections for the details).

Interactivity

This problem is interactive; you will communicate with the grader through reading from standard in and writing to standard out. First, the grader will write a single line containing the integer $T$ ($1 \le T \le 10\, 000$), the number of times your program should count votes.

At the start of each vote counting, the grader will write a single line containing the integer $N$ ($1 \le N \le 100\, 000$), the number of citizens that participated in the election.

Next, you may use the super-parallel processor a number of times. For each use, output a single line ? a_1 a_2 ... a_N where $a_1, \dots , a_ N$ are integers between $1$ and $N$. The grader will then output a line containing a string consisting of $N$ characters 0 or 1. The $i$’th of these is $1$ if $c_ i = c_{a_ i}$ and $0$ otherwise.

Finally, you must output a single line of the form ! X where $X$ is such that candidate $c_ X$ received strictly more than half of the votes, i.e. $c_ X = c_ i$ for strictly more than half of all $1 \le i \le N$. If no such $X$ exists, you should instead output ! -1.

After this, your program should continue with the next vote counting. If this was the $T$’th vote count, your program must instead immediately exit.

The sum of all $N$ over all test cases will not exceed $100\, 000$.

It is guaranteed that the votes for each test case are fixed ahead of time and do not change adaptively in response to your queries.

Scoring

Your solution will be tested on a set of test cases. If any test case is answered incorrectly, your solution will graded as incorrect. Otherwise, let $Q$ denote the maximum number of times your program used the super-parallel processor for any vote counting. Depending on $Q$ your solution will be awarded different number of points:

 2
 5

 ? 2 1 4 5 3

 11000

 ? 1 1 1 1 1

 11010

 ! 4

 4

 ? 2 3 4 1

 1010

 ! -1