Все наши герои имеют хобби. И Федор не исключение. Ему очень нравится ходить в супермаркет около дома и покупать всякие вещи.
Все товары в супермаркете имеют уникальный целый номер. И для каждого уникального целого номера найдется ровно один товар в супермаркете. Так как Федор делает много покупок, ему хотелось бы посещать супермаркет с экономией. Поэтому у него есть n скидочных купонов. i-й купон действует на товарах с номерами с li-го по ri-й включительно. Сегодня он решил взять с собой в супермаркет ровно k купонов.
Федор хочет выбрать k купонов так, чтобы количество таких товаров x, что на товар x действуют все купоны, было максимально (для лучшего понимания посмотрите примеры). Федор, кроме денег, ещё хочет сэкономить силы и время, поэтому просит вас сделать выбор купонов. Помогите Федору!
Выходные данные
В первой строке следует вывести единственное целое число — максимальное количество товаров, на которые действуют все купоны. То есть товар, на который не действует какой-то из выбранных купонов, не считается.
В следующей строке выходных данных следует вывести k различных целых чисел p1, p2, ..., pk (1 ≤ pi ≤ n) — номера купонов, выбрав которые, мы получим максимальное количество товаров, на которые действуют все эти купоны.
Если оптимальных ответов несколько, выведите любой.
Примечание
В первом примере, если Федор возьмет первые два купона, то они оба будут действовать на все товары в отрезке [40, 70]. Всего таких товаров 31.
Во втором примере ни на один товар не действуют два купона, поэтому ответ 0. Федор может взять любые два купона в этом примере.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
1 100
40 70
120 130
125 180
|
31
1 2
|
|
2
|
3 2
1 12
15 20
25 30
|
0
1 2
|
|
3
|
5 2
1 10
5 15
14 50
30 70
99 100
|
21
3 4
|