J. Aythsr 的彩票人生
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

$$$Aythsr$$$ 是一名外卖小哥，他收到很多的订单需要送。 他所在城市的地图可以看成一幅无向连通图，其中有$$$n$$$个节点，编号为$$$1 \sim n$$$，有$$$m$$$条边。 每一笔订单由两个参数 $$$(s_i,t_i)$$$ 组成，表示他需要从 $$$s_i$$$ 点出发，将外卖送到 $$$t_i$$$ 点。$$$Aythsr$$$ 可以随意规定他的路线，但是为了追求效率，在每一笔订单中，每条边只能经过一遍。

同时 $$$Aythsr$$$ 是一个相信幸运的人，城市的某些路上装配了一些 "大乐透" 彩票机，$$$Aythsr$$$ 想知道在他的每笔订单中，是否有机会买彩票。

注意，每笔订单是独立的，每笔订单的过程只计算从 $$$s_i$$$ 出发到 $$$t_i$$$ 结束，你无须关注从 $$$t_i$$$ 到 $$$s_{i+1}$$$ 的过程。

Input

第一行输出一个整数 $$$T$$$，表示有 $$$T$$$ 组数据。

每组数据由以下部分组成：

  1. 第一行输入三个整数 $$$n,m,q$$$ ，$$$n$$$ 代表城市节点的数量，$$$m$$$ 代表边的数量，$$$q$$$ 代表订单的数量。
  2. 接下来 $$$m$$$ 行描述道路，三个整数 $$$v_i, u_i, f_i$$$，表示存在一条 $$$(v_i, u_i)$$$ 的道路，$$$f_i$$$ 为 $$$1$$$ 时表示这条路上装配了"大乐透"彩票机，$$$f_i$$$ 为 $$$0$$$ 时表示这条路上未装配"大乐透" 彩票机。
  3. 接下来 $$$q$$$ 行描述订单，两个整数 $$$(s_i, t_i)$$$ ，表示他需要从 $$$s_i$$$ 点出发，将外卖送到 $$$t_i$$$ 点。

数据规模约定：

$$$n,q\le10^5, m \le 2 \times10^5, \sum n \le 10^6,\sum m \le 2 \times 10^6,\sum q \le 10^6, f_i \in \lbrace 0,1\rbrace$$$

$$$v_i,u_i,s_i,t_i \in [1, n]$$$

图中可以存在重边，自环

Output

对于每个询问，输出一个字符串：

  1. 如果可以买彩票，输出：'wow!golden legendary!'
  2. 如果不可以，输出：'awsl!'

注意输出的大小写！只有小写字母和叹号、空格

Example
Input
1
7 7 4
1 2 1
1 3 0
3 2 0
3 7 0
3 4 0
4 5 0
4 6 0
1 3
5 6
4 7
6 1
Output
wow!golden legendary!
awsl!
wow!golden legendary!
wow!golden legendary!