Небоскреб

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

На данный момент используется следующая двумерная модель. Строение описывается как прямоугольник, составленный из одинаковых блоков квадратной формы. Предполагается, что при аварии некоторые из блоков полностью разрушаются, а остальные остаются неповрежденными. Будем называть сегментом множество блоков, таких что из любого можно дойти до любого другого, если разрешается переходить из блока в блок, имеющий с ним общую сторону.

Считается, что сегмент стоит устойчиво, если один из его блоков соприкасается с нижней стороной прямоугольника.

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит одно целое число m (1 ≤ m ≤ 10 000). За ней следуют m строк, описывающих вертикальные столбцы. Описание производится в таком порядке: сначала записано число a_i оставшихся целыми фрагментов этого вертикального столбца, за которым следуют 2a_i чисел l⁽¹⁾_i, r⁽¹⁾_i, l⁽²⁾_i, r⁽²⁾_i, …, l^(ai)_i, r^(ai)_i, задающие нижние и верхние границы уцелевших фрагментов. При этом 1 ≤ l⁽¹⁾_i ≤ r⁽¹⁾_i , l⁽²⁾_i ≤ r⁽²⁾_i , . . . , l^(ai)_i ≤ r^(ai)_i ≤ 10⁶, для всех допустимых i и j выполнено r^(j)_i < l^(j+1)_i - 1. Сумма всех a_i не превосходит 100 000.

Выходные данные

В выходной файл OUTPUT.TXT выведите m чисел - высоты, на которых находится самый верхний блок в соответствующем вертикальном столбце.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]