CF1621E.New School

You have decided to open a new school. You have already found $n$ teachers and $m$ groups of students. The $i$-th group of students consists of $k_i \geq 2$ students. You know age of each teacher and each student. The ages of teachers are $a_1, a_2, \ldots, a_n$ and the ages of students of the $i$-th group are $b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$.

To start lessons you should assign the teacher to each group of students. Such assignment should satisfy the following requirements:

• To each group exactly one teacher assigned.
• To each teacher at most $1$ group of students assigned.
• The average of students' ages in each group doesn't exceed the age of the teacher assigned to this group.

The average of set $x_1, x_2, \ldots, x_k$ of $k$ integers is $\frac{x_1 + x_2 + \ldots + x_k}{k}$.

Recently you have heard that one of the students will refuse to study in your school. After this, the size of one group will decrease by $1$ while all other groups will remain unchanged.

You don't know who will refuse to study. For each student determine if you can start lessons in case of his refusal.

Note, that it is not guaranteed that it is possible to start lessons before any refusal.

你决定创办一所新学校。你已经找到了 $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$，其余所有小组保持不变。

你并不知道哪位学生会拒绝就读。对每一位学生，请判断：若该学生拒绝就读，你是否仍能正常开始授课。

注意：在任何学生拒绝就读之前，不一定总能保证可以开始授课。

The first line contains a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq m \leq n \leq 10^5$) — the number of teachers and the number of groups of students.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^5$) — the ages of teachers.

The next $2m$ lines contains descriptions of groups.

The first line of description of group contains a single integer $k_i$ ($2 \leq k_i \leq 10^5$) — the number of students in this group.

The second line of description of group contains $k_i$ integers $b_{i, 1}, b_{i, 2}, \ldots, b_{i, k_i}$ ($1 \leq b_{i, j} \leq 10^5$) — the ages of students of this group.

It is guaranteed that the total sum of $n$ over all test cases doesn't exceed $10^5$ and that the total sum of $k_1 + k_2 + \ldots + k_m$ over all test cases doesn't exceed $2 \cdot 10^5$

第一行包含一个整数 $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$。

For each test case output string of symbols $0$ and $1$ of length $k_1 + k_2 + \ldots + k_m$. The $i$-th symbol of this string should be equals $1$ if it is possible to start lessons in case of the $i$-th student refuse and it should be equals $0$ otherwise.

Students are numbered by integers from $1$ to $k_1 + k_2 + \ldots + k_m$ in the order they appear in the input. Thus, students of the $1$-st group are numbered by integers $1$, $2$, $\ldots$, $k_1$, students of the $2$-nd group are numbered by integers $k_1 + 1$, $k_1 + 2$, $\ldots$, $k_1 + k_2$ and so on.

对每个测试用例，输出一个由符号 $0$ 和 $1$ 组成的长度为 $k_1 + k_2 + \ldots + k_m$ 的字符串。该字符串的第 $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$，依此类推。

In the first test case there is one group of students with average age $\frac{25+16+37}{3}=26$ and one teacher with age $30$. There exists only one assignment that allows to start lessons.

If the student with age $16$ will refuse to study, the average age of students in this group will become $\frac{25+37}{2}=31$ so there won't be any assignment that allows to start lessons.

In the second test case it is impossible to start lessons initially. However, if the $3$-rd student with age $111$ will refuse to study, the average ages of groups will become $\frac{4 + 5}{2}=4.5$ and $\frac{11+11}{2} = 11$ correspondingly. Then it is possible to assing the first group to the first teacher and the second group to the third teacher.

在第一个测试用例中，有一组学生，其平均年龄为 $\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$。此时可将第一组学生分配给第一位教师，第二组学生分配给第三位教师。