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 intersect at a vertex) with all interior angles strictly less than $$$\pi$$$.
Putata and Budada solved the convex checker problem. But Prof. Chen asked them to go further. Now, they have to maintain a multiset of segments $$$S$$$, initially empty, and support the following two types of queries:
After each query, Putata and Budada need to answer if there exists a convex polygon $$$\mathcal{C}$$$ with the following property. Let the vertices of the convex polygon be $$$p_0, p_1, p_2, \ldots, p_{m - 1}$$$ in counter-clockwise order. For every segment $$$u \in S$$$, there exists an integer $$$j \in \{0, 1, 2, \ldots, m - 1\}$$$ such that $$$u \subseteq p_{j} p_{(j + 1) \bmod m}$$$. For two segments $$$e$$$ and $$$f$$$, we say $$$e \subseteq f$$$ if and only if, for every point $$$z \in e$$$, this point $$$z \in f$$$.
Please help Putata and Budada to solve this problem.
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^5$$$) denoting the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) denoting the number of queries.
Each of the following $$$n$$$ lines contains one query. The query begins with a character $$$op$$$ ($$$op\in\{+,-\}$$$).
If $$$\mathit{op} = \texttt{+}$$$, then four integers $$$\mathit{px}$$$, $$$\mathit{py}$$$, $$$\mathit{qx}$$$, and $$$\mathit{qy}$$$ ($$$-10^9 \leq \mathit{px}, \mathit{py}, \mathit{qx}, \mathit{qy} \leq 10^9$$$) follow, denoting an inserting query. It is guaranteed that $$$\mathit{px} \neq \mathit{qx}$$$ or $$$\mathit{py} \neq \mathit{qy}$$$.
Otherwise, an integer $$$i$$$ ($$$1 \leq i \leq n$$$) follows, denoting an erasing query. It is guaranteed that the $$$i$$$-th query is an inserting query, and the corresponding segment is currently in the multiset.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, print a line consisting of 0s and 1s. The $$$i$$$-th character must be 1 if the answer is true after the $$$i$$$-th query, otherwise it must be 0.
48+ 0 0 1 0+ 5 5 1 3+ 2 0 2 1+ 9 7 6 2+ 1 2 2 2- 4+ 0 1 0 2- 25+ 0 0 1 1+ 0 1 1 2+ 0 2 1 3- 2+ 1 1 10 104+ 0 0 1 1+ 0 0 1 0+ 0 0 0 1- 14+ 0 0 1 1+ 0 0 1 1- 1- 2
11000001 11011 1101 1111
