С каждым днем информационные технологии развиваются и все сильнее проникают во все сферы деятельности людей. Трудно представить, но наиболее современные технологии попадают и в фермерскую деятельность!

На большой ферме есть луг, на котором пасутся овечки. Овечек всего n и на каждой из них написан уникальный номер от 1 до n — ведь овечек нужно различать и помнить информацию о каждой, а они все так сильно похожи! Луг представляет из себя бесконечную последовательность участков, пронумерованных от 1 до бесконечности. Про овечку с номером i известно, что она любит пастись на участках с номерами от l_i до r_i, включительно.

За овечками следят два сотрудника: Первый и Второй. Первый просыпается рано утром, выводит овечек на лужайку и уходит. Вечером приходит Второй и собирает всех овечек.

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

Вечером на лужайку пришел Второй, собрал всех овечек и попытался выстроить в шеренгу. Но не тут-то было! Овечки-то были связаны, поэтому они совсем не собирались выстраиваться так, как хотел Второй! Развязать овечек у Второго не было ни сил, ни возможности, поэтому он решил оставить все как есть, с одним условием: он захотел выстроить овечек в шеренгу так, чтобы максимальное расстояние между двумя связанными овечками было как можно меньше. Расстояние между овечками — это количество овечек в шеренге, находящихся между двумя данными.

Помогите Второму найти нужную расстановку.