一款 5v5 竞技手游每逢版本更新都会上新皮肤。商店推荐位如果不加区分地把所有皮肤推给所有玩家，玩家划得累，购买转化率也上不去。项目组的做法是：先从历史数据里攒一批"看过页面、最终买没买"的记录，用决策树把购买意向学出来，再把新玩家逐条喂进这棵树做预测。

购买意向只用三个布尔特征描述，编号为 0、1、2：

训练样本的类别也只有两种：0 表示不购买（不推荐），1 表示购买（推荐）。

决策树的构建规则

熵

对只含两类的样本集 $S$，记类别 0、1 的样本占比为 $p_0$、$p_1$（$p_0+p_1=1$），熵定义为

其中 $p_x=0$ 的项按 $0\log_2 0=0$ 处理。

条件熵与信息增益

用特征 $A$ 把 $S$ 分成 $S_0$（取值为 0 的样本）与 $S_1$（取值为 1 的样本），分裂后的条件熵是两棵子树熵按样本量加权平均：

特征 $A$ 的信息增益，是分裂前后不确定性的减少量：

节点分裂

从根节点开始递归建树。在当前节点上，对尚未出现在从根到该节点的路径上的特征逐个计算信息增益，取增益最大的特征作为分裂特征；若几个特征的增益并列最大，取编号最小的那一个。然后按该特征的取值把节点内的样本分成两类：取值为 0 的进左子树，取值为 1 的进右子树。

某个特征一旦在某条路径上用过了，就不能在这条路径的下层节点上再用；但在另一条分支上它仍然可用。

终止条件

满足下列任意一条，当前节点就成为叶节点，不再分裂：

1. 节点内所有样本的类别相同；
2. 三个特征都已经在从根到该节点的路径上出现过；
3. 所有尚未使用的特征，其信息增益都不大于 0。

条件 1 的叶节点，类别就是节点内样本的类别；条件 2、3 的叶节点按多数表决定类：节点内类别 1 的样本多于类别 0 就取 1，少于就取 0，两者数量相等时取 0。

预测

对一条待预测样本，从根节点出发，读出当前节点分裂特征的取值：0 走左子树，1 走右子树，直到落在叶节点，输出该叶节点的类别。

输入格式

• 第一行：两个整数 $N$ 与 $M$，分别表示训练样本数与待预测样本数。
• 第 2 行到第 $N+1$ 行：每行 4 个整数，前三个依次是编号 0、1、2 的特征取值，第四个是该样本的类别（0 或 1）。
• 第 $N+2$ 行到第 $N+M+1$ 行：每行 3 个整数，依次是编号 0、1、2 的特征取值。

例如下面这段输入描述 4 条训练样本与 4 条待预测样本：

4 4
1 1 1 1
1 1 0 0
1 1 1 0
0 0 0 0
1 1 1
1 1 0
1 0 1
0 0 1

输出格式

共 $M$ 行，每行一个整数 0 或 1，按输入顺序给出每条待预测样本的类别。不要输出多余的空格或空行。

数据范围

• $1\le N\le 10^5$，$1\le M\le 10^5$
• 所有特征取值与类别均为 0 或 1
• 数据保证：在任何需要比较信息增益的节点上，并列最大的几个增益在数学上完全相等；非并列时，最大增益与次大增益之差不少于 $10^{-3}$。因此用双精度浮点按上述规则实现，不会因舍入误差选错特征。

解答要求

时间限制：C/C++ 1000ms，其他语言 2000ms

内存限制：C/C++ 512MB，其他语言 1024MB

样例1

输入

5 5
1 0 1 1
1 1 0 1
0 0 1 0
0 1 1 1
1 0 0 0
1 0 1
1 1 0
0 0 1
0 1 1
1 0 0

输出

1
1
0
1
0

解释：训练集共 5 条，类别 0 有 2 条、类别 1 有 3 条，$H(S)\approx 0.9710$。三个特征的信息增益分别约为 $0.0200$、$0.4200$、$0.0200$，最大的是特征 1，根节点按特征 1 分裂。特征 1 取 0 的一侧有 3 条样本，类别为 1、0、0，此时特征 0 与特征 2 的增益并列（都约为 $0.2516$），按规则取编号较小的特征 0；其中特征 0 取 1 的两条样本类别仍不同，再按特征 2 分开。特征 1 取 1 的一侧两条样本类别都是 1，直接成为叶节点。5 条待预测样本依次落到类别 1、1、0、1、0 的叶节点上。

样例2

输入

7 5
0 1 0 1
0 0 1 0
0 1 1 1
0 0 0 0
1 0 0 0
1 0 1 1
1 1 0 0
0 0 0
1 1 1
1 0 1
0 1 0
1 1 0

输出

0
0
1
1
0

解释：训练集共 7 条，类别 0 有 4 条、类别 1 有 3 条，$H(S)\approx 0.9852$。特征 0 的增益约为 $0.0202$，特征 1 与特征 2 的增益并列最大（都约为 $0.1281$），按规则取编号较小的特征 1 作为根节点。特征 1 取 1 的一侧有 3 条样本，类别为 1、1、0，特征 0 的增益约为 $0.9183$，大于特征 2 的 $0.2516$，按特征 0 分裂后两类完全分开。特征 1 取 0 的一侧有 4 条样本，类别为 0、0、0、1，特征 0 与特征 2 的增益并列（都约为 $0.3113$），取特征 0；其取值 1 的两条样本再按特征 2 分开。5 条待预测样本依次落到类别 0、0、1、1、0 的叶节点上。

提示