다각형의 위치와 절단

$N$개의 꼭짓점이 둘레를 따라 순서대로 주어진 다각형과 볼록함을 보장하는지 나타내는 정수 $C$가 주어진다. $C=1$이면 다각형이 볼록하고, $C=0$이면 볼록함을 보장하지 않는다.

다음 $Q$개의 질의를 처리해 보자.

• $\texttt{P}\ x\ y$: 점 $(x,y)$가 다각형의 내부, 경계, 외부 중 어디에 있는지 판별한다.
• $\texttt{G}$: 다각형의 면적 중심을 구한다.
• $\texttt{C}\ a_x\ a_y\ b_x\ b_y$: $A=(a_x,a_y)$에서 $B=(b_x,b_y)$로 향하는 직선의 왼쪽 닫힌 반평면과 다각형의 교집합의 넓이 및 면적 중심을 구한다.

면적 중심은 질량이 균일하게 분포한다고 가정했을 때의 무게중심이다. 빈 도형, 점, 선분에는 면적 중심이 없다. 각 질의는 처음 다각형을 기준으로 독립적으로 처리한다.

첫 번째 줄에 정수 $N$, $Q$, $C$가 공백으로 구분되어 주어진다. $(0\le N\le2\,000; 1\le Q\le2\,000; C\in\{0,1\})$

두 번째 줄부터 $N$개의 줄에 걸쳐 각 꼭짓점의 정수 좌표 $x$, $y$가 공백으로 구분되어 주어진다. $(\lvert x\rvert\le10^6; \lvert y\rvert\le10^6)$ 꼭짓점은 모두 서로 다르며, 마지막에 첫 번째 꼭짓점을 중복해서 주지 않는다. 시계 방향과 반시계 방향 모두 가능하다. $N\ge3$이면 넓이가 양수인 단순다각형이다.

그다음 줄부터 $Q$개의 줄에 걸쳐 질의가 다음 형식 중 하나로 주어진다.

• 문자 P와 정수 $x$, $y$가 공백으로 구분되어 주어진다. $(\lvert x\rvert\le10^6; \lvert y\rvert\le10^6)$
• 문자 G가 주어진다.
• 문자 C와 정수 $a_x$, $a_y$, $b_x$, $b_y$가 공백으로 구분되어 주어진다. $(-10^6\le a_x,a_y,b_x,b_y\le10^6)$

절단 질의는 $C=1$이고 $A\ne B$일 때만 주어진다.

P 질의는 점이 다각형의 밖에 있으면 $-1$을, 경계에 있으면 $0$을, 안에 있으면 $1$을 한 줄에 출력한다.

G 질의는 면적 중심이 없으면 $0$을 한 줄에 출력한다. 면적 중심이 있으면 $1$과 중심의 좌표 $x$, $y$를 공백으로 구분하여 한 줄에 출력한다.

C 질의는 절단 결과의 넓이를 먼저 출력한 뒤, 같은 줄에 G 질의와 같은 형식으로 면적 중심을 공백으로 구분하여 출력한다.

각 실수는 절대 오차가 $10^{-6}$ 이하이거나 상대 오차가 $10^{-8}$ 이하이면 정답으로 인정한다.