题目背景

葡萄藤上开不出百合花。

题目描述

你落在一个巨大的葡萄架上，上面一共有 $2^k$ 朵百合花和 $m$ 条葡萄藤。其中，百合花编号为 $0$ 到 $2^k-1$ 的整数，第 $i$ 条葡萄藤连接了编号为 $x_i, y_i$ 的百合花。

你可以花费 $c_i$ 的时间通过第 $i$ 条葡萄藤，也就是从 $x_i$ 走到 $y_i$，或者反过来；
还可以花费 $a_t$ 的时间从 $x$ 闪现到 $y$，其中 $x, y$ 是任意两朵百合花，$t$ 是它们在二进制表示下不同的比特数。
例如，$3$ 的二进制表示是 $\mathtt{011}$，$5$ 的二进制表示是 $\mathtt{101}$，它们有两位不同，因此从 $3$ 闪现到 $5$ 花费的时间是 $a_2$。

假设你恰好落在编号为 $s$ 的百合花上，求从 $s$ 出发到每一朵百合花所需要的最短时间。

输入格式

第一行包含三个正整数 $k, m, s$，其含义如题目描述。

第二行包含 $k$ 个非负整数 $a_1, a_2, \dots, a_k$，其含义如题目描述。

第 $3$ 至第 $(m+2)$ 行每行三个非负整数 $x_i, y_i, c_i$（$1 \leq i \leq m$），其含义如题目描述。

输出格式

输出一行 $2^k$ 个数 $D_0, D_1, \dots, D_{2^k-1}$，空格隔开，其中 $D_i$ 表示从 $s$ 到 $i$ 的最短时间。

样例

输入：

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

输出：

3 14 0 17 9 11 17 8

数据范围与提示

保证：

• $k \leq 17$
• $m \leq 2\times 10^5$
• $0 \leq s, x_i, y_i \leq 2^k-1$
• $0 \leq a_i, c_i \leq 2^{30}-1$