Luka 拥有一家地理数据公司，负责维护详细的城市地图并向相关方导出数据。通常，客户不需要完整的地图，而是希望得到一张仅包含主要街道的简化地图。

城市地图是一个无向图，包含 $n$ 个交叉路口（用 $1$ 到 $n$ 的整数表示）和 $m$ 条双向街道。每条街道都被分配了一个优先级，即一个非负整数。当客户请求地图时，会选择一个阈值优先级 $p$。原始地图随后会被复制并按照以下步骤转换为导出地图：

1. 删除所有优先级低于 $p$ 的街道。
2. 对于每个交叉路口 $i = 1, 2, \dots, n$（按此顺序处理）： (a) 如果交叉路口 $i$ 没有连接任何街道，则将其删除。 (b) 如果交叉路口 $i$ 恰好连接到两条不同的街道 $x$ 和 $y$，且这两条街道分别通向与 $i$ 不同的交叉路口 $a$ 和 $b$，则使用以下步骤对交叉路口 $i$ 进行收缩：

    i. 删除街道 $x$ 和 $y$。
    ii. 删除交叉路口 $i$。
    iii. 添加一条连接交叉路口 $a$ 和 $b$ 的新街道 $z$。

阈值优先级为 95 时的第二个样例示意图

最初，地图不包含环（连接交叉路口自身的街道）或平行边（同一对交叉路口之间有多条街道），但在收缩过程中可能会形成环和平行边。注意，在上述步骤 2.(b) 中，$x$ 和 $y$ 都不可能是环（因为 $a$ 和 $b$ 必须与 $i$ 不同），但新添加的街道 $z$ 可能是环（$a$ 和 $b$ 有可能是同一个路口）。

给定一张地图和一系列导出请求，对于每个请求，求出导出地图中交叉路口的数量和街道的数量。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 300\,000$) 和 $m$ ($1 \le m \le 300\,000$)，分别表示交叉路口的数量和街道的数量。接下来的 $m$ 行，每行包含三个整数 $a, b$ 和 $p$ ($1 \le a, b \le n, 0 \le p \le 300\,000$)，描述了一条优先级为 $p$、连接交叉路口 $a$ 和 $b$ 的街道。没有街道连接交叉路口自身。任意两个交叉路口之间最多只有一条街道。

下一行包含一个整数 $q$ ($1 \le q \le 300\,000$)，表示导出请求的数量。最后一行包含 $q$ 个整数。第 $k$ 个整数 $t_k$ ($0 \le t_k \le 300\,000$) 表示第 $k$ 次请求的阈值优先级。

输出格式

输出应包含 $q$ 行。第 $k$ 行应包含两个整数，分别表示第 $k$ 次请求对应的导出地图中交叉路口的数量和街道的数量。

样例

输入 1

6 7
1 2 20
2 3 80
2 5 100
3 5 50
3 4 100
5 6 90
4 6 100
4
25 75 85 95

输出 1

2 3
1 1
2 1
4 2

输入 2

10 14
2 7 150
1 2 100
2 3 150
3 1 200
1 4 60
4 5 20
2 5 100
5 6 90
6 7 120
7 5 130
6 8 50
8 9 200
9 10 200
10 7 200
5
300 50 95 100 110

输出 2

0 0
6 9
4 5
4 5
5 4