Вы решили открыть новую школу. Вы уже нашли \(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\), все остальные группы останутся без изменений.
Вы не знаете, кто именно решил отказаться от обучения. Для каждого ученика определите, сможете ли Вы начать занятия в случае его отказа.
Обратите внимание, что не гарантируется, что до отказа ученика от обучения, было возможно начать занятия.
Выходные данные
Для каждого набора входных данных выведите одну строку длины \(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\) и так далее.
Примечание
В первом наборе входных данных есть одна группа учеников с средним возрастом \(\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\) соответственно. Тогда можно назначить первой группе первого преподавателя, а второй группе — третьего преподавателя.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 1
30
3
25 16 37
4 2
9 12 12 6
2
4 5
3
111 11 11
|
101
00100
|