L. Coworking Spaces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In Next Digital we are 105 employees ( "nexters") and thanks to the fact that we are a 100% remote company we are spread all over the Spanish geography, or living as digital nomads abroad. The average age is 27 years old, and we like to see each other, have a cold beer and eat in an Asturian restaurant. Since we have more than a hundred nexters, it is more difficult to coincide, so we have planned to have multiple coworking spaces distributed in such a way that all nexters have at least one space less than an hour away by one or more means of transport, directly or passing through other cities. We don't want to waste time traveling, and since we are remote, it doesn't make sense to buy offices that will be empty most of the time.

We have asked for a budget from different coworking companies that offer us several flexible workspaces on demand. We have already discarded those companies that either did not have coffee included or were not in cities with any nexter living there. Now we have to rule out those that don't have workspaces close enough to each and every nexter. We don't want to hire multiple companies, we just want sufficiently distributed locations.

To reach a conclusion we have divided the work among several teams. The "Hormigas" team has made a list of the cities where there are one or more nexters, the "Vacas" team has obtained through an API the travel times between these cities, the '"Koalas" team has processed all the information previously generated and obtained the minimum distance between each city connected directly or through intermediate cities without nexters living. Everything was ready for "Mapaches" team to verify the list of coworking spaces, but the constant errors in one of their applications have left this task in their backlog.

Input

The entry begins with the numbers $$$N$$$, $$$E$$$, $$$X$$$ and $$$T$$$ on a single line. Being:

  • $$$N$$$ ($$$0 \lt N \le 200$$$) an integer indicating how many different cities the 105 nexters are in,
  • $$$E$$$ ($$$0 \le E \le 20,000$$$) the number of roads connecting two different cities,
  • $$$X$$$ ($$$0 \le X \le 50$$$) the number of coworking companies filtered by the "Hormigas" team, and
  • $$$T$$$ ($$$1 \lt T \le 200$$$) the maximum minutes a nexter is willing to travel in total; if it takes $$$T$$$ minutes or more on the way there or back, they will no longer want to go. There is no waiting time on transfers.
  • $$$1 \le c \lt T$$$
  • The following conditions are guaranteed:
    • The sum of N over all test cases will not exceed $$$200$$$.
    • The sum of E over all test cases will not exceed $$$20,000$$$.
    • The sum of X over all test cases will not exceed $$$50$$$.
Next $$$E$$$ rows appear, with three integers $$$u$$$, $$$v$$$, and $$$c$$$. The $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$) are indices representing each city with one or more nexters. The three numbers tells us that between the cities $$$u$$$ and $$$v$$$ it takes $$$c$$$ ($$$1 \le c \lt T$$$) minutes with the fastest direct mean of transport in both ways.

Finally, $$$X$$$ rows will appear, one for each coworking company. Each row will start with the number $$$o$$$ ($$$1 \le o \le N$$$) indicating in how many cities they offer us an office, followed by $$$o$$$ numbers where each number is the index of a city.

Output

We are asked to write one line for each test case, with the index list of companies separated by spaces in ascending order that have enough coworking spaces distributed so that nexters have at least one location closer than $$$T$$$ minutes. If none of the companies meet this constraint, "NO HAY EMPRESAS" will be written. The index of a company will be its position in the list of $$$X$$$ companies starting with $$$1$$$ and ending with $$$X$$$.

The program will terminate when it receives the input "$$$N=E=X=T=0$$$" without displaying anything in the output.

Example
Input
4 4 4 60
1 2 20
2 3 20
4 3 50
1 4 40
1 2
1 3
1 4
2 1 2
5 5 4 60
1 2 20
2 3 20
4 3 50
1 4 40
5 1 55
1 2
1 3
1 4
2 2 3
0 0 0 0
Output
2 4
NO HAY EMPRESAS