Czech ACM Student Chapter

Czech Technical University in Prague

Charles University in Prague

Technical University of Ostrava

acm

ˇ a

Slovak University of Technology

Pavol Jozef Saf´rik University in Koˇice

s

cz

ˇ

University of Zilina

Masaryk University

Matej Bel University in Bansk´ Bystrica

a

University of West Bohemia

CTU Open Contest 2011

Invasion

invasion.c, invasion.C, invasion.java, invasion.p

Alien invasion began, and scary man-eating aliens are establishing their bases all over the coun-

try. You are only safe on the places that are sufficiently far away from all current alien bases.

You need to quickly write a program to help you determine where to move.

Input Specification

The input contains several instances, each of them consisting of several lines. The first line of

each instance contains integers N (1 ≤ N ≤ 10 000), M (0 ≤ M ≤ 100 000), A (0 ≤ A ≤ N ) and

K (1 ≤ K ≤ 100) separated by spaces, giving the number of towns in the country, the number

of roads between them, the number of bases that the aliens are going to build, and the minimum

safe distance from alien bases, respectively. The towns are assigned numbers 1, . . . , N .

The following M lines describe the roads; each of them contains integers T1, T2 (1 ≤ T1 < T2 ≤

N ) and D (1 ≤ D ≤ 100) separated by spaces, where D is the length of the road between towns

T1 and T2. There is at most one direct road between any two towns. All roads can be used in

both directions.

The following A lines describe the positions of alien bases; the i-th of them contains the number

Bi (1 ≤ Bi ≤ N ) of the town where the aliens build their i-th base.

Each instance is followed by one empty line. The empty line after the last instance is followed

by a line containing four zeros.

Output Specification

The output for each input instance consists of A lines. On i-th line, write the number of towns

that are safe after the aliens build their i-th base. The town is safe if its distance from any of

the towns B1, B2, . . . , Bi is at least K .

Print one empty line after each instance.

Sample Input

7

6

33

1

2

1

1

3

1

2

5

1

3

6

1

1

4

1

4

7

2

2

1

4

1011

1

0000

Output for Sample Input

2

1

0

0