Hermit Crabs

On many beaches, you can see hermit crabs, which are quite interesting creatures. They are related to crabs, but have a soft belly, so they need to live inside empty shells from sea snails for protection. So what you see is a sea snail shell walking along the beach at brisk pace. When you approach it, the crab withdraws inside, and the shell looks just like a shell, except it has a big claw closing off the entrance. Like most animals, hermit crabs grow over time, which means that they have to move shells. If they don’t find a suitable shell, they usually get eaten pretty quickly. If shells are scarce, hermit crabs sometimes even fight for them with each other. Here, we will see which hermit crabs survive over time as they outgrow their shells.

To simplify things a little bit, we assume the following. Each hermit crab i has an integer size ci ≥ 0. Because the crab grows, ci increases by one every time unit. Each shell j also has an integer size sj ≥ 0, which of course does not change over time. A hermit crab i can live in shell j at time t if the hermit crab’s size at time t lies between sj − D and sj , for a given constant D. (If the shell is too large, then the crab cannot protect the entrance; if it is too small, it does not fit inside.) Initially, at time 0, each crab i lives in shell i. (We will make sure that the size fits.) The moment a hermit crab becomes too large for its current shell, it leaves the shell, and moves into the biggest currently unoccupied shell into which it can fit. If there is no such shell at that moment, it gets eaten by a bird. If multiple crabs are trying to move into the same shell at the exact same time, they fight, and only the largest crab interested in that shell survives. If another crab leaves a shell j exactly at the same time as crab i is looking for a shell, crab i can move into shell j. All inputs will be such that no two crabs will have exactly the same size, and no two shells will have exactly the same size.

The first line contains the number K of data sets. This is followed by K data sets, each of the following form:

The first line contains four integers n, m, D, T. n is the number of hermit crabs, and m the number of shells, and they will satisfy 1 ≤ n ≤ m ≤ 1000. D is the maximum time a crab can spend in a shell (see description above), and T is the length of the observation period.

This is followed by n lines, each containing one integer ci, the initial size of crab i (all ci will be different). Next are m lines, each containing one integer sj , the size of the jth shell (all sj will be different). We will make sure that si − D ≤ ci ≤ si for i = 1, . . . , n, i.e., shell i has the right size for crab i initially.

For each data set, first output “Data Set x:” on a line by itself, where x is its number. Then, output, one number per line, and in increasing order, the list of all crabs still alive at time t. Each data set should be followed by a blank line.