E. Новая школа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы решили открыть новую школу. Вы уже нашли $$$n$$$ преподавателей и $$$m$$$ групп учеников. Группа учеников $$$i$$$ состоит из $$$k_i \geq 2$$$ учеников. Вы знаете возраста всех преподавателей и всех учеников. Возраста преподавателей равны $$$a_1, a_2, \ldots, a_n$$$, а возраста учеников в $$$i$$$-й группе равны $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$$$.

Чтобы начать занятия, осталось лишь назначить каждой группе учеников преподавателя. При этом должны выполняться следующие условия:

  • Каждой группе учеников назначен ровно один из преподавателей.
  • Каждому преподавателю назначено не более $$$1$$$ группы учеников.
  • Для каждой группы, cреднее арифметическое возрастов учеников группы не превосходит возраста назначенного этой группе преподавателя.

Средним арифметическим множества $$$x_1, x_2, \ldots, x_k$$$ из $$$k$$$ чисел является значение $$$\frac{x_1 + x_2 + \ldots + x_k}{k}$$$.

Недавно Вы узнали, что один из учеников решил отказаться от обучения в Вашей школе. После его отказа размер одной из групп учеников уменьшится на $$$1$$$, все остальные группы останутся без изменений.

Вы не знаете, кто именно решил отказаться от обучения. Для каждого ученика определите, сможете ли Вы начать занятия в случае его отказа.

Обратите внимание, что не гарантируется, что до отказа ученика от обучения, было возможно начать занятия.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следуют описания этих наборов.

В первой строке дано два числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \leq n \leq 10^5$$$) — количество преподавателей и количество групп учеников.

Во второй строке дано $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$) — возраста преподавателей.

В следующих $$$2m$$$ строках содержатся описания групп.

В первой строке описания группы дано одно число $$$k_i$$$ ($$$2 \leq k_i \leq 10^5$$$) — количество учеников в группе.

Во второй строке описания группы дано $$$k_i$$$ целых чисел $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$$$ ($$$1 \leq b_{i, j} \leq 10^5$$$) — возраста учеников в этой группе.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, и что сумма $$$k_1 + k_2 + \ldots + k_m$$$ всех наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку длины $$$k_1 + k_2 + \ldots + k_m$$$, состоящую из символов $$$0$$$ и $$$1$$$. $$$i$$$-й символ этой строки должен быть равен $$$1$$$, если в случае отказа $$$i$$$-го ученика можно будет начать занятия, и равен $$$0$$$ иначе.

Ученики пронумерованы целыми числами от $$$1$$$ до $$$k_1 + k_2 + \ldots + k_m$$$ в том порядке, в котором они встречаются во входных данных. Таким образом, ученики $$$1$$$-й группы имеют номера $$$1$$$, $$$2$$$, $$$\ldots$$$, $$$k_1$$$, ученики $$$2$$$-й группы имеют номера $$$k_1 + 1$$$, $$$k_1 + 2$$$, $$$\ldots$$$, $$$k_1 + k_2$$$ и так далее.

Пример
Входные данные
2
1 1
30
3
25 16 37
4 2
9 12 12 6
2
4 5
3
111 11 11
Выходные данные
101
00100
Примечание

В первом наборе входных данных есть одна группа учеников с средним возрастом $$$\frac{25+16+37}{3}=26$$$ и один преподаватель с возрастом $$$30$$$. Существует единственный способ назначить каждой группе учеников преподавателя и начать занятия.

Если ученик возраста $$$16$$$ откажется от обучения, среднее арифметическое возрастов в группе станет равно $$$\frac{25+37}{2}=31$$$, и не будет существовать способа назначить каждой группе учеников преподавателя.

Во втором наборе входных данных невозможно начать занятия изначально. Но если $$$3$$$-й ученик возраста $$$111$$$ откажется от обучения, средние возраста учеников в группах станут равны $$$\frac{4 + 5}{2}=4.5$$$ и $$$\frac{11+11}{2} = 11$$$ соответственно. Тогда можно назначить первой группе первого преподавателя, а второй группе — третьего преподавателя.