F. Coin Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. Your program will interact with the judge using standard input and output.

You are given an array $$$a$$$ of $$$n$$$ positive integers and an integer $$$k$$$, where $$$2k \leq n$$$. You have an initial score equal to $$$0$$$.

You will be asked $$$k$$$ queries. For each query, you will be given an integer $$$x \in \{1, 2\}$$$. You must choose an index $$$i$$$ ($$$1 \leq i \leq n$$$) such that$$$^\dagger$$$:

  • $$$i$$$ is divisible by $$$x$$$;
  • The index $$$i$$$ has not been chosen in any previous query;

Whenever you choose some index $$$i$$$ in some query, the value of $$$a_i$$$ is added to the score.

Your task is to maximize the score after completing all $$$k$$$ queries.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le 2k \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Interaction

The interaction proceeds as follows for $$$k$$$ times:

  • The judge will output a single integer $$$x \in \{1, 2\}$$$.
  • You must respond with a single integer $$$i$$$ ($$$1 \leq i \leq n$$$) that satisfies the conditions above$$$^\dagger$$$.
  • The judge will output "1" if $$$i$$$ is divisible by $$$x$$$ and it has not been chosen before in any previous query, and "0" otherwise.

If your program makes an invalid response, then the judge's response will be "0". After receiving such a response, your program should immediately terminate to receive the verdict Wrong Answer. Otherwise, it may receive any other verdict.

After responding to a query, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • sys.stdout.flush() in Python;
  • std::io::stdout().flush() in Rust;
  • see the documentation for other languages.
Example
Input
6 3
5 1 3 4 2 6
1
1
1
1
2
1
Output
1
6
4
Note

Sample explanation:

The size of the array is 6 and there are 3 queries. The first 2 lines describe the array and the number of queries.

In the first query, we must choose an index divisible by $$$1$$$, we choose the index $$$1$$$ and since it's divisible by $$$1$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid.

In the second query, we must choose an index divisible by $$$1$$$, we choose the index $$$6$$$ and since it's divisible by $$$1$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid. Note that if we chose $$$1$$$ instead the judge will print $$$0$$$ (since it has been chosen before).

In the third query, we must choose an index divisible by $$$2$$$, we choose the index $$$4$$$ and since it's divisible by $$$2$$$ and has not been chosen before, the judge will print $$$1$$$ to confirm that the chosen index is valid. Note that if we chose $$$6$$$ instead the judge will print $$$0$$$ (since it has been chosen before), and if we chose $$$3$$$ the judge will also print $$$0$$$ (since it's not divisible by $$$2$$$).

Note that over all combinations of: two indices divisible by 1 and one index divisible by 2, the maximum possible result is 15 (which is equal to the result in the example) and all chosen indices are distinct and satisfy the divisibility condition, so the result is considered correct.