F. 变量与操作

时间限制：每个测试点 $5$ 秒
内存限制：$512$ 兆字节

有 $n$ 个变量，记第 $i$ 个变量的值为 $a_i$。

另有 $m$ 个操作，这些操作将会被应用于这些变量。第 $i$ 个操作由三个整数 $x_i, y_i, z_i$ 描述。当应用第 $i$ 个操作时，变量 $x_i$ 会被赋值为 $\min(a_{x_i},\ a_{y_i} + z_i)$。

每个操作恰好会被应用一次，但它们的顺序并不固定，可以以任意顺序应用。

如果一个初始变量值序列 $a_1, a_2, \dots, a_n$ 被称为稳定的，当且仅当无论按什么顺序应用操作，最终得到的变量值都相同。如果第 $i$ 个变量的最终取值依赖于操作顺序，则称初始变量值序列为 $i$-不稳定。

你需要处理 $q$ 个查询。在每个查询中，你会获得初始值 $a_1, a_2, \dots, a_n$ 和一个整数 $k$。在应用操作之前，你可以进行最多 $k$ 次操作，每次可以选择一个变量并将其值减少 $1$。对于每个变量 $i$，你需要独立地判断是否可以通过上述变换（最多 $k$ 次减 $1$）使得序列变为一个 $i$-不稳定的序列。

输入
第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 500$，$1 \le m \le 4 \cdot 10^5$）—— 变量个数和操作个数。
接下来 $m$ 行，第 $i$ 行包含三个整数 $x_i, y_i, z_i$（$1 \le x_i, y_i \le n$，$x_i \neq y_i$，$0 \le z_i \le 10^5$）—— 第 $i$ 个操作的描述。
下一行包含一个整数 $q$（$1 \le q \le 1000$）—— 查询个数。
每个查询包含两行：

• 第一行一个整数 $k$（$0 \le k \le 10^9$）—— 最多可以进行减 $1$ 操作的次数。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$）—— 变量的初始值。

输出
对于每个查询，输出一个长度为 $n$ 的字符串，由 $0$ 和 $1$ 组成。第 $i$ 个字符是 $1$ 表示有可能得到一个 $i$-不稳定的序列，否则为 $0$。

示例

输入

4 5
2 1 10
3 2 5
1 4 8
1 2 6
3 1 17
3
0
20 0 15 5
10
20 0 15 5
30
20 0 15 5

输出

0000
0000
0110

输入

3 5
1 2 100
1 2 10
1 3 5
1 2 100
3 2 5
1
1000000000
0 0 0

输出

000

输入

3 4
2 3 5
1 2 0
3 1 4
1 3 4
10
5
7 5 3
2
5 7 0
1
1 1 1
5
3 0 1
0
5 3 5
5
6 0 4
5
1 5 6
1
7 7 2
1
1 6 6
4
7 7 2

输出

000
000
000
001
000
001
001
000
000
000

注
考虑第一个示例。如果初始变量值为 $[20,0,15,5]$，无论以何种顺序应用操作，最终值都会是 $[6,0,5,5]$。进行 $10$ 次减少操作不够。然而，如果我们能进行最多 $30$ 次改变，就可以将第 $1$ 个变量减少 $2$，第 $4$ 个变量减少 $25$，得到初始值 $[18,0,15,-20]$，此时序列对于第 $2$ 个变量和第 $3$ 个变量是不稳定的：

• 若按给定顺序应用操作，得到 $[-12,0,5,-20]$；
• 若按顺序 $[3,2,4,1,5]$ 应用操作，得到 $[-12,-2,5,-20]$；
• 若按顺序 $[3,4,5,1,2]$ 应用操作，得到 $[-12,-2,3,-20]$。