레몬컵 문제 배치하기

레몬컵 개최를 앞둔 다다스와 담유는 문제의 배치 순서를 두고 논쟁을 벌이고 있다. 다다스는 $N$개의 문제들을 다음과 같이 난이도 순서대로 배치하였다.

사진에 나온 난이도는 실제 문제의 난이도와 아무런 관계가 없음에 유의하라.

(난이도 배치)

하지만 이와 같은 배치가 마음에 들지 않는 담유는 문제들을 난이도 내림차순으로 배치하려고 한다.

담유는 문제의 순서를 뒤집기 위해 다음 연산을 사용할 수 있다.

$s_1 \ e_1 \ s_2 \ e_2$

이는 \textbf{$s_1$번째 문제부터 $e_1$번째 문제}까지, 그리고 \textbf{$s_2$번째 문제부터 $e_2$번째 문제}까지의 순서를 각각 뒤집는 연산이다. 이때 다음 조건을 만족해야 한다.

• $e_1 - s_1 = e_2 - s_2$.
• 1 \le s_1 < e_1 < s_2 < e_2 \le N.

주어진 연산을 이용하여 문제의 순서를 완전히 뒤집을 수 있는지 판정하고, 가능하다면 그 과정을 출력하라.

입력은 다음과 같은 형식으로 주어진다.

$N$

• $8 \le N \le 100\ 000$.

만약 문제의 순서를 완전히 뒤집을 수 없다면 첫째 줄에 -1을 출력한다.

그렇지 않다면 첫째 줄에 담유가 수행한 연산의 횟수 $Q$를 출력한다.

둘째 줄부터 $Q$개의 줄에 걸쳐 그 중 $i$번째 줄에 $i$번째 연산을 나타내는 네 정수 $s_1, e_1, s_2, e_2$​를 공백으로 구분하여 출력한다.

1. (10점)

모든 테스트 케이스에서 $N \leq 1000$이다.

모든 테스트 케이스에서 $Q$의 최댓값을 $M$이라 하자.

• $M \leq 1000$이면 $10$점을 얻는다.
• 그렇지 않으면 $0$점을 얻는다.
• 만약 문제의 순서를 완전히 뒤집을 수 없으나 -1을 출력하지 않은 경우, 또는 그 반대의 경우에는 $0$점을 받는다.

2. (90점)

추가적인 제약 조건이 없다.

모든 테스트 케이스에서 $Q$의 최댓값을 $M$이라 하자. 점수는 다음과 같다.

만약 문제의 순서를 완전히 뒤집을 수 없으나 -1을 출력하지 않은 경우, 또는 그 반대의 경우에는 $0$점을 받는다.