Master of Both V

Prof. Chen은 자료구조와 계산 기하학의 대가이다. 최근 그는 Putata와 Budada에게 볼록 다각형의 정의를 가르쳤다. 볼록 다각형은 단순 다각형(즉, 두 꼭짓점이 겹치지 않고, 연속된 두 변이 꼭짓점에서 만나는 경우를 제외하면 두 변이 교차하지 않는 다각형)이며, 모든 내각이 $\pi$보다 엄격히 작다.

Putata와 Budada는 볼록성 검사 문제를 풀었다. 이후 Prof. Chen은 그들에게 한 단계 더 나아가, 두 종류의 질의를 지원하는 선분 다중집합 $S$를 관리하라고 요청했다.

• $+$ $px$ $py$ $qx$ $qy$: 끝점이 $(px,py)$, $(qx,qy)$인 선분을 다중집합 $S$에 넣는다.
• $-$ $i$: $i$번째 질의에서 삽입한 선분을 $S$에서 뺀다. 보장: $i$번째 질의는 삽입 질의이고, 그 선분은 현재 다중집합에 들어 있다.

각 질의 후에, 꼭짓점이 반시계 방향 순서로 $p_0,p_1,p_2,\dots,p_{m-1}$인 볼록 다각형 $\mathcal{C}$가 존재하는지 답한다. 존재 조건은 $S$의 모든 선분 $u\in S$에 대해, $u\subseteq p_jp_{(j+1)\bmod m}$을 만족하는 $j\in\{0,1,\dots,m-1\}$가 있는 것이다. 두 선분 $e, f$에 대해 $e\subseteq f$는 $e$의 모든 점 $z$가 $f$에도 속한다는 뜻이다.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 5 \cdot 10^5$)가 주어진다.

각 테스트 케이스의 첫 줄에는 질의의 수 $n$ ($1\le n\le 5\cdot 10^5$)이 주어진다. 이어서 $n$개의 줄에 질의가 하나씩 주어진다. 질의는 연산 문자 $op$ ($op\in\{+,-\}$)로 시작한다.

$op=+$이면 정수 $px, py, qx, qy$ ($-10^9\le px,py,qx,qy\le 10^9$) 네 개가 주어진다. $px\neq qx$ 또는 $py \neq qy$가 보장된다.

그렇지 않으면 정수 $i$ ($1\le i\le n$)가 주어진다. $i$번째 질의는 삽입 질의이며, 그 선분은 현재 다중집합에 들어 있음이 보장된다.

모든 테스트 케이스의 $n$의 합은 $5\cdot 10^5$을 넘지 않는다.

각 테스트 케이스마다 '0'과 '1'로 이루어진 문자열을 한 줄에 출력한다. $i$번째 문자는 $i$번째 질의 후 답이 참이면 '1', 아니면 '0'이다.