题目描述

信息熵表示数据集的不确定性：

数据集 $S$ 中有 $c$ 个类别，$p_i$ 为第 $i$ 类的出现频率。

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

其中 $S_v$ 是 $A$ 取值为 $v$ 的样本子集。信息增益越大，越适合用该特征分裂。

请实现按信息增益建树的决策树分类器。每条训练样本形如

[feature_1, feature_2, ..., feature_m, label]

特征与类别标签都用整数表示。特征从左到右的下标为 $0,1,\ldots,m-1$。

建树从根结点开始，规则如下：

• 若当前子集的标签全部相同，或没有尚未使用的特征，则该结点为叶子。叶子类别是子集中出现次数最多的标签；次数相同取较小的标签。
• 否则只在尚未使用的特征中选择信息增益最大的特征进行划分。信息增益相同则选择下标较小的特征。同一条从根到叶的路径上，每个特征至多使用一次。
• 只对当前子集里实际出现过的取值建立子结点，并在对应子集上递归。

预测时从根结点向下。若测试样本在当前特征上的取值没有出现在该结点的训练子集中，则输出该结点的多数标签（次数相同取较小标签）。

下列表格只帮助理解划分过程。真正的输入全部是整数，不需要把单词换成数字。

得到的决策树为：

Outlook
├── Sunny → No
├── Overcast → Yes
└── Rain
    ├── Weak → Yes
    └── Strong → No

Outlook 划分后的信息增益最大，所以放在根结点。

输入描述

第一行一个整数 $m$，表示特征数。

第二行一个整数 $n$，表示训练样本数。

接下来 $n$ 行，每行 $m+1$ 个整数，以空格分隔，依次是 $m$ 个特征值和 $1$ 个类别标签。

接下来一行一个整数 $k$，表示测试样本数。

接下来 $k$ 行，每行 $m$ 个整数，以空格分隔，表示一条测试样本的特征值。

输出描述

输出 $k$ 行，每行一个整数，为对应测试样本的预测类别。

样例1

输入

2
5
0 0 0
0 1 0
1 0 1
1 1 0
2 0 1
4
0 1
1 0
1 1
2 0

输出

0
1
0
1

说明

五条训练样本的标签为 $0,0,1,0,1$。

按特征 $0$ 划分：取值 $0$ 的标签是 $\{0,0\}$，取值 $1$ 的标签是 $\{1,0\}$，取值 $2$ 的标签是 $\{1\}$。加权熵为 $\frac{2}{5}$。

按特征 $1$ 划分：取值 $0$ 的标签是 $\{0,1,1\}$，取值 $1$ 的标签是 $\{0,0\}$。前者熵约为 $0.918$，加权熵约为 $0.551$。

父集熵相同，特征 $0$ 的信息增益更大，根结点选用特征 $0$。

• 特征 $0$ 为 $0$ 时标签全是 $0$，叶子预测 $0$。样本 $(0,1)$ 因此输出 $0$。
• 特征 $0$ 为 $2$ 时标签是 $1$，叶子预测 $1$。样本 $(2,0)$ 输出 $1$。
• 特征 $0$ 为 $1$ 时还剩样本 $(1,0,1)$ 与 $(1,1,0)$，再用特征 $1$：取值 $0$ 预测 $1$，取值 $1$ 预测 $0$。样本 $(1,0)$ 输出 $1$，样本 $(1,1)$ 输出 $0$。

样例2

输入

2
5
0 0 1
1 1 0
1 1 0
1 2 0
1 2 0
2
0 9
1 1

输出

1
0

说明

特征 $0$ 与特征 $1$ 都能把样本划成纯子集，条件熵都是 $0$，信息增益相同。应选择下标较小的特征 $0$。

特征 $0$ 为 $0$ 的子集标签是 $1$，为 $1$ 的子集标签全是 $0$。样本 $(0,9)$ 预测 $1$，样本 $(1,1)$ 预测 $0$。

若改选特征 $1$，样本 $(0,9)$ 的取值 $9$ 在训练集中没有出现，只能输出根结点的多数类 $0$，与正确类别 $1$ 不同。

数据范围

$1 \le m \le 50$

$1 \le n \le 2000$

$k \ge 1$

特征值和类别标签均为整数。