합 근원 판별

JAG 회원들이 정수 게임을 시작했다. 게임에는 $N + M + 1$명의 참가자가 있다. 공개 숫자 보유자 $N$명, 비밀 숫자 보유자 $M$명, 그리고 답변자 한 명, 즉 당신이다.

준비 단계에서 정수 $K$가 $N+M+1$명의 참가자 모두에게 주어진다. $N + M$명의 숫자 보유자는 다음 제약 아래에서 각자 정수를 하나씩 고른다.

• 각 보유자가 소유하는 정수는 양의 정수이다.
• 모든 정수의 합은 $K$이다.
• 비밀 숫자 보유자가 소유한 정수는 모두 공개 숫자 보유자가 소유한 어떤 정수보다도 작다.

선택이 끝나면 $N$명의 공개 숫자 보유자는 자신의 정수 $O_{1}, \dots, O_{N}$을 답변자에게 공개하지만, 비밀 숫자 보유자는 공개하지 않는다.

게임은 $Q$라운드로 진행된다. 각 라운드가 시작될 때 $M$명의 비밀 숫자 보유자는 위 제약 아래에서 자신의 숫자를 바꿀 수 있지만, 공개 숫자 보유자는 바꿀 수 없다. 그런 다음 $N + M$명의 숫자 보유자가 그중 일부를 임의로 선택하고, 선택된 보유자가 소유한 정수의 합 $X$를 계산하여 답변자에게 알려 준다. 각 라운드에서 답변자는 정보 $K$, $X$, $O_{1}, \dots, O_{N}$로부터 반드시 선택된 공개 숫자 보유자를 알아내려고 한다. 답변자는 답에 실제로 선택된 공개 숫자 보유자 하나당 점수를 얻는다. 반면, 답에 선택되지 않은 보유자가 하나라도 포함되면 그 라운드에서 얻은 점수를 모두 잃는다. 따라서 답변자인 당신은 반드시 선택되었다고 확신할 수 있는 공개 숫자 보유자만 답해야 한다.

이 문제에서 당신의 과제는 각 라운드마다 합에 반드시 필요하다고 확신할 수 있는 공개 숫자 보유자를 모두 판별하는 프로그램을 작성하는 것이다.

입력은 하나의 테스트 케이스로 이루어지며 형식은 다음과 같다.

$N$ $M$ $K$ $Q$ $O_{1}$ $\cdots$ $O_{N}$ $X_{1}$ $\cdots$ $X_{Q}$

첫 줄에 네 정수 $N$, $M$, $K$, $Q$가 주어진다. $N$과 $M$은 각각 공개 숫자 보유자와 비밀 숫자 보유자의 수이다 $(1 \le N, 0 \le M, N + M \le 40)$. $K$는 정수이다 $(1 \le K \le 200{,}000)$. $Q$는 게임의 라운드 수이다 $(1 \le Q \le 10{,}000)$.

둘째 줄에 $N$개의 정수 $O_{1}, \cdots, O_{N}$이 주어지며, $i$번째 공개 숫자 보유자는 $O_{i}$를 소유한다 $(1 \le O_{1} \le \dots \le O_{N} \le K)$.

셋째 줄에 $Q$개의 정수 $X_{1}, \cdots, X_{Q}$가 주어진다 $(0 \le X_{i} \le K)$. $X_{i}$는 $i$번째 라운드에서 선택된 보유자가 소유한 정수의 합이다.

$X_{i}$를 구성하는 방법이 적어도 하나 존재함이 보장된다. 다시 말해, 비밀 숫자 보유자가 소유한 정수를 나타내는 정수 수열 $S_{1}, \dots, S_{M}$이 다음 조건을 만족하는 경우가 적어도 하나 존재한다고 가정할 수 있다.

• $1 \le j \le M$에 대해 $0 < S_{j} < O_{1}$이다. $O_{1} = \min_{1 \le k \le N} O_{k}$이다.
• $\sum_{j=1}^{N} O_{j} + \sum_{k=1}^{M} S_{k} = K$이다.
• $\sum_{j \in U} O_{j} + \sum_{k \in V} S_{k} = X_{i}$를 만족하는 부분집합 $U \subseteq \{1, \dots, N\}$와 $V \subseteq \{1, \dots, M\}$가 적어도 하나 존재한다.

각 합 $X_{i}$에 대해, $X_{i}$를 구성하는 데 반드시 필요한 공개 숫자 보유자의 번호를 출력한다. 각 합에 대한 출력은 한 줄에 오름차순으로, 공백 하나로 구분하여 출력한다. $X_{i}$에 반드시 사용되는 정수가 있는 공개 숫자 보유자가 없으면 $-1$을 한 줄에 출력한다.