题目描述

小 D 新入职了某国的交管部门，他的第一个任务是负责国家的一条南北主干道的车辆超速检测。这条主干道十分长，以至于可以认为它的长度是无穷的。为了考考小 D，上司首先需要他解决一个简化的场景。

这个周末，主干道上预计出现 $n$ 辆车，其中第 $i$ 辆车从主干道上距离最南端 $d_i$ 的位置驶入，以 $v_i$ 的初速度和 $a_i$ 的加速度做匀加速运动向北行驶。我们只考虑从南向北的车辆并且这些车不会减速，故 $v_i>0,a_i\geq 0$。

主干道上设置了 $m$ 个测速仪，其中第 $j$ 个测速仪位于主干道上距离最南端 $p_j$ 的位置。当某辆车经过某个测速仪时，若这辆车的瞬时速度超过了测速仪的限速 $l_j$，那么这辆车就会被判定为超速。注意当车辆驶入主干道时，如果在对应位置有一个测速仪，这个测速仪也会对这辆车进行测速。

上司想知道，这 $n$ 辆车中哪些车被判定为超速。

由于 $n$ 很大，上司允许小 D 使用编程解决这两个问题，于是小 D 找到了你。

如果你对于加速度并不熟悉，小 D 贴心地在本题的“提示”部分提供了有关加速度的公式。

输入格式

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含两个正整数，表示 $n,m$。

接下来 $n$ 行，每行包含三个整数，表示 $d_i,v_i,a_i$。

接下来一行包含 $m$ 个整数，第 $j$ 个整数表示 $p_j$。

最后一行包含 $m$ 个整数，第 $j$ 个整数表示 $l_j$。

输出格式

对于每组数据：输出一行包含 $n$ 个整数，第 $i$ 个数为 $0$ 表示第 $i$ 辆车没有超速，为 $1$ 代表该车超速。

样例

1
5 5
0 3 0
12 4 0
1 1 4
5 5 2
6 4 4
2 5 8 9 15
3 3 3 3 3

0 1 1 1 1

数据范围

对于所有测试数据，保证：

• $1\leq T\leq 6$。
• $1\leq n,m\leq 10^5,1\leq l_i\leq 10^6$。
• $0\leq d_i\leq 10^6,1\leq v_i\leq 10^3,0\leq a_i\leq 10^3$。
• $0\leq p_1\leq p_2\leq \cdots \leq p_m\leq 10^6$。

特殊性质 A：$a_i=0$。

特殊性质 B：$l_j$ 全部相同。

提示

与加速度有关的定义和公式如下：

• 匀加速运动是指物体在运动过程中，加速度保持不变的运动，即每单位时间内速度的变化量是恒定的。
• 当一辆车的初速度为 $v_0$、加速度 $a\neq 0$，做匀加速运动，则 $t$ 时刻后它的速度 $v_1 = v_0 + a \times t$，它的位移（即行驶路程）$s=v_0\times t+0.5\times a\times t^2$。
• 当一辆车的初速度为 $v_0$、加速度 $a \neq 0$，做匀加速运动，则当它的位移（即行驶路程）为 $s$ 时，这辆车的瞬时速度为 $\sqrt{v_0^2+2\times a\times s}$。
• 当一辆车的初速度为 $v_0$、加速度 $a \neq 0$，在它的位移（即行驶路程）为 $\frac{v_1^2-v_0^2}{2a}$ 时，这辆车的瞬时速度为 $v_1$。

如果你使用浮点数进行计算，需要注意潜在的精度问题。