1992 - contest1 E 动作游戏

小 i 是一位动作游戏大师,经常能在游戏中打出一些精细的操作。众所周知,在一个动作游戏中,打败一个 BOSS 往往需要一个合理的站位,不错的引招,对 BOSS 的攻击作出合理的应对方式。而应对 BOSS 的攻击就在于闪(fan)避(gun)。

为了简化问题,我们不考虑角色的站位,只考虑 BOSS 的攻击和闪避操作。

BOSS 的一套组合技往往有着多段攻击判定,每一段攻击判定都有一个持续存在的时间区间,我们设 BOSS 的一套组合技的第 i 段攻击判定持续的时间段为区间 (l_i, r_i)

为了应对 BOSS 的攻击,玩家需要进行闪避。玩家可以在任意时刻进行闪避操作,假设玩家在 s 时刻进行了一次闪避操作,那么玩家将在 (s, s + t) 的这段时间内获得无敌帧,无敌帧可以免疫 BOSS 的攻击判定。

注意,玩家在无敌帧持续的过程中是不能够进行闪避操作的,也就是说下一次闪避操作必须等到上一次闪避操作结束之后再进行。

如果 BOSS 的攻击判定的持续时间内玩家持续拥有无敌帧,那么玩家将躲过这次攻击判定,否则将会被 BOSS 攻击。

值得注意的是,尽管小 i 身为一个动作游戏大师,对闪避时机的掌控已经到达登峰造极的境界,可以连续进行多次闪避操作,但是在上一次闪避操作结束和下一次闪避操作开始的那一瞬间,小 i 依然会吃到攻击判定(因为闪避的时间是一段开区间,如果在上一个闪避结束的瞬间 BOSS 的攻击判定未结束的话,即使立即进行下一段闪避,也会吃到攻击判定)。

小 i 将在 0 时刻进入 BOSS 房间,进入 BOSS 房间后他可以立刻开始闪避操作,他想知道对于 BOSS 发出的一套组合技,他能不能完美规避过去。

Input

第一行两个整数 n, t,表示 BOSS 的这个组合技的攻击判定数量和小 i 闪避的持续时间。

接下来 n 行每行两个整数代表 l_i, r_i

1 \leq n \leq 10^5

1 \leq t \leq 10^9

1 \leq l_i < r_i \leq 10^9

注意 BOSS 的攻击判定可能重叠。

Output

如果小 i 能成功规避,输出 HEIR OF FIRE DESTORYED.,否则输出 YOU DIED.

Examples

Input

3 3
1 3
2 3
2 5

Output

YOU DIED.

Input

3 3
1 4
3 4
2 4

Output

HEIR OF FIRE DESTORYED.

Input

2 5
1 2
4 7

Output

YOU DIED.

Hint

样例3解释: 注意小 i 是在 0 时刻进入 BOSS 房间的,所以即使他刚进入立即闪避,也会在 5 时刻落入 BOSS 的判定范围内,所以会被攻击。

新版界面
Time Limit 1 second
Memory Limit 256 MB
Discuss Stats
上一题 下一题