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$$$ необходимо независимо определить, можно ли превратить заданные значения в $$$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 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]$$$.