← 返回题目列表

Codeforces · 558/D

D. 猜猜你的出路!二

中文机器翻译题面 查看原题

Amr 购买了一款新视频游戏“猜你出路!II”。游戏的目标是找到迷宫的出口,该出口看起来像高度为 h 的完美二叉树。玩家最初站在树的根部,树的出口位于某个叶节点。

让我们对树的所有节点进行索引,这样

- 根号是 1
- 每个内部节点 i (i ≤ 2h - 1 - 1) 将有一个索引 = 2i 的左子节点和一个索引 = 2i + 1 的右子节点

节点的级别定义为 1(对于根),或 1 + 节点的父节点级别。 h 层的顶点称为叶子。迷宫的出口位于某个叶子节点n,玩家不知道出口在哪里,所以他必须猜测出口!

在新版本的游戏中,允许玩家提出格式为“祖先(exit, i)节点号是否属于范围[L, R]?”的问题。这里的祖先(v,i)是位于第i层的节点v的祖先。游戏只会回答“是”或“否”。该游戏的设计并不总是正确回答,有时还会作弊来迷惑玩家!

Amr 问了很多问题,并对所有这些答案感到困惑,所以他请求你帮助他。给定问题及其答案,您能否确定游戏是否讲述了矛盾的信息?如果信息不矛盾并且可以唯一确定出口节点,则输出其编号。如果信息不矛盾,但退出节点定义不唯一,则输出问题数不够。否则输出信息矛盾。

输入

第一行包含两个整数h、q (1 ≤ h ≤ 50, 0 ≤ q ≤ 105),分别为树的高度和问题数。

接下来的 q 行将包含四个整数,每个 i、L、R、ans (1 ≤ i ≤ h, 2i - 1 ≤ L ≤ R ≤ 2i - 1, $$ans \in \{0, 1\}$$),表示语句中描述的问题及其答案(如果答案为“是”,则 ans = 1;如果答案为“否”,则 ans = 0)。

输出

如果游戏提供的信息矛盾则输出“游戏作弊!”没有引号。

否则,如果您可以唯一标识迷宫的出口,则输出其索引。

否则输出“数据不足!”没有引号。

示例

输入 #1

3 1
3 4 6 0

输出 #1

7

输入 #2

4 3
4 10 14 1
3 6 6 0
2 3 3 1

输出 #2

14

输入 #3

4 2
3 4 6 1
4 12 15 1

输出 #3

Data not sufficient!

输入#4

4 2
3 4 5 1
2 3 3 1

输出#4

Game cheated!

注意

节点 u 是节点 v 的祖先当且仅当

- u 与 v 是同一节点,
- u 是节点 v 的父节点,
- 或者 u 是节点 v 的父节点的祖先。

在第一个示例测试中,有 4 个叶节点 4, 5, 6, 7。第一个问题表明该节点不在范围 [4, 6] 中,因此出口是节点号 7。

在第二个示例测试中,有 8 个叶节点。在第一个问题之后,出口位于 [10, 14] 范围内。在第二个问题和第三个问题之后,只有节点号 14 是正确的。检查下图即可完全理解。