LaLa와 마법진 (LiLi 버전)

이 문제는 출력 전용 문제다.

LaLa의 연구실에는 마법진 더미가 있다.

마법진은 특수한 잉크로 그린 단순 다각형으로 나타낼 수 있으며, 볼록하면 사용 가능하다. 즉 모든 내부 각이 $\pi$ 이하이면 사용 가능하다.

LaLa는 모든 마법진을 사용 가능한 상태로 바꾸려 한다. 하지만 잘못 다루면 마법의 힘을 모두 잃을 수 있다. 다행히 LaLa에게는 이를 위한 완벽한 마법 도구가 있다.

도구는 다음과 같이 동작한다. 마법진을 넣었을 때 사용 가능하면 도구는 그렇다고 알려 준다. 그렇지 않으면 다음 두 조건을 만족하는 서로 다른 두 점 $u$, $v$를 고른다.

• $u$와 $v$는 마법진의 볼록 껍질 경계 위에 있다.
• 마법진의 경계를 따라 반시계 방향으로 $u$에서 $v$까지 가는 경로에서, $u$와 $v$를 제외한 어떤 점도 볼록 껍질 경계 위에 있지 않다.

그다음 도구는 $u$-$v$ 경로를 $u$와 $v$의 중점을 중심으로 $\pi$만큼 회전시킨다. 즉 $u$-$v$ 경로 위의 각 점 $w$는 $u+v-w$가 된다. 여기서 덧셈은 마법진이 그려진 종이의 2차원 좌표계에서 좌표별로 한다. 이 수정 결과도 단순 다각형이라는 점에 유의하라.

LaLa는 전혀 모르고 있지만, 여동생 LiLi가 이 계획을 엿들었다. LaLa가 얼마나 게으른지 아는 LiLi는 장난으로, 사용 가능하게 만드는 데 도구를 아주 많이 써야 하는 마법진을 몰래 넣으려 한다. 구체적으로 LiLi는 높이 $1\,000$개 이하의 선분으로 이루어진 마법진을 더미에 넣는다. 그리고 도구는 $120\,000$단계 이상 $1\,000\,000$단계 이하의 수정 순서를 수행해 이 마법진을 사용 가능한 마법진으로 만들 수 있다.

LiLi가 그런 마법진을 하나 계산하도록 돕는 프로그램을 작성하라.

출력은 다음 형식을 따라야 한다.

$N$

$x\_0$ $y\_0$

$x\_1$ $y\_1$

$\vdots$

$x\_{N-1}$ $y\_{N-1}$

$Q$

$a\_0$ $b\_0$ $c\_0$ $d\_0$

$a\_1$ $b\_1$ $c\_1$ $d\_1$

$\vdots$

$a\_{Q-1}$ $b\_{Q-1}$ $c\_{Q-1}$ $d\_{Q-1}$

여기서 초기 마법진은 모든 정수 $0 \le i < N$에 대해 점 $(x\_i, y\_i)$와 $(x\_{(i+1 \bmod N)}, y\_{(i+1 \bmod N)})$을 잇는 $N$개의 선분의 합이다. 길이가 $Q$인 도구 수정 순서가 있으며, $i$번째 수정은 점 $(a\_i, b\_i)$에서 $(c\_i, d\_i)$까지의 반시계 방향 경로를 선택한다.

출력은 다음 제약을 만족해야 한다.

• 출력의 모든 수는 정수이다.
• $3 \le N \le 1\,000$
• $120\,000 \le Q \le 1\,000\,000$
• 모든 정수 $0 \le i < N$과 $0 \le j < Q$에 대해 $0 \le x\_i, y\_i, a\_j, b\_j, c\_j, d\_j \le 1\,000\,000\,000$이다.
• 모든 정수 $0 \le i < j < N$에 대해 $x\_i \ne x\_j$ 또는 $y\_i \ne y\_j$이다.
• 모든 정수 $0 \le i < Q$에 대해 $a\_i \ne c\_i$ 또는 $b\_i \ne d\_i$이다.
• 점열 $(x\_0, y\_0), (x\_1, y\_1), \ldots, (x\_{N-1}, y\_{N-1})$은 단순 다각형의 경계를 반시계 방향으로 한 바퀴 도는 순서이다.
• 처음 $i$번 수정을 마친 뒤 점 $(a\_i, b\_i)$에서 $(c\_i, d\_i)$까지의 반시계 방향 경로를 선택하는 것은 모든 정수 $0 \le i < Q$에 대해 유효하다.
• 최종 마법진은 사용 가능하다.

두 연속된 선분이 각 $\pi$로 만나는 것은 허용된다. 또한 어떤 수도 최소화할 필요는 없으며, 프로그램은 출력 제약만 만족하면 된다.

다음 그림은 초기 마법진을 보여 준다.

다음 그림은 마법진을 사용 가능하게 만드는 도구 사용 순서를 보여 준다. 경계의 점선 부분은 도구가 수정하는 경로이며, 수정 후에는 빨간 부분이 된다.

Step 0	Step 1
Step 2	Step 3
Step 4