您决定开设一所新学校。您已经找到了 $$$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$$$ 组学生。
- 每组学生的平均年龄不超过分配到该组的老师的年龄。
$$$k$$$ 整数的集合 $$$x_1, x_2, \ldots, x_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$$$
输出
对于每个测试用例,输出符号 $$$0$$$ 和 $$$1$$$ 长度为 $$$k_1 + k_2 + \ldots + k_m$$$ 的字符串。如果在第 $$$i$$$ 个学生拒绝的情况下可以开始上课,则该字符串的第 $$$i$$$ 个符号应等于 $$$1$$$,否则应等于 $$$0$$$。
学生按输入中出现的顺序按从 $$$1$$$ 到 $$$k_1 + k_2 + \ldots + k_m$$$ 的整数进行编号。因此,$$$1$$$-st组的学生用整数$$$1$$$、$$$2$$$、$$$\ldots$$$、$$$k_1$$$编号,$$$2$$$-nd组的学生用整数$$$k_1 + 1$$$、$$$k_1 + 2$$$、$$$\ldots$$$、 $$$k_1 + k_2$$$ 等等。
示例
输入 #1
2 1 1 30 3 25 16 37 4 2 9 12 12 6 2 4 5 3 111 11 11
输出 #1
101 00100
注意
在第一个测试用例中,有一组平均年龄为 $$$\frac{25+16+37}{3}=26$$$ 的学生和一名平均年龄为 $$$30$$$ 的老师。仅存在一项允许开始课程的作业。
如果年龄为 $$$16$$$ 的学生拒绝学习,则该组学生的平均年龄将变为 $$$\frac{25+37}{2}=31$$$,因此不会有任何允许开始上课的作业。
在第二个测试用例中,最初无法开始课程。然而,如果年龄为 $$$111$$$ 的 $$$3$$$-rd 学生拒绝学习,则各组的平均年龄将相应变为 $$$\frac{4 + 5}{2}=4.5$$$ 和 $$$\frac{11+11}{2} = 11$$$。然后可以将第一组分配给第一位老师,将第二组分配给第三位老师。