First Echoes

Time limit: 3000 msMemory limit: 256 MB

An underground city has $N$ rooms and $M$ undirected corridors. Corridor $i$ connects rooms $U_i$ and $V_i$ and takes exactly $W_i$ units of time to traverse in either direction.

At time $0$ , for each $j$ with $1 \le j \le K$ , a messenger of color $j$ is placed in source room $S_j$ . The source rooms are pairwise distinct.

Initially, every room is unvisited. The following rules determine what happens:

When messengers first appear in an unvisited room at some time $T$ , only messenger colors appearing in that room at exactly time $T$ matter.
If those messengers have exactly one distinct color $c$ , the room is marked with color $c$ . Immediately at time $T$ , a copy of color $c$ starts traversing every corridor incident to that room.

Determine the final state of every room.

Input

The first line contains three integers $N$ , $M$ , and $K$ ( $1 \le K \le N \le 2 \times 10^5$ , ), the number of rooms, corridors, and source rooms.

Output

Print one line containing $N$ integers $A_1, A_2, \ldots, A_N$ , separated by single spaces.

Samples

Sample 1

Input

Output

1 0 2 -1 -1

Rooms $1$ and $3$ start with colors $1$ and $2$ . Room $2$ first sees both colors at time $1$ , so it freezes. Since no messenger starts from room , rooms and stay silent.

First Echoes

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2