Juku는 특별히 중요한 올림피아드를 준비하다가 다음 문제를 발견했다.

배열의 구간 합

길이가 $N$인 배열 $A$와 $(l, r)$ 형태의 쿼리 $Q$개가 주어진다.

각 쿼리마다 $A\[l] + A\[l + 1] + \cdots + A\[r]$의 값을 답으로 출력한다.

$N = Q = 10^5$임이 알려져 있다.

Juku는 이 문제를 풀기 위해 다음 의사코드를 작성했다.

lptr = 1, rptr = 1, sum = A[1], ops = 0

for each query (ql, qr):
    while rptr < qr:
        rptr += 1
        sum += A[rptr]
        ops += 1
    while lptr > ql:
        lptr -= 1
        sum += A[lptr]
        ops += 1
    while rptr > qr:
        sum -= A[rptr]
        rptr -= 1
        ops += 1
    while lptr < ql:
        sum -= A[lptr]
        lptr += 1
        ops += 1
    print sum

이 코드의 실행 시간이 제한 시간을 넘었다. 그러나 Juku는 어느 강의에서 "Mo's algorithm"이라는 이야기를 들은 기억이 어렴풋이 났고, 이렇게 생각하기 시작했다. 쿼리의 순서를 바꾸면 프로그램이 제한 시간 안에 들어갈 수 있을까? 그리고 쿼리 순서만 바꿔서 프로그램을 얼마나 빠르게 만들 수 있을까?

$Q$개의 쿼리 $(l, r)$이 주어진다. 쿼리는 균등 분포를 따른다고 보장된다(힌트의 참고 사항 참조). 위 의사코드를 실행한 뒤 ops의 최종 값이 최대한 작아지도록 쿼리를 재배열하라.

첫 줄에 공백으로 구분된 두 정수 $N$과 $Q$가 주어진다($N = Q = 10^5$). 이어지는 $Q$개의 줄에는 각각 공백으로 구분된 두 정수 $l$과 $r$이 주어진다($1 \le l \le r \le N$).

$Q$개의 줄을 출력한다. 각 줄에는 공백으로 구분된 두 정수 $l$과 $r$을 출력한다. 출력하는 쿼리는 입력 쿼리들의 순열이어야 한다.

실제 입력 파일은 다음 코드로 생성되었다.

print(100000, 100000)
for i in 1...100000:
    l = random(1, 100000)
    r = random(1, 100000)
    if (l < r):
        print(l, r)
    else:
        print(r, l)

여기서 random(1, 100000)은 $1 \le x \le 100\,000$을 만족하는 정수 $x$를 반환하며, 가능한 반환값은 모두 같은 확률로 나온다.