소라게

많은 해변에서 볼 수 있는 소라게는 꽤 흥미로운 생물이다. 게의 친척이지만 배가 물러서, 몸을 보호하려면 고둥(바다 달팽이)의 빈 껍데기 속에서 살아야 한다. 그래서 우리가 실제로 보는 것은 해변을 종종거리며 돌아다니는 고둥 껍데기다. 가까이 다가가면 소라게는 껍데기 속으로 몸을 숨기고, 큰 집게발로 입구를 막아 그냥 껍데기처럼 보인다. 대부분의 동물처럼 소라게도 시간이 지나면 자라기 때문에, 언젠가는 더 큰 껍데기로 옮겨야 한다. 알맞은 껍데기를 찾지 못한 소라게는 대개 금방 잡아먹히며, 껍데기가 부족하면 서로 싸우기도 한다. 여기서는 소라게들이 껍데기보다 커지는 동안 어떤 소라게가 살아남는지를 알아본다.

문제를 단순화하기 위해 다음과 같이 가정한다.

• 각 소라게 $i$ 는 정수 크기 $c_i \ge 0$ 를 가진다. 소라게가 자라므로 $c_i$ 는 매 시간 단위마다 $1$ 씩 커지며, 시각 $t$ 에서의 크기는 $c_i + t$ 이다.
• 각 껍데기 $j$ 는 정수 크기 $s_j \ge 0$ 를 가지며, 이 값은 시간이 지나도 변하지 않는다.
• 주어진 상수 $D$ 에 대해, 시각 $t$ 에서 소라게 $i$ 의 크기가 $s_j - D \le c_i + t \le s_j$ 를 만족하면 소라게 $i$ 는 껍데기 $j$ 에 살 수 있다. (껍데기가 너무 크면 입구를 막을 수 없고, 너무 작으면 몸이 들어가지 않는다.)
• 시각 $0$ 에서 소라게 $i$ 는 껍데기 $i$ 에 산다. (크기가 맞도록 입력이 보장된다.)
• 소라게가 현재 껍데기에 비해 너무 커지는 순간, 즉 크기가 $s_j$ 를 넘어서는 순간, 그 껍데기를 떠나 자신이 들어갈 수 있는 비어 있는 껍데기 중 가장 큰 것으로 옮겨 간다. 그 순간 그런 껍데기가 하나도 없으면 새에게 잡아먹힌다.
• 여러 소라게가 정확히 같은 순간에 같은 껍데기로 옮겨 가려 하면 서로 싸우며, 그 껍데기를 원한 소라게 중 가장 큰 것만 살아남고 나머지는 잡아먹힌다.
• 어떤 소라게가 껍데기 $j$ 를 떠나는 순간에 다른 소라게가 껍데기를 찾고 있다면, 그 다른 소라게는 껍데기 $j$ 로 들어갈 수 있다.

크기가 같은 두 소라게는 없고, 크기가 같은 두 껍데기도 없으므로 위의 모든 선택은 유일하게 결정된다. 시각 $T$ 에 아직 살아 있는 소라게들을 구하라.

첫 줄에 데이터 집합의 수 $K$ 가 주어진다. 이어서 $K$ 개의 데이터 집합이 다음 형식으로 주어진다.

각 데이터 집합의 첫 줄에는 네 정수 $n$, $m$, $D$, $T$ 가 주어진다. $n$ 은 소라게의 수, $m$ 은 껍데기의 수이며 $1 \le n \le m \le 1000$ 을 만족한다. $D$ 는 위 설명의 상수이고, $T$ 는 관찰 기간의 길이다.

다음 $n$ 개의 줄에는 각각 소라게 $i$ 의 처음 크기 $c_i$ 가 하나씩 주어진다(모든 $c_i$ 는 서로 다르다). 그다음 $m$ 개의 줄에는 각각 껍데기 $j$ 의 크기 $s_j$ 가 하나씩 주어진다(모든 $s_j$ 는 서로 다르다). 입력은 $i = 1, \dots, n$ 에 대해 $s_i - D \le c_i \le s_i$ 를 보장하므로, 처음에 껍데기 $i$ 는 소라게 $i$ 에게 알맞다.

각 데이터 집합마다 먼저 Data Set x: 를 한 줄에 출력한다. 여기서 $x$ 는 데이터 집합의 번호이다($1$ 부터 시작). 그다음 시각 $T$ 에 아직 살아 있는 모든 소라게의 번호를 증가하는 순서로 한 줄에 하나씩 출력한다. 각 데이터 집합 뒤에는 빈 줄을 하나 출력한다.