Problem Statement

There are $N$ people and $K$ nations, labeled as Person $1$, Person $2$, $\ldots$, Person $N$ and Nation $1$, Nation $2$, $\ldots$, Nation $K$, respectively. Each person belongs to exactly one nation: Person $i$ belongs to Nation $A_i$. Additionally, there are $L$ popular people among them: Person $B_1$, Person $B_2$, $\ldots$, Person $B_L$ are popular. Initially, no two of the $N$ people are friends.

For $M$ pairs of people, Takahashi, a God, can make them friends by paying a certain cost: for each $1\leq i\leq M$, he can pay the cost of $C_i$ to make Person $U_i$ and Person $V_i$ friends.

Now, for each $1\leq i\leq N$, solve the following problem.

Can Takahashi make Person $i$ an indirect friend of a popular person belonging to a nation different from that of Person $i$? If he can do so, find the minimum total cost needed. Here, Person $s$ is said to be an indirect friend of Person $t$ when there exists a non-negative integer $n$ and a sequence of people $(u_0, u_1, \ldots, u_n)$ such that $u_0=s$, $u_n=t$, and Person $u_i$ and Person $u_{i+1}$ are friends for each $0\leq i < n$.

Constraints

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq K \leq 10^5$
• $1 \leq L \leq N$
• $1 \leq A_i \leq K$
• $1 \leq B_1<B_2<\cdots<B_L\leq N$
• $1\leq C_i\leq 10^9$
• $1\leq U_i<V_i\leq N$
• $(U_i, V_i)\neq (U_j,V_j)$ if $i \neq j$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K L
A_1 A_2 \cdots A_N
B_1 B_2 \cdots B_L
U_1 V_1 C_1
U_2 V_2 C_2
\vdots
U_M V_M C_M

Output

Let $X_i$ defined as follows: $X_i$ is $-1$ if it is impossible to make Person $i$ an indirect friend of a popular person belonging to a nation different from that of Person $i$; otherwise, $X_i$ is the minimum total cost needed to do so. Print $X_1, X_2, \ldots, X_N$ in one line, with spaces in between.