시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

В школе номер 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$-й, включительно. Группы можно выводить в любом порядке. Каждый класс должен войти ровно в одну группу.

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

예제 입력 1

5 1 2
7 5
10 1
2 3
2 6
4 3

예제 출력 1

4
1 1
2 3
4 4
5 5