Keegan is running a printer shop! There are $N$ printers in this shop, connected by $M$ cables. Unfortunately, some of the printers have begun catching fire. When a printer catches fire, it will spread the fire to all the printers connected to it. It takes exactly $d_i$ seconds for the fire to transmit from one printer to another through the cable connecting them. After $t$ seconds, Keegan notices the fire and activates his sprinkler system, which will extinguish fires on exactly $K$ printers $p_1,p_2,\dots p_K$, along with any fires currently spreading on any cables. If there are still fires after the sprinkler system has been activated, his shop will be damaged! In order to maintain the safety of his shop, Keegan asks you for help determining which printers can catch fire without resulting in damage to the shop.

Constraints

$1\le K\le N\le 2\times {10}^5$

$0\le M\le min(\frac{N(N-1)}{2},2\times {10}^5)$

$1\le t\le {10}^{18}$

$1\le u_i,v_i,p_i\le N$

$1\le d_i\le {10}^9$

Subtask 1 [15%]

$1\le N\le 800$

$0\le M\le 800$

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line will contain four integers, $N$, $M$, $K$, and $t$.

The second line will contain $K$ integers $p_1,p_2,\dots p_K$.

The next $M$ lines will each contain three integers, $u_i$, $v_i$, and $d_i$, denoting that there exists a bidirectional cable from printer $u_i$ to printer $v_i$ taking $d_i$ seconds for the fire to travel through.

Output Specification

Output a single binary string of length $N$, where the $i$-th character is a 1 if the $i$-th printer can catch on fire without resulting in damage to the shop, and a 0 otherwise.

Sample Input 1

4 4 2 2
2 4
1 2 1
2 3 2
2 4 3
3 4 1

Sample Output 1

0000

Explanation for Sample 1

If the fire starts at printer $1$, it will remain on fire as it is not extinguished at the end.

If the fire starts at printer $2$, it will spread to printer $1$, which is not extinguished.

If the fire starts at printer $3$, it will remain on fire as it is not extinguished at the end.

If the fire starts at printer $4$, it will spread to printer $3$, which is not extinguished.

Sample Input 2

5 7 2 5
1 3
3 4 5
5 1 7
5 4 2
5 2 1
1 3 10
5 3 1
4 2 2

Sample Output 2

10000

Sample Input 3

5 7 4 5
4 2 1 3
3 4 6
3 1 5
4 5 8
1 5 4
1 2 1
3 5 7
2 4 3

Sample Output 3

00110