CF558D Guess Your Way Out! II

问题描述 Amr 买来了一个新的游戏，名叫 Guess Your Way Out! II。这个游戏需要你找到迷宫的出口。迷宫是一个高度为h的满二叉树，一开始你在根节点，迷宫的唯一出口在某一个叶子节点处。 这棵树的节点编号是这样规定的，根节点编号为 $1$，编号为 $i$ 的节点的左儿子编号为 $2\times i$，右儿子编号为 $2 \times i + 1$。每个节点的层次是这样定义的，根节点在第一层，儿子节点的层数在它的父亲节点的基础上增加 $1$。 一开始玩家并不知道迷宫的出口在哪里，于是就只能向游戏提问，每次的提问都是这样的：“出口节点的层数为 $i$ 的祖先节点的编号是否在区间 $[L,R]$ 内？”这时游戏会给出回答“是”或“不是”，不过这个游戏又是会出错，就会给出错误的回答。 Amr 已经进行了若干次提问，并记录下了每次的提问和回答，他想知道，游戏是否一定给出过错误的回答，通过这些答案能不能唯一确定出口的位置。于是 Amr 就来求助于你了。

第一行两个整数 $h$, $q$，表示完全二叉树迷宫的总层数和 Amr 的提问次数。 接下来 $q$ 行，每行四个整数 $i$, $L$, $R$, $ans$，表示 Amr 的一次提问和游戏给出的回答（$ans=1$表示“是”，$ans=0$表示“不是”）。

如果游戏一定给出过错误的回答，输出“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.