Amr купил новую видеоигру "Угадай, где выход! II". Задача этой игры — найти выход в лабиринте, имеющим вид полного двоичного дерева высоты h. Изначально игрок стоит в корне дерева, а выход из дерева располагается в некотором листе дерева.
Пронумеруем все вершины дерева, таким образом, что
- Корень дерева имеет номер 1
- У каждой внутренней вершины i (i ≤ 2h - 1 - 1) есть левый потомок с номером 2i и правый потомок с номером 2i + 1
Уровень вершины определяется как 1 для корня, либо как 1 + уровень вершины-родителя в противном случае. Вершины уровня h называются листьями. Выход из лабиринта расположен в некотором листе n, причём игрок не знает, где выход, так что цель игры — угадать, где выход!
В новой версии игры игроку дозволяется задавать вопросы формата "Принадлежит ли номер ancestor(exit, i) отрезку [L, R]?". Здесь за ancestor(v, i) обозначается предок вершины v, расположенный на уровне i, а exit обозначает вершину с выходом. Игра может отвечать только "Yes" (Да) или "No" (Нет). Игра устроена так, что она не всегда отвечает верно, и иногда она сообщает ложную информацию, чтобы сбить игрока с толку!
Amr задал много вопросов и запутался во всех этих ответах, так что он попросил вас помочь ему. Вам даны вопросы и ответы на них, можете ли вы определить, сообщала ли игра противоречивую информацию или нет? Если информация непротиворечива, и вершина выхода определяется однозначно, то выведите её номер. Если информация непротиворечива, но вершина выхода однозначно не определяется, то выведите, что было задано недостаточное количество вопросов. В противном случае, сообщите, что информация противоречива.
Выходные данные
Если информация, полученная от игры, противоречива, выведите: "Game cheated!" (игра сжульничала) без кавычек.
Если информация непротиворечива, и можно однозначно найти выход из лабиринта, выведите его номер.
В противном случае, выведите: "Data not sufficient!" (недостаточно данных) без кавычек.
Примечание
Вершина u называется предком вершины v тогда и только тогда, когда
- u — та же самая вершина, что и v,
- u — непосредственный родитель вершины v,
- либо u — предок непосредственного родителя вершины v.
В первом тесте дано 4 вершины-листа 4, 5, 6, 7. Первый вопрос говорит, что данная вершина не находится в диапазоне [4, 6], так что выход — это вершина номер 7.
Во втором тесте дано 8 вершин-листьев. После первого вопроса становится известно, что выход находится в диапазоне [10, 14]. После второго и третьего вопроса становится понятно, что только узел номер 14 подходит. Смотрите на изображение ниже для разъяснений.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
3 4 6 0
|
7
|
|
2
|
4 3
4 10 14 1
3 6 6 0
2 3 3 1
|
14
|
|
3
|
4 2
3 4 6 1
4 12 15 1
|
Data not sufficient!
|
|
4
|
4 2
3 4 5 1
2 3 3 1
|
Game cheated!
|