Book Selection for AK BalticOI

You are committed to AK BalticOI, and your approach is through learning. In a bookstore, you find N books arranged on a shelf and numbered 1 through N. The i-th book has a difficulty of x_i. You wish to select exactly K books to study, but you do not want the material to be overly simple or excessively difficult. Thus, you want to ensure that the sum of the difficulties of the selected books lies within the range \([A,2A]\).

Unfortunately, you do not know the precise value of each x_i beforehand, so you must browse the books to determine their difficulties. However, the bookstore owner is fastidious and does not allow you to browse more than S books (via the skim function) to discover their difficulty. Fortunately, the books are arranged in increasing order of difficulty (i.e. \(x_1 < x_2 < \cdots < x_N\)).

You are to implement an interactive solution by writing a function void solve(int N, int K, long long A, int S) which is invoked exactly once. You may call the following functions:

• long long skim(int i): Browse the i-th book to obtain its difficulty x_i.
• void answer(vector<int> v): Purchase the books you have selected, where v = { i1, i2, ..., iK } and the sum of the difficulties of these books (i.e. \(\sum_{j=1}^{K} x_{i_j}\)) must satisfy \(A \le \sum_{j=1}^{K} x_{i_j} \le 2A\).
• void impossible(): Indicate that it is impossible to select such a set of K books.

Once a valid solution is found, answer must be called exactly once. If no such combination exists, call impossible() exactly once. Exceeding S calls to skim or deviating from the prescribed protocol will result in a judgment of Not correct. Also, writing any extraneous output to standard output will result in a Security violation.

For local testing, the interactor provides two lines via standard input:

1. The first line contains four integers: N, K, A, and S.
2. The second line contains N integers: x₁, x₂, ..., x_N.

The interactor will then run your program and finally output one of several messages indicating whether your solution was accepted.

inputFormat

The first line of input contains four space-separated integers: N (the number of books), K (the number of books to select), A (the lower bound for the acceptable sum of difficulties), and S (the maximum number of books you are allowed to browse via skim).

The second line contains N space-separated integers, representing the difficulties of the books in strictly increasing order: x₁, x₂, ..., x_N.

outputFormat

This is an interactive problem. Instead of writing directly to standard output, you are required to call one of the provided functions:

• If a valid set of books is found, call answer(v) with the list v containing the indices of the selected books. The chosen indices must satisfy \(A \le \sum_{j=1}^{K} x_{i_j} \le 2A\).
• If no valid selection exists, call impossible().

Any extraneous output or deviation from the interactive protocol will result in an error.

sample

5 2 10 5
2 3 5 7 11

3 4