题目内容

某云监控平台每天产生海量网络告警，运维团队训练了一个随机森林模型来识别根因告警。模型已离线训练完成，现在需要你实现该模型的推理与同源告警检索引擎。

随机森林由 $T$ 棵独立的决策树组成。每条告警包含 $M$ 个特征属性。对每棵树，从根节点开始独立评估：

• 如果遇到内部节点，会判断告警的第 $idx$ 个特征值是否 $\le$ 阈值 $val$：如果是，则走向左子节点；否则走向右子节点。
• 如果走到叶子节点，推理结束。定义该告警在这棵树上的落点为该叶子节点的节点编号。

一条告警的路径指纹定义为一个 $T$ 元组：它在第 $1$ 棵树到第 $T$ 棵树上的落点编号依次组成。指纹只由落点编号决定，与叶子上的标签无关——两条告警即使每个落点的标签都相同，只要落点编号不完全一致，就不算同源。

落点编号序列完全相同的告警构成一组同源告警。运维平台随后收到 $Q$ 条查询，每条查询给出一个告警编号 $j$，需要回答：与第 $j$ 条告警同源的告警（含第 $j$ 条自身）共有多少条，以及这些告警中编号最小的是多少（用于定位该组告警中最早出现的源头）。

注意：查询数量很大，请设计高效的算法在时限内完成所有查询。

解答要求

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

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

输入描述

• 第一行：4 个用空格分隔的整数 $T$ $M$ $N$ $Q$。$T$ 为树的数量，$M$ 为特征维度数，$N$ 为告警条数，$Q$ 为查询条数。
• 接下来是 $T$ 棵树的结构定义。对于每棵树：
  • 第一行：一个整数 $K$，表示该树共有 $K$ 个节点。节点编号为 $1$ 到 $K$，根节点编号固定为 $1$。
  • 接下来 $K$ 行，按节点编号 $1 \sim K$ 的顺序依次描述每个节点。每行以一个整数 $type$ 开头：
    • 若 $type=1$，代表内部节点，后接 4 个整数 $idx$ $val$ $left$ $right$：若告警的第 $idx$ 个特征值 $\le val$，跳至编号 $left$ 的节点，否则跳至编号 $right$ 的节点（特征索引 $idx$ 从 1 开始）。
    • 若 $type=0$，代表叶子节点，后接 1 个整数 $label$（$0$ 或 $1$），表示该节点的分类结果。
• 接下来 $N$ 行告警数据：每行 $M$ 个用空格分隔的整数，代表一条告警的 $M$ 个特征值。
• 最后 $Q$ 行查询：每行一个整数 $j$。

约束

• $1 \le T \le 8$
• $1 \le M \le 6$
• $1 \le N \le 2 \times 10^4$
• $1 \le Q \le 2 \times 10^5$
• $1 \le K \le 32$
• $type=1$ 时：$1 \le idx \le M$，$left, right \in [1,K]$
• $type=0$ 时：$label \in \{0, 1\}$
• $-10^9 \le val$ 且告警特征值 $\le 10^9$
• $1 \le j \le N$
• 题目保证树结构合法：不存在环，每个内部节点的两个子节点编号均有效

输出描述

输出共 $Q$ 行，按查询给出的顺序，每行输出两个用空格分隔的整数：与该查询同源的告警总数（含自身），以及这些告警中最小的编号。

样例1

输入

2 2 4 3
3
1 1 5 2 3
0 0
0 1
3
1 2 3 2 3
0 1
0 0
3 4
7 2
6 9
9 1
4
2
3

输出

2 2
2 2
1 3

说明

共 2 棵树、4 条告警。逐条推理：

• 告警 1 $[3,4]$：树 1 中 $3 \le 5$ 成立走左到叶子 2；树 2 中第 2 特征 $4 \le 3$ 不成立走右到叶子 3。指纹 $(2,3)$。
• 告警 2 $[7,2]$：树 1 中 $7 \le 5$ 不成立到叶子 3；树 2 中 $2 \le 3$ 成立到叶子 2。指纹 $(3,2)$。
• 告警 3 $[6,9]$：树 1 到叶子 3；树 2 到叶子 3。指纹 $(3,3)$。
• 告警 4 $[9,1]$：树 1 到叶子 3；树 2 到叶子 2。指纹 $(3,2)$。

查询 $j=4$：同源组 $\{2,4\}$，共 2 条，最小编号 2。查询 $j=2$ 与之同指纹，同为 2 2。查询 $j=3$：指纹 $(3,3)$ 只有告警 3 自身，输出 1 3。

样例2

输入

1 1 3 2
1
0 1
5
-7
5
3
1

输出

3 1
3 1

说明

单棵树且 $K=1$：根节点即为叶子，任何告警的落点都是节点 1，指纹恒为 $(1)$。三条告警全部同源，共 3 条，最小编号 1。两次查询都输出 3 1。