有 $$$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$$$,您必须独立确定是否可以将给定值转换为 $$$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 \ne 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$$$ 零和/或一的字符串。第 $$$i$$$ 个字符应该是 1 如果可以获得 $$$i$$$-不稳定序列,或者 0 否则。
示例
输入复制
4 52 1 103 2 51 4 81 2 63 1 173020 0 15 51020 0 15 53020 0 15 5
输出复制
0000 0000 0110
输入复制
3 51 2 1001 2 101 3 51 2 1003 2 5110000000000 0 0
输出复制
000
输入复制
3 42 3 51 2 03 1 41 3 41057 5 325 7 011 1 153 0 105 3 556 0 451 5 617 7 211 6 647 7 2
输出复制
000 000 000 001 000 001 001 000 000 000
注意
考虑第一个例子。如果初始变量值为 $$$[20, 0, 15, 5]$$$,则无论操作顺序如何,结果值都将为 $$$[6, 0, 5, 5]$$$。减少变量 $$$10$$$ 倍是不够的。然而,如果我们可以应用不超过 $$$30$$$ 的更改,我们可以将 $$$1$$$-st 变量减少 $$$2$$$,并将 $$$4$$$-th 变量减少 $$$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]$$$。