CF558D.Guess Your Way Out! II

Amr bought a new video game "Guess Your Way Out! II". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let's index all the nodes of the tree such that

• The root is number 1
• Each internal node i (i ≤ 2_h_ - 1 - 1) will have a left child with index = 2_i_ and a right child with index = 2_i_ + 1

The level of a node is defined as 1 for a root, or 1 + level of parent of the node otherwise. The vertices of the level h are called leaves. The exit to the maze is located at some leaf node n, the player doesn't know where the exit is so he has to guess his way out!

In the new version of the game the player is allowed to ask questions on the format "Does the ancestor(exit, i) node number belong to the range [L, R]?". Here ancestor(v, i) is the ancestor of a node v that located in the level i. The game will answer with "Yes" or "No" only. The game is designed such that it doesn't always answer correctly, and sometimes it cheats to confuse the player!.

Amr asked a lot of questions and got confused by all these answers, so he asked you to help him. Given the questions and its answers, can you identify whether the game is telling contradictory information or not? If the information is not contradictory and the exit node can be determined uniquely, output its number. If the information is not contradictory, but the exit node isn't defined uniquely, output that the number of questions is not sufficient. Otherwise output that the information is contradictory.

Amr 购买了一款新视频游戏《猜猜你的出路！II》。游戏目标是找到一个形如高度为 $h$ 的完美二叉树的迷宫的出口。玩家初始时站在树的根节点，而迷宫出口位于某个叶节点上。

我们对树的所有节点进行如下编号：

• 根节点编号为 $1$；
• 每个内部节点 $i$（满足 $i \leq 2^{h-1} - 1$）的左子节点编号为 $2i$，右子节点编号为 $2i + 1$。

节点的层号（level）定义如下：根节点的层号为 $1$；其余任意节点的层号为其父节点的层号加 $1$。所有层号为 $h$ 的节点称为叶节点（leaves）。迷宫出口位于某个叶节点 $n$ 上；但玩家并不知道出口具体在哪个叶节点，因此他必须通过猜测来寻找出路！

在游戏的新版本中，玩家可以提出如下形式的问题：“节点 $\text{ancestor}(\text{exit},\, i)$ 的编号是否属于区间 $[L,\, R]$？”其中 $\text{ancestor}(v,\, i)$ 表示节点 $v$ 在第 $i$ 层上的祖先节点。游戏仅回答“Yes”或“No”。但该游戏被特别设计为并非总是给出正确答案，有时它会故意撒谎以迷惑玩家！

Amr 提出了大量问题，却被这些答案搞得晕头转向，于是他请你帮忙。给定所有提问及其对应答案，你能否判断这些信息是否存在矛盾？若信息不矛盾且能唯一确定出口节点，则输出该节点编号；若信息不矛盾但无法唯一确定出口节点，则输出“提问数量不足”；否则输出“信息矛盾”。

The first line contains two integers h, q (1 ≤ h ≤ 50, 0 ≤ q ≤ 105), the height of the tree and the number of questions respectively.

The next q lines will contain four integers each i, L, R, ans (1 ≤ i ≤ h, 2_i_ - 1 ≤ L ≤ R ≤ 2_i_ - 1, ), representing a question as described in the statement with its answer (ans = 1 if the answer is "Yes" and ans = 0 if the answer is "No").

第一行包含两个整数 $h$ 和 $q$（$1 \le h \le 50$，$0 \le q \le 10^5$），分别表示树的高度和问题的数量。

接下来的 $q$ 行每行包含四个整数 $i$、$L$、$R$、$ans$（$1 \le i \le h$，$2^{i-1} \le L \le R \le 2^i - 1$，），表示题目描述中的一个问题及其答案（若答案为“Yes”，则 $ans = 1$；若答案为“No”，则 $ans = 0$）。

If the information provided by the game is contradictory output "Game cheated!" without the quotes.

Else if you can uniquely identify the exit to the maze output its index.

Otherwise output "Data not sufficient!" without the quotes.

如果游戏提供的信息自相矛盾，则输出“Game cheated!”（不含引号）。

否则，若能唯一确定迷宫的出口，则输出其索引。

否则，输出“Data not sufficient!”（不含引号）。

Node u is an ancestor of node v if and only if

• u is the same node as v,
• u is the parent of node v,
• or u is an ancestor of the parent of node v.

In the first sample test there are 4 leaf nodes 4, 5, 6, 7. The first question says that the node isn't in the range [4, 6] so the exit is node number 7.

In the second sample test there are 8 leaf nodes. After the first question the exit is in the range [10, 14]. After the second and the third questions only node number 14 is correct. Check the picture below to fully understand.

节点 $u$ 是节点 $v$ 的祖先，当且仅当满足以下条件之一：

• $u$ 与 $v$ 是同一个节点；
• $u$ 是节点 $v$ 的父节点；
• $u$ 是节点 $v$ 的父节点的祖先。

在第一个样例测试中，有 4 个叶子节点：4、5、6、7。第一个问题指出出口节点不在区间 $[4,\,6]$ 内，因此出口节点为编号 7。

在第二个样例测试中，共有 8 个叶子节点。第一个问题之后，出口节点位于区间 $[10,\,14]$ 内；再经过第二和第三个问题后，唯一满足条件的节点是编号 14。请参见下方图片以全面理解。