PROGRAMMING:One day subway Tour
Mori likes to take the subway. This holiday, he finally came to the legendary city of Subway - Mordor, planning to have a good subway addiction!
The pricing rule of mordu Metro is: the starting price is 2 yuan, and the shortest distance between the departure station and the arrival station (that is * * charging distance * *) is increased by 1 yuan per km.
For example, if * * k * * = 10 and Dongan Temple Station is 40km away from modu Green Bridge station, the fare is 2 + 4 = 6 yuan.
In order to get the most satisfaction, Sensen decided to take the subway in the following way: get on the train at a certain station (it might be better to set it as subway station * * a * *), then for all the arrival stations with the same fare, Sensen will only leave the station at the farthest charging distance or the terminal station of the line, and then take a certified photo outside the station with Sensen Meitu app, and then go to the next station in the same way.
Sitting, Sensen suddenly became curious: in the case of a given departure station (Sensen will also take a picture at the time of departure), which site certification photos can he leave in his whole journey?
Subway is a form of railway transportation, which refers to the urban rail transit system mainly running underground. Generally speaking, the subway is composed of several stations, and there are many different lines running in two directions. It can be compared with the bus. When two or more lines pass through the same station, they can * * transfer * * and change their own lines. For example, if both modu line 1 and line 2 pass through the people's Square Station, when you take Line 1 to the people's Square, you can transfer to line 2 to each station of line 2. There is no need to get out of the station for transfer (and there is no certification photo), so there is no restriction on the transfer when Sensen takes the subway.
###Input format:
The first line of input is three positive integers * * n * *, * * m * * and * * k * *, indicating that mordu Metro has * * n * * stations (1 & Leq** N** ≤ 200), * * m * * lines (1 & Leq** M** ≤ 1500), and the shortest distance exceeds * * k * * km (1 & Leq** K** ≤ 10 < sup > 6 < / sup >), plus 1 yuan.
Next, there are * * m * * lines, each of which consists of the following formats:
< site 1 > < space > < distance > < space > < site 2 > < space > < distance > < space > < site 3 >... < site X-1 > < space > < distance > < space > < site x >
The station is a number from 1 to * * n * *; The distance between two station numbers refers to the distance between two stations on the line. The distance between the two stations is a positive integer not greater than 10 < sup > 6 < / sup >. The stations on one line are different from each other.
**Note * *: there may be multiple directly connected lines between two stations, and the distance may not be equal.
Then there is a positive integer * * Q * * (1 & Leq** Q** ≤ 200), indicating that Sensen tried to start from * * Q * * sites.
Finally, there are * * Q * * lines, each line has a positive integer * * x < sub > I < / sub > * * *, which indicates that morimori tries to start from the site with the number of * * x < sub > I < / sub > *.
###Output format:
For each site that Sensen tries, output a line of integers to indicate the number of sites that can be reached. The site numbers are sorted from small to large.
###Input example:
```in
6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
four
two
three
four
five
```
###Output example:
```out
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6
```
answer：If there is no answer, please comment
The pricing rule of mordu Metro is: the starting price is 2 yuan, and the shortest distance between the departure station and the arrival station (that is * * charging distance * *) is increased by 1 yuan per km.
For example, if * * k * * = 10 and Dongan Temple Station is 40km away from modu Green Bridge station, the fare is 2 + 4 = 6 yuan.
In order to get the most satisfaction, Sensen decided to take the subway in the following way: get on the train at a certain station (it might be better to set it as subway station * * a * *), then for all the arrival stations with the same fare, Sensen will only leave the station at the farthest charging distance or the terminal station of the line, and then take a certified photo outside the station with Sensen Meitu app, and then go to the next station in the same way.
Sitting, Sensen suddenly became curious: in the case of a given departure station (Sensen will also take a picture at the time of departure), which site certification photos can he leave in his whole journey?
Subway is a form of railway transportation, which refers to the urban rail transit system mainly running underground. Generally speaking, the subway is composed of several stations, and there are many different lines running in two directions. It can be compared with the bus. When two or more lines pass through the same station, they can * * transfer * * and change their own lines. For example, if both modu line 1 and line 2 pass through the people's Square Station, when you take Line 1 to the people's Square, you can transfer to line 2 to each station of line 2. There is no need to get out of the station for transfer (and there is no certification photo), so there is no restriction on the transfer when Sensen takes the subway.
###Input format:
The first line of input is three positive integers * * n * *, * * m * * and * * k * *, indicating that mordu Metro has * * n * * stations (1 & Leq** N** ≤ 200), * * m * * lines (1 & Leq** M** ≤ 1500), and the shortest distance exceeds * * k * * km (1 & Leq** K** ≤ 10 < sup > 6 < / sup >), plus 1 yuan.
Next, there are * * m * * lines, each of which consists of the following formats:
< site 1 > < space > < distance > < space > < site 2 > < space > < distance > < space > < site 3 >... < site X-1 > < space > < distance > < space > < site x >
The station is a number from 1 to * * n * *; The distance between two station numbers refers to the distance between two stations on the line. The distance between the two stations is a positive integer not greater than 10 < sup > 6 < / sup >. The stations on one line are different from each other.
**Note * *: there may be multiple directly connected lines between two stations, and the distance may not be equal.
Then there is a positive integer * * Q * * (1 & Leq** Q** ≤ 200), indicating that Sensen tried to start from * * Q * * sites.
Finally, there are * * Q * * lines, each line has a positive integer * * x < sub > I < / sub > * * *, which indicates that morimori tries to start from the site with the number of * * x < sub > I < / sub > *.
###Output format:
For each site that Sensen tries, output a line of integers to indicate the number of sites that can be reached. The site numbers are sorted from small to large.
###Input example:
```in
6 2 6
1 6 2 4 3 1 4
5 6 2 6 6
four
two
three
four
five
```
###Output example:
```out
1 2 4 5 6
1 2 3 4 5 6
1 2 4 5 6
1 2 4 5 6
```
answer：If there is no answer, please comment