题目描述

YJC最近写了一篇关于游戏的论文。CJY看他那么喜欢游戏，决定出一道题考考他。CJY给出了一种两个人玩的游戏。 定义游戏规则如下：给一张$n$个点，$m$条边的有向无环图，每条边有颜色$c$，在图上放了$q$颗石子，每颗石子在一个点上。每次操作时选择一个有出边且点上有石子的点$x$，从点上取走一颗石子，然后选择一个颜色集合$S$，对于每条满足颜色$e∈S$的出边$i$，在边$i$的终点上放上一颗石子。双方轮流操作，不能操作者负。CJY问YJC是先手获胜还是后手获胜。YJC很轻松地解决了这个问题。 CJY把数据规模放大了。YJC遇到了困难，于是他来向你求助。

输入

第$1$行包含两个整数$n$和$m$，表示图的点数和边数。 第$2$到$m+1$行每行包含三个整数$s$,$t$和$c$，表示一条边的起点、终点和颜色。 接下来一行包含一个整数$q$，表示石子数量。 接下来一行包含$q$个整数，表示每颗石子所在的点。

输出

输出一个整数，如果先手必胜则输出$1$，否则输出$0$。

输入样例

2 1
2 1 1
1
2

输出样例

1

提示

【数据规模与约定】 实际测试时使用捆绑测试，一个测试点包含多个分测试点。 对于20%的数据，$n≤5,m≤10,q≤20$。 对于30%的数据，$n≤20,m≤100, q≤100$。 对于100%的数据，$n≤200,m≤5000,q≤10000,c≤5000$。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共8个测试点，非原站或官方原始数据。总分100分。