시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 4 4 4 100.000%

문제

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}, \dots, 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}, \dots, 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.

입력

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

$N$ $M$ $K$ $Q$ $O_{1}$ $\cdots$ $O_{N}$ $X_{1}$ $\cdots$ $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 \le N, 0 \le M, N + M \le 40)$. $K$ is an integer $(1 \le K \le 200{,}000)$. $Q$ is the number of rounds of the game $(1 \le Q \le 10{,}000)$.

The second line contains $N$ integers $O_{1}, \cdots, O_{N}$, as the $i$-th open number holder owns $O_{i}$ ($1 \le O_{1} \le \dots \le O_{N} \le K$).

The third line indicates $Q$ integers $X_{1}, \cdots, X_{Q}$ $(0 \le X_{i} \le 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}, \dots, S_{M}$, which represents integers owned by secret number holders, satisfying the followings:

  • $0 < S_{j} < O_{1}$ for $1 \le j \le M$. Note that $O_{1} = \min_{1 \le k \le 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, \dots, N\}$ and $V \subseteq \{1, \dots, M\}$ such that $\sum_{j \in U} O_{j} + \sum_{k \in V} S_{k} = X_{i}$ holds.

출력

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.

예제 입력 1

2 2 23 2
7 10
9 10

예제 출력 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 $3$s.

예제 입력 2

1 1 100 3
51
49 51 100

예제 출력 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.

예제 입력 3

2 1 58152 4
575 57500
575 57577 77 0

예제 출력 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$.

예제 입력 4

3 2 1500 1
99 300 1000
99

예제 출력 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$.

예제 입력 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

예제 출력 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$.