题目描述

某国家项目要修建 N 座供魔法师居住的高塔。所有高塔都建在一条直线上，坐标为非负整数 P_1, P_2, ..., P_N。

这片地区最多有 3 个魔法师派系：

• 白魔法师（White）
• 灰魔法师（Gray）
• 黑魔法师（Black）

同一派系的魔法师从事相同类型的活动：

• 白魔法师擅长治疗魔法；
• 灰魔法师擅长炼金；
• 黑魔法师擅长死灵术。

因此，同一派系的魔法师往往需要相同资源，例如草药、金属、爪子等。正因如此，让两个同派系魔法师住得太近并不是好主意。

更具体地说：

• 两座白魔法师高塔之间的距离至少要为 R_W；
• 两座灰魔法师高塔之间的距离至少要为 R_G；
• 两座黑魔法师高塔之间的距离至少要为 R_B。

注意，某些地区可能没有某些派系的魔法师。我们用 K 表示这片地区实际存在的派系数。已知：

• 白魔法师在任何地方都会存在；
• 只要有黑魔法师，就一定也有灰魔法师。

问题在于：项目在决定每座塔归哪个派系之前就已经批准建设了。你现在需要判断：是否存在一种给塔分配派系的方法（每座塔恰好分配给一个派系），使得同派系之间的最小距离要求全部满足。

由于塔的数量可能非常多，手工判断并不可行。请编写程序 towers.cpp，根据各塔坐标判断是否存在合法分配方案。你的程序需要在一次运行中处理多个子测试。

输入格式

第一行输入一个整数 T，表示子测试个数。

之后每个子测试的格式如下：

• 第一行输入 N 和 K；
• 第二行输入 K 个数：
  • R_W
  • R_G（当 K ≥ 2 时给出）
  • R_B（当 K ≥ 3 时给出）
• 最后一行输入塔的坐标 P_1, P_2, ..., P_N。

为了方便，坐标保证按升序给出，即：

输出格式

对于每个子测试，输出一行：

• 若存在合法分配，输出 1；
• 否则输出 0。

限制

• 4 ≤ T ≤ 1000
• 1 ≤ K ≤ 3
• K < N ≤ S/4 ≤ 5 × 10^5
• 1 ≤ R_W, R_G, R_B ≤ 10^8
• 0 ≤ P_i ≤ 10^8

其中 S 表示单个测试中所有 N 的总和。

子任务与评分

一个子任务的分数仅在通过该子任务中所有测试后才能获得。

样例

输入

2
7 2
8 5
1 2 4 9 11 14 15
7 3
8 5 10
1 2 4 9 11 14 15

输出

0
1

样例解释

两个子测试中的塔位置相同，但：

• 第一个子测试中 K = 2；
• 第二个子测试中 K = 3。

第一个子测试无解。第二个子测试的一个可行分配为：

B W G W B G W

其中：

• B 表示黑魔法师；
• W 表示白魔法师；
• G 表示灰魔法师。

注意： 样例中没有满足限制 T ≥ 4 与 N ≤ S/4。这只是在样例里如此，系统测试会满足全部限制。