#3880. 炼辰

内存限制:256 MiB 时间限制:10 Sec

题目描述

Background

载着荣耀的流光在星云上启程,不知终落谁手。

Description

星云由N颗星组成,呈环状分布(按照顺时针方向标号顺序为1,2,3,...,N,1,2,3...),流光可以有两种流动方式:

    一、沿顺时针由一颗星滑向它的下一颗星。

    二、我们定义“焱”为一种传送机制,即若两个星球之间燃烧着“焱”,则顺时针序靠后的星球,可以通过此机制传送回顺时针序靠前的那个星球。

某一天星云被破坏了,只剩下了最后一抹荣耀流光被两股神秘力量角逐。而破坏带来了两个限制:

    一、某颗行星P被设定为流光禁区(即永远无法被选择为流光的落脚点)。

二、一旦一颗星被流光划过,那么就再也不能被经过了。

现在两种神秘力量轮流引导流光的流动,先手在第一次操作时为确定流光的起始位置,问谁可以拿到最后一次的掌控权来获得胜利?

另外学者们发现,“焱”具有特殊的性质:

如果把每个“焱”视为零点为其两个星球的类似圆弧的轨迹,那么两条轨迹之间不会相交或外切,但是内切和包含以及相离都是合法的。

输入格式

第一行三个整数nmp表示星云上n个点按标号顺时针环形排列,有m个“焱”,行星p为流光禁区。

接下来有m行,每行两个整数uv,表示uv之间存在一个“焱”。

输出格式

如果先手胜,输出“dawn”,否则输出“galaxy”。

样例

样例输入


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

样例输出


			
dawn

数据范围与提示

1<=p,u,v<=n<=1,000,000

0<=m<=2,000,000