Sum Source Detection

Time Limit : 2 sec, Memory Limit : 524288 KB

Sum Source Detection

JAG members began a game with integers. The game consists of $N + M + 1$ players: $N$ open number holders, $M$ secret number holders, and one answerer, you.

In the preparation, an integer $K$ is told to all $N + M + 1$ players. $N + M$ number holders choose their own integers per person under the following restrictions:

  • Each holder owns a positive integer.
  • The sum of all the integers equals $K$.
  • Every integer owned by secret number holders is strictly less than any integers owned by open number holders.

After the choices, $N$ open number holders show their integers $O_1, ..., O_N$ to the answerer while secret number holders do not.

The game has $Q$ rounds. At the beginning of each round, $M$ secret number holders can change their numbers under the above restrictions, while open number holders cannot. Then $N + M$ number holders select part of members among them arbitrary, calculate the sum $X$ of the integers owned by the selected members, and tell $X$ to the answerer. For each round, the answerer tries to identify the definitely selected open number holders from the information $K$, $X$, and $O_1, ..., O_N$: The answerer will get points per actually selected open number holder in the answer. On the other hand, if the answer contains at least one non-selected member, you lose your points got in the round. Thus, the answerer, you, must answer only the open number holders such that the holders are definitely selected.

Your task in this problem is to write a program to determine all the open number holders whose integers are necessary to the sum for each round in order to maximize your points.

Input

The input consists of a single test case formatted as follows.

$N$ $M$ $K$ $Q$
$O_1$ ... $O_N$
$X_1$ ... $X_Q$

The first line consists of four integers $N, M, K,$ and $Q$. $N$ and $M$ are the numbers of open number holders and secret number holders respectively ($1 \leq N, 0 \leq M, N + M \leq 40$). $K$ is an integer ($1 \leq K \leq 200,000$). $Q$ is the number of rounds of the game ($1 \leq Q \leq 10,000$).

The second line contains $N$ integers $O_1, ..., O_N$, as the $i$-th open number holder owns $O_i$ ($1 \leq O_1 \leq ... \leq O_N \leq K$).

The third line indicates $Q$ integers $X_1, ..., X_Q$ ($0 \leq X_i \leq K$). $X_i$ is the sum of the integers owned by the selected members in the $i$-th round.

It is guaranteed that there is at least one way to compose $X_i$. In other words, you can assume that there is at least one integer sequence $S_1, ..., S_M$, which represents integers owned by secret number holders, satisfying the followings:

  • $0 < S_j < O_1$ for $1 \leq j \leq M$. Note that $O_1 = min_{1\leq k \leq N}O_k$ holds.
  • $\sum_{j=1}^N O_j + \sum_{k=1}^M S_k = K$.
  • There is at least one pair of subsets $U \subseteq \{1,...,N\}$ and $V \subseteq \{1, ..., M\}$ such that $\sum_{j\in U} O_j + \sum_{k\in V}S_k = X_i$ holds.

Output

On each sum $X_i$, print the indices of the open number holders whose integers are required to make up $X_i$. The output for each sum has to be printed in one line, in ascending order, and separated by a single space. If there is no open number holder whose integer is certainly used for $X_i$, print $-1$ in one line.

Sample Input 1

2 2 23 2
7 10
9 10

Output for Sample Input 1

1
-1

The first sum 9 can be achieved only by the first open number holder's 7 plus 2 of a secret number holder. In this case, secret number holders have 2 and 4. The second open number holder's 10 is a candidate for the second sum 10. The first open holder's 7 plus 3 is also possible one, as secret number holders have two 3s.

Sample Input 2

1 1 100 3
51
49 51 100

Output for Sample Input 2

-1
1
1

The only secret number holder owns 49. The output for the first sum is $-1$ because the open number holder's 51 is not selected.

Sample Input 3

2 1 58152 4
575 57500
575 57577 77 0

Output for Sample Input 3

1
2
-1
-1

In this case, the only secret number holder definitely has 77. The output for the last sum 0 is -1 because no integer of open number holders is needed to form 0.

Sample Input 4

3 2 1500 1
99 300 1000
99

Output for Sample Input 4

1

The only way to compose 99 is to select the first open number holder only; secret number holders have two integers between 1 and 98, while the sum of them must be 101.

Sample Input 5

3 2 20 19
3 3 11
1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20

Output for Sample Input 5

-1
-1
-1
-1
-1
-1
1 2
1 2
1 2
3
3
3
3
3
3
3
1 2 3
1 2 3
1 2 3

The numbers owned by the two secret number holders are 1 and 2. At least one open number holder's 3 is required to compose 5 and 6 respectively, but it is impossible to determine the definitely selected open number holder(s). On the other hand, 7 needs the two open number holders who both own 3.


Source: ACM-ICPC Japan Alumni Group Summer Camp 2017 , Tokyo, Japan, 2017-09-24
http://acm-icpc.aitea.net/