Фирма по грузоперевозкам привезла к воротам загородного домазаказанный домашний кинотеатр в очень большой кубической коробкеразмерами \(1 \times 1 \times 1\) метр. Таккак машину на территорию участка не пустили, коробка была сгружена уворот. Одна из ее сторон (имеется в виду грань куба) помечена как хрупкая - та, рядом с которой расположен экран.Коробка выгружена так, что хрупкая сторона не находится на земле.

Из-за огромных размеров коробки по участку её можно передвигать только перекатывая через ребра. При этом хрупкая сторона не должна оказаться на земле, иначе экран немедленносломается.

Участок имеет форму прямоугольника размером \(N\) на \(M\) метров. План участка нарисован на клетчатой бумаге, размер клетки которой соответствует 1 метру. На плане введена система координат так, что левая нижняя клетка плана имеет координату \((1,1)\), правая нижняя - \((1,M)\), правая верхняя - \((N,M)\).

Изначально коробка расположена рядом с воротами, в клетке, которая на плане имеет координаты \((1, b)\) (эта клетка расположена у нижней стороны плана участка), а переместить ее надо к двери - на другую клетку с координатами \((c, d)\). Задано, с какой стороны исходно находится хрупкая сторона. С какой стороны она будет после перекатываний - не важно (важно лишь, чтобы она не оказалась на земле).Участок окружён по периметру забором, поэтому коробку не получится выкатить за пределы участка.

Ваша задача - помочь грузчикам перекатить коробку от ворот до двери дома, не поломав экрана.

Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.

Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:

• в каждом ряду количество девушек-студенток и количество юношей-студентов различалось бы не более чем на 1;
• на каждой "вертикали мест" (т. е. местах, имеющих один и тот же номер, но расположенных в разных рядах) количество девушек-студенток и количество юношей-студентов также различалось бы не более чем на 1.

Каждое место в зале определяется двумя числами от 1 до \(S\) - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \(i\) расположено в \(a_i\)-м ряду и имеет в нём номер \(b_i\). Поскольку ценители прекрасного могли занять совершенно любые места, числа \(a_i\) и \(b_i\) могут принимать любые значения от 1 до \(S\). В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.

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

По заданному числу \(N\) найдите натуральное число \(K\), такое что:

• число \(\overline{KK}\) (повторённая два раза десятичная запись \(K\)) является точным квадратом некоторого натурального числа (см. примеры),
• \(K\) при записи в десятичной системе счисления имеет длину от \(N\) до \(N+23\) (включительно).

Так, для \(N=1\) условию удовлетворяет, например, число \(K=13223140496\), т.к. оно имеет длину 11, что укладывается в диапазон от 1 до 24, а также число \(1322314049613223140496\) является точным квадратом натурального числа.

На прямой задано \(N\) попарно различных отрезков \([a_i, b_i]\) (\(i = 1, 2, \dots, N\), \(a_i < b_i\)). Будем говорить, что отрезок номер \(i\) непосредственно содержится в отрезке номер \(j\) (\(i \ne j\)), если:

• он полностью принадлежит \(j\)-му (то есть \(a_j \le a_i\) и \(b_i \le b_j\)),
• среди заданных \(N\) отрезков не найдётся такого отрезка (с номером \(k\)), что \(i\)-й отрезок принадлежит \(k\)-му и \(k\)-й принадлежит \(j\)-му (здесь \(i\), \(j\) и \(k\) - различные числа).

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