| Codeforces Round 312 (Div. 2) |
|---|
| Закончено |
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 задал много вопросов и запутался во всех этих ответах, так что он попросил вас помочь ему. Вам даны вопросы и ответы на них, можете ли вы определить, сообщала ли игра противоречивую информацию или нет? Если информация непротиворечива, и вершина выхода определяется однозначно, то выведите её номер. Если информация непротиворечива, но вершина выхода однозначно не определяется, то выведите, что было задано недостаточное количество вопросов. В противном случае, сообщите, что информация противоречива.
В первой строке записано два целых числа h, q (1 ≤ h ≤ 50, 0 ≤ q ≤ 105), высота дерева и количество вопросов соответственно.
В каждой из следующих q строк будет записано по четыре целых числа i, L, R, ans (1 ≤ i ≤ h, 2i - 1 ≤ L ≤ R ≤ 2i - 1, 
), обозначающих запрос, описанный в условии, и его ответ (ans = 1, если ответ — "Yes" и ans = 0, если ответ — "No").
Если информация, полученная от игры, противоречива, выведите: "Game cheated!" (игра сжульничала) без кавычек.
Если информация непротиворечива, и можно однозначно найти выход из лабиринта, выведите его номер.
В противном случае, выведите: "Data not sufficient!" (недостаточно данных) без кавычек.
3 1
3 4 6 0
7
4 3
4 10 14 1
3 6 6 0
2 3 3 1
14
4 2
3 4 6 1
4 12 15 1
Data not sufficient!
4 2
3 4 5 1
2 3 3 1
Game cheated!
Вершина u называется предком вершины v тогда и только тогда, когда
- u — та же самая вершина, что и v,
- u — непосредственный родитель вершины v,
- либо u — предок непосредственного родителя вершины v.
В первом тесте дано 4 вершины-листа 4, 5, 6, 7. Первый вопрос говорит, что данная вершина не находится в диапазоне [4, 6], так что выход — это вершина номер 7.
Во втором тесте дано 8 вершин-листьев. После первого вопроса становится известно, что выход находится в диапазоне [10, 14]. После второго и третьего вопроса становится понятно, что только узел номер 14 подходит. Смотрите на изображение ниже для разъяснений.
