题目描述

阿瓦和阿卡一起来到了幻想游乐园。这座游乐园比较奇特，它的入口建在幻想山的悬崖上，它的出口建在图潇山的悬崖上，游乐园中的游乐设施之间只能够通过乘坐过山车来互相到达。

幻想游乐园一共有 $n$ 个游乐设施，我们将人口编号为 $1$ 出口编号为 $n$。一共建了 $m$ 条过山车道来连接两个游乐设施，第 $i$ 条过山车道连接编号为 $u_i$ 和 $v_i$ 的两个游乐设施，乘坐它花费的时间为 $w_i$。

阿瓦和阿卡觉得简单地坐过山车没什么意思，于是他们想出了一个有趣的问题: 能不能找到一种乘坐过山车的方式使得从起点到终点正好花费 $P$ 分钟呢?

你可以经过一个游乐设施多次，也可以乘坐一条过山车多次，每次都计算时间。

输入格式

第一行两个数 $n, m$ , 表示游乐设施个数和过山车道的条数。

接下来 $m$ 行, 第 $i$ 行三个数 $u_{i}, v_{i}, w_{i}$ 。

接下来一行一个数 $Q$ , 表示询问个数。

接下来 $Q$ 行, 每行一个询问 $P$ 。

输出格式

输出 $Q$ 行，对于每组询问，如果能够找到一种方式使得从起点到终点恰好花费 $P$ 分钟，则输出一行 $\verb!AWaDa!!$，否则输出一行 $\verb!AKTang!!$。

样例输入输出

3 5
3 1 6
3 3 1
3 3 10
3 1 10
1 2 3
3
6
7
3

AWaDa!
AWaDa!
AKTang!

说明/提示

对于 $20 \%$ 的数据， $n, m, Q \leq 10, P \leq 100$。

对于 $50 \%$ 的数据， $n, m \leq 100, Q \leq 10$ 。

对于 $100 \%$ 的数据, $n, m \leq 10^{4}, Q \leq 10^{5}, P \leq 10^{9}, 0<u_{i}, v_{i} \leq n, 0<w_{i} \leq 50 $ 。