트리를 안 쓰는 트리 문제

지호는 작년 겨울 학교에 설치했던 크리스마스트리를 철거하려고 한다. 트리에 달려 있던 조명을 버리기 아까웠던 지호는 이 조명으로 예쁜 장식을 만들려고 한다.

트리 조명은 $N^2$개의 전구가 일자로 연결된 형태이다. 각 전구는 $N$개의 색상 중 하나를 가지며, 왼쪽에서 $i$번째 전구의 색상은 $((i-1)\mod N) + 1$이다. 아래 그림 1은 $N=4$인 경우이다.

[그림 1] $4^2$개의 일자로 연결된 전구. 전구에 쓰인 수는 그 전구의 색상을 나타낸다.

지호는 이 조명을 적당히 자르고 이어 붙여서, 가로와 세로가 각각 $N$개의 전구로 이루어진 정사각형 장식을 만들려고 한다. 잘라낸 조명은 돌리거나 뒤집을 수 없다. $i$행 $j$열 칸에 놓인 조명의 색상을 $a_{i,j}$라고 할 때, 모든 $(i,j)$에 대해 $a_{i,j}-i-j+1$이 $N$의 배수가 되어야 한다. 아래 그림 2는 $N=4$인 경우이다. 그림의 색상은 전구의 색을 나타내는 것이 아니라, 각 조각이 어디에 배치되었는지를 구분하기 위한 것이다.

[그림 2] 그림 1의 전구를 적당히 잘라 붙여 정사각형으로 재배치한 모습.

조명을 자르는 일은 번거로우므로, 지호는 자르는 횟수를 최소화하고 싶어 한다. 자르는 횟수가 최소인 경우를 하나 찾아 조각의 개수와 배치를 출력하자. $t$번째 조각이 왼쪽에서 $s$번째 전구부터 $e$번째 전구까지로 이루어져 있고, 이 조각의 맨 왼쪽 전구가 정사각형의 $i$행 $j$열에 놓인다면, 각 조각에 대해 $s$, $e$, $i$, $j$를 계산해서 출력해야 한다.

첫 번째 줄에 양의 정수 $N$이 주어진다.

첫 번째 줄에 잘라서 만든 조각의 개수 $M$을 출력한다.

두 번째 줄부터 $M$개의 줄을 출력한다. $t$번째 줄에는 $t$번째 조각이 가진 전구의 범위 $s$와 $e$, 그리고 이 조각의 맨 왼쪽 전구가 놓이는 위치 $i$와 $j$를 공백으로 구분하여 출력한다.

$1 \leq N \leq 1000$