19889번 - Школьная демократия 스페셜 저지다국어

문제

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

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

Пусть в результате выборов в школьный совет пройдет $B$ мальчиков и $G$ девочек. По опыту прошлых лет завуч думает, что совет будет работать тем эффективней, чем больше разность $B-G$ числа мальчиков и числа девочек в совете. Обратите внимание, что эта величина может оказаться и отрицательной, завуч хочет максимизировать именно само значение этой величины, а не ее модуль. Например, из вариантов $B = 2,ドル $G = 5,ドル при котором $B - G = -3,ドル и $B = 3,ドル $G = 4,ドル при котором $B - G = -1,ドル второй вариант предпочтительнее.

Всего в школе $n$ классов, и завуч уже подготовил их список. Теперь ему предстоит разбить их на группы. Группа не может содержать меньше чем $l$ классов, иначе совет будет очень большим. В то же время группа не может содержать больше чем $r$ классов, иначе учащиеся не смогут договориться о выдвигаемых кандидатах. Напомним, что каждая группа должна быть составлена из классов, которые идут подряд в списке завуча.

Помогите завучу найти оптимальное по его мнению разбиение на группы.

입력

В первой строке входного файла содержится два целых числа $n,ドル $l$ и $r$ (1ドル \le n \le 100,000円,ドル 1ドル \le l \le r \le n$) --- количество классов в школе, максимальное и минимальное допустимое количество классов в одной группе соответственно. В следующих $n$ строках содержится по два целых числа $b_i$ и $g_i$ (1ドル \le b_i, g_i \le 10,000円$) --- количество мальчиков и девочек в $i$-м классе соответственно.

출력

В первой строке выведите целое число $x$ --- количество групп в оптимальном по мнению завуча разбиении. В следующих $x$ строках выведите по два числа $s_i$ и $f_i$ (1ドル \le s_i \le f_i \le n$). Это означает, что в $i$-ю группу следует включить классы с $s_i$-го по $f_i$-й, включительно. Группы можно выводить в любом порядке. Каждый класс должен войти ровно в одну группу.

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

제한

힌트