给定一个包含 $N$ 个顶点（编号从 $1$ 到 $N$）和 $M$ 条边的无向图 $G$。

考虑一对顶点 $(a, b)$，其中 $a < b$。定义 $(a, b)$ 的关联度为至少有一个端点为 $a$ 或 $b$ 的边的总数。

你需要回答 $Q$ 个查询。每个查询给出一个整数 $k$，询问在 $G$ 中有多少对顶点 $(a, b)$ 满足 $a < b$ 且 $(a, b)$ 的关联度严格大于 $k$。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示顶点数和边数（$1 \le N, M \le 10^6$）。

接下来 $M$ 行，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$，表示第 $i$ 条边的两个端点（$1 \le x_i, y_i \le N$）。图中可能存在自环或重边。

下一行包含一个整数 $Q$，表示查询次数（$1 \le Q \le 10^6$）。

接下来 $Q$ 行，第 $i$ 行包含一个整数 $k_i$，表示第 $i$ 个查询（$1 \le k_i \le 10^6$）。

输出格式

对于每个查询，输出一行，包含一个整数，即该查询的答案。

样例

输入 1

4 5
1 2
2 4
1 3
2 3
2 1
2
2
3

输出 1

6
5