Interactive Negative Index Finder

This is an interactive problem.

You are given a hidden array \(q_1, q_2, \dots, q_n\) of integers satisfying \(1 \leq |q_i| \leq V\) for each \(i\), and there is exactly one index \(i\) such that \(q_i < 0\). Initially, you have a variable \(Q = 0\). You are allowed to issue at most \(k\) queries. In each query, you may provide a multiset \(S\) (possibly with repeated elements) of positive integers, where \(0 \leq |S| \leq S_{\max}\) and each element of \(S\) is between \(1\) and \(n\) (inclusive). The judge will compute \[ M = \prod_{i \in S} q_i \] with the convention that if \(S\) is empty then \(M = 1\), and then update \(Q \leftarrow Q + M\). After each query, the judge returns the sign of the current \(Q\) as one of {+, -, or 0} (i.e. + if \(Q > 0\), - if \(Q < 0\), or 0 if \(Q = 0\)).

Your task is to determine the index \(i\) for which \(q_i < 0\) within at most \(k\) queries. Important: the index you eventually report must have appeared in at least one of your queries.

Note: It is guaranteed that for every test case the index where \(q_i < 0\) is chosen uniformly at random from \([1, n]\).

inputFormat

The input is given in the following format for offline simulation:

n k S_max V
q1 q2 ... qn

Here:

• \(n\) is the number of hidden integers.
• \(k\) is the maximum number of allowed queries.
• \(S_{\max}\) is the maximum size of the multiset you can query.
• \(V\) is the upper bound for \(|q_i|\).
• \(q_i\) are the hidden integers with \(1 \leq |q_i| \leq V\) and exactly one of them is negative.

For the purpose of this problem, the entire array \(q\) is provided in the input.

outputFormat

Output a single integer representing the index \(i\) (1-indexed) for which \(q_i < 0\). It is guaranteed that the correct \(i\) appears in at least one of your queries.

sample

5 1 5 10
3 -2 5 1 7

2