You have landed on a giant grapevine with a total of $2^k$ lilies and $m$ grapevines. The lilies are numbered with integers from $0$ to $2^k - 1$, and the $i$-th grapevine connects the lilies numbered $x_i$ and $y_i$.

You can spend $c_i$ time to travel through the $i$-th grapevine, i.e., from $x_i$ to $y_i$ or vice versa. You can also spend $a_k$ time to "flash" from $x$ to $y$, where $x$ and $y$ are any two lilies, and $k$ is the number of differing bits in their binary representations. For example, the binary representation of $3$ is $011$ and the binary representation of $5$ is $101$; they differ in two bits, so the time taken to flash from $3$ to $5$ is $a_2$.

Assuming you start exactly at the lily numbered $s$, find the shortest time required to travel from $s$ to every other lily.

Input

The input is read from standard input.

The first line contains three positive integers $k, m, s$, with meanings as described above.

The second line contains $k$ non-negative integers $a_i$ ($1 \le i \le k$), with meanings as described above.

The $3$-rd to $(m + 2)$-th lines each contain three non-negative integers $x_i, y_i, c_i$ ($1 \le i \le m$), with meanings as described above.

It is guaranteed that $k \le 17$, $m \le 2 \times 10^5$, $0 \le s, x_i, y_i \le 2^k - 1$, and $0 \le a_i, c_i \le 2^{30} - 1$.

Output

Output to standard output.

Output a single line containing $2^k$ numbers $D_i$ ($0 \le i \le 2^k - 1$), separated by spaces, where $D_i$ represents the shortest time from $s$ to $i$.

Examples

Input 1

3 6 2
17 14 11
0 2 3
4 2 9
2 2 1
2 2 6
7 0 5
4 2 9

Output 1

3 14 0 17 9 11 17 8

Input 2

See 2.in in the problem directory.

Output 2

See 2.ans in the problem directory.

Note

Please pay attention to the constant factor impact caused by different implementation methods.