You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 有一个 $n$ 个点 $m$ 条边的连通无向图，并且每条边还拥有一个正整数边权 $w_i$。

这天他在课上学到了最小生成树：无向图中选 $n-1$ 条边，使得所有 $n$ 个点被这些边连通，最小化这些边的权值和。但小 Y 觉得这样的定义没有很好的用上自己的边权——那些权值很大的边难道没有自己的价值吗？

于是小 Y 自定义了新的一类生成树：我们称一颗生成树是兼容 $x$ 的，当且仅当这棵生成树的所有边边权的最大公因数（GCD）是 $x$ 的倍数。小 Y 很开心，因为这样所有的边权都会有用武之地。

但小 Y 逐渐发现，自己的无向图有可能不存在兼容某个 $x$ 的生成树！于是小 Y 决定做一些修改，每次修改可以把一条边的权值改成任意正整数。但太多的修改又影响了图原本的特色，于是小 Y 想问你，为了让图中存在一棵兼容 $x$ 的生成树，最少要做多少次修改？

输入格式

从 mst.in 文件读入数据。

第一行三个整数 $n,m,k$，代表无向图的点数、边数、询问个数。

接下来 $m$ 行，每行三个正整数 $u_i, v_i, w_i$，代表图中的一条边。

接下来 $k$ 行，每行一个正整数 $x_i$ ，代表一个询问。

输出格式

输出到 mst.out 文件。

输出 $k$ 行，每行一个整数，代表第 $i$ 个询问的答案。注意询问得到的修改不会真实的在图上进行，换句话说，所有的询问都是基于初始的图。

样例 1

4 6 3
1 2 2
1 3 5
1 4 4
2 3 9
2 4 12
3 4 6
2
3
5

0
1
2

样例 2

点击链接 ex_mst2.in 和 ex_mst2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于每个测试点，$1\le n,m,k\le 10^5, 1\le u_i,v_i\le n, 1\le w_i,x_i\le 10^6$。