학교 민주주의

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$은 학교의 학급 수이고, $l$과 $r$은 각각 한 모둠에 들어갈 수 있는 학급 수의 최솟값과 최댓값이다. 다음 $n$개 줄에 정수 $b_i$와 $g_i$가 주어진다 ($1 \le b_i, g_i \le 10\,000$). $b_i$와 $g_i$는 각각 $i$번째 학급의 남학생 수와 여학생 수이다.

첫째 줄에 교감이 생각하는 최적의 모둠 나누기에서 모둠의 수 $x$를 출력한다. 다음 $x$개 줄에 정수 $s_i$와 $f_i$를 출력한다 ($1 \le s_i \le f_i \le n$). 이는 $i$번째 모둠에 $s_i$번째부터 $f_i$번째까지의 학급을 포함시켜야 한다는 뜻이다. 모둠은 어떤 순서로 출력해도 된다. 모든 학급은 정확히 한 모둠에 들어가야 한다.

모든 제약을 만족하는 모둠 나누기가 적어도 하나 존재함이 보장된다. 최적의 답이 여러 개라면 아무거나 출력한다.