题目描述

在幻想世界当中，每年都会举办一场盛大的棒棒糖大赛，规则是:每名参赛者在主办方给出了几百支棒棒糖中每找到两支一模一样的棒棒糖就计分，同时那两只棒棒糖被主办方回收。

这挑战着选手的眼力和手速，是一场极具观赏性的比赛。而今年，主办方决定规模再加倍，给每名选手的棒棒糖数量达到几十万根。但这样一个问题就来了，选手在短时间内并不能完成比赛。于是他们决定更改规则。

主办方保证下发给每一位选手的棒棒糖的个数一定为 $n$，且会进行 $m$ 次询问，对于每次询问会给定两个正整数 $l,r$，你需要迅速判断这个区间内是否有两只一模一样的棒棒糖，若有，则输出 AWaDa!，否则输出 AKTang!。

输入格式

第一行两个正整数 $n,m$，表示棒棒糖的支数及询问次数。

第二行 $n$ 个正整数，第 $i$ 个数表示第 $i$ 支棒棒糖的种类编号 $a_i$，

之后 $m$ 行每行 $2$ 个正整数，表示每组询问。

输出格式

对于每组询问，你需要输出一个字符串表示你的答案。

样例 #1

样例输入 #1

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

样例输出 #1

AWaDa!
AWaDa!
AKTang!

提示

【样例解释 #1】

在第一组询问中，$1 \sim 5$ 中有重复的棒棒糖编号 $2,3$，

在第二组询问中，$2 \sim 4$ 中有重复的棒棒糖编号 $2$，

在第三组询问中，$1 \sim 3$ 中没有重复的棒棒糖编号。

【数据范围】

对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$1 \le a_i \le 10^9$。

第一个点 $91$ 分，其余点 $1$ 分。

加强版：$1 \le n \le 2 \times 10^6$。