Find the Negative Index

This is an interactive problem where you are given an array of hidden integers (q_1, q_2, \dots, q_n) with (1 \leq |q_i| \leq V), and exactly one of them is negative. You are allowed to make at most (k) queries to determine the unique index (i) such that (q_i < 0). In each query, you propose a multiset (S) (possibly empty, with size at most (S_{\max}) and each element at most (n)). The query computes (M = \prod_{i\in S} q_i) (with the convention that (M = 1) if (S) is empty) and updates a global variable (Q \leftarrow Q + M). After each query, the judge returns the sign of (Q) as either '+' (if (Q>0)), '-' (if (Q<0)), or '0' (if (Q=0)).

For the offline version of the problem, the input provides the actual values of (q_1, q_2, \dots, q_n). Your task is to identify and output the index of the negative number. Note that the reported index is considered to be part of one of your queries.

inputFormat

The first line contains four integers: (n), (k), (S_{\max}), and (V). The second line contains (n) integers: (q_1, q_2, \dots, q_n). It is guaranteed that exactly one of the (q_i) is negative and for every (i), (1 \leq |q_i| \leq V).

outputFormat

Output a single integer representing the index (1-indexed) of the negative number (q_i).

sample

5 10 5 10
1 2 -3 4 5

3