Шерлок и Мориарти встретились для финальной битвы умов. Шерлок дал Мориарти правильный выпуклый n-угольник. Кроме того, он дал ему некоторые диагонали в этом многоугольнике, которые разделяют его на регионы. Гарантируется, что диагонали не пересекаются во внутренних точках.

Шерлок посчитал для каждого региона его важность. Важность региона, образованного вершинами многоугольника с номерами a₁, a₂, ... , a_x, равна 2^a₁ + 2^a₂ + ... + 2^a_x. Затем Шерлок упорядочил регионы в порядке увеличения важности. После этого он присвоил каждому региону уникальный номер от 1 до k, где k — количество регионов, а номер региона это его позиция в упорядоченном по важности списке.

Шерлок хочет, чтобы Мориарти раскрасил регионы, используя не более чем 20 цветов так, чтобы все простые пути между двумя одноцветными регионами проходили через хотя бы один регион, покрашенный в цвет с номером меньше, чем номер цвета данных регионов. Простой путь между двумя регионами f и h это последовательность регионов r₁, r₂, ... r_t такая, что r₁ = f, r_t = h, для каждого 1 ≤ i < t регионы r_i и r_i + 1 имеют общую сторону, а также r_i = r_j если и только если i = j.

Мориарти не смог ответить и спросил решение у Шерлока. Помогите Шерлоку предоставить ответ Мориарти.