Вы решили открыть новую школу. Вы уже нашли $$$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}$$$.
Чтобы начать занятия, осталось лишь назначить каждой группе учеников преподавателя. При этом должны выполняться следующие условия:
Средним арифметическим множества $$$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$$$ и так далее.
21 130325 16 374 29 12 12 624 53111 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$$$ соответственно. Тогда можно назначить первой группе первого преподавателя, а второй группе — третьего преподавателя.
| Hello 2022 |
|---|
| Закончено |
