베라의 등산로 만들기

등산을 좋아하는 베라가 자기만의 등산로 망을 만들려고 한다. 이 망에는 $1$번부터 $V$번까지 번호가 붙은 장소 $V$개와 양방향 등산로 $E$개가 있고, $i$번 등산로는 서로 다른 두 장소 $a_i$와 $b_i$를 직접 잇는다. 망은 연결되어 있어야 하므로 어느 두 장소 사이든 등산로를 따라 오갈 수 있어야 한다. 같은 두 장소를 직접 잇는 등산로가 여러 개 있어도 된다.

$a < b$인 두 장소 $a$와 $b$는, 같은 등산로를 두 번 넘게 지나지 않으면서 $a$에서 $b$까지 갔다가 다시 $a$로 돌아올 수 있으면 아름답게 연결된 쌍이 된다. 베라는 아름답게 연결된 쌍이 정확히 $K$개인 망을 아름다운 망이라고 부른다.

망이 너무 커지면 안 되므로 $1 \le V, E \le 5000$을 만족해야 한다.

거의 모든 $K$에 대해 아름다운 망은 여러 가지가 있으므로, 이 문제는 그중 하나를 정해서 묻는다. 어떤 망을 출력해야 하는지는 출력 단락에 정확히 적혀 있다.

첫째 줄에 정수 $K$가 주어진다. ($1 \le K \le 10^7$)

아래 규칙대로 망을 만들어 출력한다. 다른 답은 인정하지 않는다.

먼저 $K$를 블록으로 나눈다. 빈 목록에서 시작해 $K > 0$인 동안 다음을 반복한다. $m \ge 2$이면서 $m(m-1)/2 \le K$인 가장 큰 정수 $m$을 골라 목록 뒤에 붙이고, $K$를 $K - m(m-1)/2$로 바꾼다. 이렇게 얻은 목록을 $m_1, m_2, \dots, m_t$라 하고 $V = m_1 + m_2 + \dots + m_t$로 둔다.

장소에 $1$번부터 $V$번까지 번호를 붙이고 각 블록에 연속한 번호 구간을 준다. 블록 $1$은 $1$번부터 $m_1$번까지, 블록 $2$는 그다음 $m_2$개를 차지하는 식이다. 블록 $j$의 첫 장소를 $s_j$, 마지막 장소를 $e_j$라고 하자.

출력의 첫째 줄에는 $V$와 $E = V + t - 1$을 공백 하나로 구분해 출력한다. 이어지는 $E$개의 줄에는 등산로 하나의 두 장소를 공백 하나로 구분해, 아래에 적힌 순서대로 출력한다.

$j = 1, 2, \dots, t$ 순서로 블록 $j$의 등산로를 출력한다.

• $m_j = 2$이면 "$s_j$ $e_j$" 줄을 두 번 출력한다.
• $m_j \ge 3$이면 등산로 $(s_j, s_j + 1)$, $(s_j + 1, s_j + 2)$, ... , $(e_j - 1, e_j)$와 마지막으로 $(e_j, s_j)$까지 $m_j$개를 한 줄에 하나씩, 각 줄에 앞쪽 장소를 먼저 적어 출력한다.

블록 $t$개의 등산로를 모두 출력한 다음, 블록을 잇는 등산로 $t - 1$개를 출력한다. $j = 2, 3, \dots, t$ 순서로 "$e_{j-1}$ $s_j$" 줄을 출력하면 된다.

이 망은 연결되어 있고, 아름답게 연결된 쌍이 정확히 $K$개이며, 입력으로 가능한 모든 $K$에 대해 $V \le 4587$과 $E \le 4592$를 만족한다.

첫 번째 예제는 $K = 2$라서 블록이 $m_1 = 2$, $m_2 = 2$로 나뉜다. 장소 $1$과 $2$를 등산로 두 개가 잇고, 장소 $3$과 $4$를 등산로 두 개가 이으며, 장소 $2$와 $3$ 사이의 등산로가 두 블록을 연결한다. 아름답게 연결된 쌍은 $(1, 2)$와 $(3, 4)$ 두 개다.

두 번째 예제는 $K = 6$이라서 블록이 $m_1 = 4$ 하나뿐이고, 망은 장소 네 개로 이루어진 사이클이 된다. 장소 쌍 여섯 개가 모두 아름답게 연결된 쌍이다.