Master of Both V

Prof. Chen is the master of data structures and computational geometry. Recently, he taught Putata and Budada the definition of a convex polygon. A convex polygon is a simple polygon (that is, no two vertices coincide, and no two edges intersect unless two consecutive edges meet at a vertex) whose interior angles are all strictly less than $\pi$.

Putata and Budada solved the convex checker problem. Prof. Chen then asked them to go further: maintain a multiset of segments $S$ that supports two types of queries.

• $+$ $px$ $py$ $qx$ $qy$: insert the segment with endpoints $(px,py)$ and $(qx,qy)$ into the multiset $S$.
• $-$ $i$: erase the segment inserted by the $i$-th query. It is guaranteed that the $i$-th query is an insertion and that its segment is currently in the multiset.

After each query, answer whether there exists a convex polygon $\mathcal{C}$ with vertices $p_0,p_1,p_2,\dots,p_{m-1}$ in counterclockwise order such that for every segment $u\in S$, there is some $j\in\{0,1,\dots,m-1\}$ with $u\subseteq p_jp_{(j+1)\bmod m}$. For two segments $e,f$, $e\subseteq f$ holds if and only if every point $z\in e$ also lies in $f$.

The first line contains a single integer $t$ ($1 \le t \le 5 \cdot 10^5$), the number of test cases.

Each test case starts with a line containing an integer $n$ ($1\le n\le 5\cdot 10^5$), the number of queries. Each of the following $n$ lines contains one query. A query begins with a character $op$ ($op\in\{+,-\}$).

If $op=+$, four integers $px, py, qx, qy$ ($-10^9\le px,py,qx,qy\le 10^9$) follow. It is guaranteed that $px\neq qx$ or $py \neq qy$.

Otherwise, an integer $i$ ($1\le i\le n$) follows. It is guaranteed that the $i$-th query is an insertion and that its segment is currently in the multiset.

The sum of $n$ over all test cases does not exceed $5\cdot 10^5$.

For each test case, print a string of '0' and '1' on one line. The $i$-th character is '1' if the answer is true after the $i$-th query, and '0' otherwise.