Ямочка большая любительница головоломок, и поэтому недавно купила себе новый пазл. Собранный пазл представляет собой прямоугольную таблицу из K строк и L столбцов, из K · L квадратиков одинакового размера, называемых кусочками пазла. Каждая сторона кусочка пазла может быть углублением определенного типа, либо штырьком определенного типа, либо гладкой, если эта сторона является границей пазла. Если два кусочка в собранном пазле соседние по стороне, то у одного кусочка на этой стороне должен быть штырёк, а у другого углубление, причем одинакового типа.

К сожалению, Ямочка оказалась не очень опытной в сборке пазлов, поэтому купила набор для новичков: в данном наборе типы всех штырьков различны, типы всех углублений тоже. Более формально: каждому типу соединения соответствует ровно один штырёк и одно углубление, либо не соответствует ничего.

Вскрыв коробку с пазлом и немного потыкав кусочки друг с другом, Ямочка поняла, что головоломки это не её, поэтому задача собрать данный пазл ложится целиком и полностью на вас.

В первой строке дано целое число N (1 ≤ N ≤ 10⁵) — количество кусочков пазла.

В следующих N строках дается по 4 целых числа l_i, u_i, r_i, d_i (−10⁶ ≤ l_i, u_i, r_i, d_i ≤ 10⁶) — описание соответственно левой, верхней, правой и нижней стороны i-го кусочка пазла. Пусть t — одно из этих чисел, тогда:

• если t > 0, то на этой стороне расположен штырёк типа |t|;
• если t < 0, то на этой стороне расположено углубление типа |t|;
• если t = 0, то эта сторона гладкая и обязана находиться на внешней границе пазла.

Конечно же, любой кусочек можно вращать по часовой стрелке на любой градус, кратный 90^∘.

В первой строке выведите два числа K, L (1 ≤ K, L ≤ N; K × L = N).

В следующих K строчках выведите по L целых чисел — номера кусочков в порядке ввода, которые должны стоять на этом месте в собранном пазле.

Каждая деталь должна встретиться в ответе ровно один раз. Повороты деталей в выходных данных указывать не требуется. Ответ считается корректным, если существует набор поворотов, при котором все соседние стороны совместимы, а гладкие стороны находятся на границе.

Гарантируется, что ответ всегда есть. Если подходящих ответов несколько, выведите любой из них.