CART（Classification and Regression Trees）分类树通过二元切分，递归地把样本划入不纯度更低的子集。分裂特征和切分点由基尼指数（Gini Index）算出，得到一棵二叉树；离散取值和连续取值都可以参与分裂。 本题用这棵 CART 分类树预测客户是否购房。根据训练集建出二叉决策树，每个节点按基尼指数选择特征和切分点，再对测试样本给出预测。

划分规则： 对每一个特征，把它所有可能的取值逐一当作切分点，当前节点的样本分成左子集和右子集：

• 左子集：特征值 = 切分点
• 右子集：特征值 ≠ 切分点

数据集说明

每条记录包含 4 个特征和 1 个标签，输入时全部写成整数枚举。

• 特征1： 年龄段（0：18-30岁；1：31-40岁；2：41-55岁；3：56岁及以上）
• 特征2： 婚姻状况（0：单身；1：恋爱；2：已婚）
• 特征3： 是否有房（0：无；1：有）
• 特征4： 是否有工作（0：无；1：有）
• 标签： 购房结果（0：否；1：是）

基尼指数计算公式

数据集里若有 $K$ 个类别，$p_k$ 表示第 $k$ 类样本所占比例：

加权基尼指数 特征 $A$ 以取值 $v$ 为切分点时，$D$ 被分成 $D_1(A=v)$ 与 $D_2(A \neq v)$：

预测规则

叶子节点输出该节点中人数最多的类别；若两个类别人数相同，输出编号较小的类别。

停止分裂条件

下面任一条件成立，节点即停止分裂：

1. 节点内全部样本的标签相同
2. 节点内的样本数小于 2
3. 不存在使基尼指数降低的切分点

平局处理规则

1. 按特征编号从小到大遍历（特征1 → 特征2 → 特征3 → 特征4）
2. 对当前特征，按取值从小到大遍历全部可能切分点
3. 计算各切分点的加权基尼指数，保留其中最小的切分
4. 若若干特征的加权基尼指数同为最小，取编号较小的特征
5. 若同一特征上若干取值的加权基尼指数同为最小，取较小取值作为切分点（左子集是该特征等于这个较小值的样本）

解答要求

• 时间限制：C/C++ 1000ms，其他语言 2000ms
• 内存限制：C/C++ 512MB，其他语言 1024MB

输入

第一行给出整数 $N$，表示训练集的客户人数（$4 \le N \le 20$）。 随后 $N$ 行，每行 5 个整数，依次是 4 个特征和 1 个标签，整数之间以空格分隔。 第 $N+2$ 行给出整数 $M$，表示待预测的样本人数（$1 \le M \le 10$）。 随后 $M$ 行，每行 4 个整数，依次是 4 个特征，整数之间以空格分隔。

输出

输出一行，共 $M$ 个整数，依次为 $M$ 个测试样本在所建 CART 树上的预测结果，整数之间以空格分隔。

样例1

输入：

8
0 0 0 0 0
1 1 0 1 0
2 2 0 0 0
3 1 0 1 0
0 1 1 0 1
1 2 1 1 1
2 0 1 0 1
3 2 1 1 1
4
2 1 0 1
0 2 1 0
3 0 0 0
1 1 1 1

输出：

0 1 0 1

解释：

1. 根节点共 8 名客户，标签 0（否）与标签 1（是）各 4 人，所以 $$Gini(D) = 1 - (4/8)^2 - (4/8)^2 = 0.5$$

2. 选取加权基尼指数最小的切分。特征3（是否有房）取切分点 0 时，左子集 4 人标签全为 0，右子集 4 人标签全为 1，加权基尼指数为 0。取切分点 1 只是左右对调，加权基尼指数同样为 0。二者并列，按平局规则保留较小取值 0，左子集为「是否有房 = 0」。 其余切分的加权基尼指数都大于 0。例如特征2（婚姻状况）取切分点 1 时，左子集 3 人里有 2 个 0、1 个 1，右子集 5 人里有 2 个 0、3 个 1，加权基尼指数为 $7/15$；特征4（是否有工作）取 0 或 1 时，两侧都是 2 个 0 与 2 个 1，加权基尼指数为 $1/2$。

3. 左右子集的标签都已相同，停止分裂。左叶子预测 0，右叶子预测 1。

4. 四个测试样本的特征3依次为 0、1、0、1。等于切分点的进入左子树，不等于的进入右子树，预测为 0 1 0 1。