The Perfect Alibi

Time limit1sMemory limit128 MB

Summary

Each witness gives a suspect, a place, and a time interval; conflicting pairs are discarded, and we list suspects with no surviving witness covering the crime time.

Level: Medium5 of 10
Topics: Implementation, Sorting, Intervals, Simulation
Solved: No attempts yet

Problem

One of the more important things for a criminal to have is an alibi: a confirmation that the person was seen in a different place at the time the crime happened. That rules the person out as a suspect.

An alibi usually takes the form of a witness saying “I saw him/her in place $X$ from time $Y$ to $Z$ .” If that time range includes the time of the crime, and the police have no reason to mistrust the witness, this proves the suspect could not have committed the crime.

The only reason we mistrust a witness is this: another witness claims the same person was in a different place during an overlapping time window. If two witnesses $A$ and $B$ claim to have seen the same suspect $X$ in different places during overlapping time intervals, then we treat the input as though $A$ and $B$ never existed and discard both completely. (Untrustworthy witnesses do not prove guilt either.)

Write a program that narrows down an initial set of suspects using the alibis given by witnesses, while discarding every untrustworthy witness.

Input

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

The first line of a data set contains four integers $s, w, p, t$ . Here $1 \le s \le 50$ is the number of suspects, $1 \le w \le 200$ is the number of witnesses, $1 \le p \le 50$ is the number of possible locations, and $0 \le t \le 1000$ is the time of the crime.

This is followed by $w$ lines, each describing one witness statement with four integers $S_i, P_i, b_i, f_i$ . Here $1 \le S_i \le s$ is the suspect the witness claims to have seen, $1 \le P_i \le p$ is the place where the witness claims to have been, and $[b_i, f_i]$ is the claimed time interval of the observation. All values are integers.

Output

For each data set, first output “Data Set x:” on a line by itself, where $x$ is its number. On the following lines, output the suspects who are still under suspicion (those without a valid alibi), one per line, in increasing order. If every suspect has an alibi, output “No suspect.” instead. Put one blank line between the outputs of consecutive data sets.

Examples1

Example 1

Input

Expected output

Data Set 1:
1
3

Data Set 2:
No suspect.