L. Master of Both V
time limit per test
5 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

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:

  • "+ $$$\mathit{px}$$$ $$$\mathit{py}$$$ $$$\mathit{qx}$$$ $$$\mathit{qy}$$$": insert a segment with endpoints $$$(\mathit{px}, \mathit{py})$$$ and $$$(\mathit{qx}, \mathit{qy})$$$ into the multiset $$$S$$$.
  • "- $$$i$$$", erase the segment inserted in the $$$i$$$-th query. It is guaranteed that the $$$i$$$-th query is an insertion query, and the corresponding segment is currently in the multiset.

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.

Input

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$$$.

Output

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.

Example
Input
4
8
+ 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
- 2
5
+ 0 0 1 1
+ 0 1 1 2
+ 0 2 1 3
- 2
+ 1 1 10 10
4
+ 0 0 1 1
+ 0 0 1 0
+ 0 0 0 1
- 1
4
+ 0 0 1 1
+ 0 0 1 1
- 1
- 2
Output
11000001
11011
1101
1111