32996번 - 트리를 안 쓰는 트리 문제 스페셜 저지

문제

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

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

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

지호는 이 조명을 적당히 자르고 이어붙여 가로와 세로로 각각 $N$개씩의 전구가 배치된 정사각형 형태의 장식을 만들려 한다. 단, 잘라낸 각 조명은 돌리거나 뒤집을 수 없다. 이때, $i$행 $j$열에 위치한 (즉 $(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,ドル 그리고 $t$번째 조각의 맨 왼쪽 전구가 배치되는 위치 $i$와 $j$를 공백으로 구분하여 출력하여라.

제한

• 1ドル \leq N \leq 1000$

힌트