题目描述

渐渐地，Magic Land 上的人们对那座岛屿上的各种现象有了深入的了解。

为了分析一种奇特的称为梦想封印（Fantasy Seal）的特技，需要引入如下的概念：

每一位魔法的使用者都有一个「魔法脉络」，它决定了可以使用的魔法的种类。

一般地，一个「魔法脉络」可以看作一个无向图，有 $n$ 个结点及 $m$ 条边，将结点编号为 $1 \sim n$，其中有一个结点是特殊的，称为核心（Kernel），记作 $1$ 号结点。每一条边有一个固有（即生成之后再也不会发生变化的）权值， 是一个不超过 $u$ 的自然数。

每一次魔法驱动，可看作是由核心（Kernel）出发的一条有限长的道路（Walk），可以经过一条边多次，所驱动的魔法类型由以下方式给出：

将经过的每一条边的权值异或（xor）起来，得到 $s$。

如果 $s$ 是 $0$，则驱动失败，否则将驱动编号为 $s$ 的魔法（每一个正整数编号对应了唯一一个魔法）。

需要注意的是，如果经过了一条边多次，则每一次都要计入 $s$ 中。

这样，魔法脉络决定了可使用魔法的类型，当然，由于魔法与其编号之间的关系尚未得到很好的认知，此时人们仅仅关注可使用魔法的种类数。

梦想封印可以看作是对「魔法脉络」的破坏：

该特技作用的结果是，「魔法脉络」中的一些边逐次地消失。

我们记总共消失了 $q$ 条边，按顺序依次为 $dis_1, dis_2, \ldots , dis_q$。

给定了以上信息，你要计算的是梦想封印作用过程中的效果，这可以用 $q+1$ 个自然数来描述：

$ans_0$ 为初始时可以使用魔法的数量。

$ans_1$ 为 $dis_1$ 被破坏（即边被删去）后可以使用魔法的数量。

$ans_2$ 为 $dis_1$ 及 $dis_2$ 均被破坏后可使用魔法的数量。

$\cdots$

$ans_q$ 为 $dis_1, dis_2, \ldots , dis_q$ 全部被破坏后可以使用魔法的数量。

输入格式

第一行包含三个正整数 $n,m,q$。

接下来的 $m$ 行，每行包含 $3$ 个整数，$a_i$, $b_i$, $w_i$，表示一条权为 $w_i$ 的与结点 $a_i$, $b_i$ 关联的无向边，其中 $w_i$ 是不超过 $u$ 的自然数。

接下来 $q$ 行，每行一个整数：$dis_i$。

输出格式

一共包 $q+1$ 行，依次为 $ans_0, ans_1, \ldots , ans_q$。

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

5
2
0

样例说明 1

初始时可使用编号为 $1, 3, 4, 6, 7$ 的魔法。

在删去第 $1$ 条边（连结 $1,2$ 结点的边）后，可使用 $4$ 和 $6$ 号魔法。

第 $3$ 条边（连结第 $1,3$ 结点的边）也被删去后，核心（Kernel）即结点 $1$ 孤立，易知此时无法使用魔法。

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

15
11
5
2
2
1
1
0

数据规模和约定

所有数据保证该无向图不含重边、自环。

所有数据保证不会有一条边被删除多次，即对于不同 $i$ 和 $j$，有 $dis_i\neq disj$。

对于 $30\%$ 的数据中 $n,m,q \leq 50$，$u \leq 100$；

对于 $60\%$ 的数据中 $n,m \leq 300$，$q \leq 50$，$u \leq 10^9$；

对于 $80\%$ 的数据，$n \leq 300$，$m,q \leq 5000$，$u \leq 10^18$；

对于 $100\%$ 的数据，$n \leq 5000$，$m,q \leq 20000$，$u \leq 10^18$、

题目来源

Day3