Convex Polygon
Description
Consider a convex polygon. Let $(i, j)$-segment be the line segment connecting the $i$-th and $j$-th vertices. Let the double oriented chord area $(i, j)$ be twice the area of the shape bounded by the $(i, j)$-segment and the edges of the polygon going in counterclockwise order from the $i$-th vertex to the $j$-th one.
You are given a convex polygon and some queries of three types. The first query type requires removing the specified vertex from the polygon. The second type requires restoring a vertex that was removed earlier. Finally, the third query type requires calculating the double oriented chord area with given $i$ and $j$. Your task is to process the given queries.
The first line of the input contains the only integer $n$ ($3 \le n \le 100\,000$). The next $n$ lines contain two integers: the coordinates of the vertices (ranging from $-10^9$ to $10^9$). It is guaranteed that the given polygon is non-degenerate and strictly convex (that is, the polygon is convex and no three of its vertices lie on the same line). The vertices are enumerated in counterclockwise order.
The description of the polygon is followed by an integer $q$, the number of queries ($1 \le q \le 100\,000$). The next $q$ lines contain one query each.
Each query starts with one of the following characters: '-", +", or ?". The character -" is followed by a vertex number and means that the respective vertex should be removed. The character +" is followed by a vertex number and means that the respective vertex should be restored. The character '?" is followed by two integers $i$ and $j$ and means that you have to calculate the double oriented chord area $(i, j)$.
It is guaranteed that for the first two types of queries, no query will ask to restore a vertex that is not currently removed, and no query will ask to remove a vertex that is not currently present. For the third type, $i$ and $j$ will never coincide and will both be present at the time of the query. It is also guaranteed that the polygon will never have less than three vertices.
For each "?" query, output a single integer: the requested double oriented chord area. One can easily prove that these numbers are always integers.
Input
The first line of the input contains the only integer $n$ ($3 \le n \le 100\,000$). The next $n$ lines contain two integers: the coordinates of the vertices (ranging from $-10^9$ to $10^9$). It is guaranteed that the given polygon is non-degenerate and strictly convex (that is, the polygon is convex and no three of its vertices lie on the same line). The vertices are enumerated in counterclockwise order.
The description of the polygon is followed by an integer $q$, the number of queries ($1 \le q \le 100\,000$). The next $q$ lines contain one query each.
Each query starts with one of the following characters: '-", +", or ?". The character -" is followed by a vertex number and means that the respective vertex should be removed. The character +" is followed by a vertex number and means that the respective vertex should be restored. The character '?" is followed by two integers $i$ and $j$ and means that you have to calculate the double oriented chord area $(i, j)$.
It is guaranteed that for the first two types of queries, no query will ask to restore a vertex that is not currently removed, and no query will ask to remove a vertex that is not currently present. For the third type, $i$ and $j$ will never coincide and will both be present at the time of the query. It is also guaranteed that the polygon will never have less than three vertices.
Output
For each "?" query, output a single integer: the requested double oriented chord area. One can easily prove that these numbers are always integers.
6
-2 -3
2 -3
4 0
2 3
-2 3
-4 0
8
? 1 2
? 2 6
- 4
? 2 6
- 3
? 2 6
+ 4
? 2 6
0
60
48
24
48
Note
Below are the states of the polygon at the time of each of the "?" queries.
    |