Lunch (OOI qualification)
Time limit: 2 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: data structures, geometry, game theory, linear algebra

# Lunch

| Input file:   | standard input  |
|---------------|-----------------|
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 512 megabytes   |

You are given a convex polygon with $N$ points. It is not guaranteed that no three points lie on the same line. There are $M$ different special points inside the polygon. Additionally, a point $C$ is given with coordinates $(x_0, y_0)$, which lies inside the convex polygon but not on its boundary.

Alice and Bob play a game, taking turns starting with Alice. On each turn, a player must choose a vertex of the polygon different from $C$ and move it to point $C$. If there is already a vertex at point $C$ in the polygon, these vertices are merged. A move can only be made if there is a special point that lies inside the polygon before the move, but not in it afterwards. It is guaranteed that the point can never be on the boundary of the polygon after any number of moves.

After a move, the polygon is not required to be convex and can also become degenerate (i.e., become a segment). The game ends when a player cannot make a move.

There are also $q$ changes of two types:

- + $x$ $y$, which means that the point with coordinates $(x, y)$ becomes special. It is guaranteed that this point was not special before.
- - $x$ $y$, which means that the point with coordinates $(x, y)$ stops being special. It is guaranteed that this point was special before.

After each modification, as well as at the beginning, determine which player should win if both of them play optimally. After each modification, the game starts with the initial polygon, taking into account the applied modifications to the special points.

## Input

The first line contains three integers $n$, $m$ and $q$ ($3 \le n \le 10000$, $0 \le m \le 100000$, $0 \le q \le 1000000$) the number of points in the polygon, the number of special points and the number of changes.

The second line contains two integers $x_0$ and $y_0$ ($-10^9 \le x_0, y_0 \le 10^9$) — coordinates of the point $C$. It is guaranteed that the point lies inside the given polygon and does not lie on its border.

Each of the next $n$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) — coordinates of the $i$-th point of the polygon. The points are given in a counterclockwise order.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) — coordinates of the $i$-th special point. It is guaranteed that at any time the points are distinct and lie inside the polygon.

The following $q$ lines contain a description of the requests. The $i$-th of them contains the symbol $c$ and two integers $x$ and $y$ ($c$ = "+" or "-" (without quotes), $-10^9 \le x, y \le 10^9$) - description of the next request.

- If $c$ = "+", then the point $(x, y)$ becomes special. It is guaranteed that this point was not special before.
- If $c$ = "-", then the point $(x, y)$ ceases to be special. It is guaranteed that before that this point was special.

It is guaranteed that at any time after any number of correct moves, none of the singular points can be on the boundary of the polygon.

## Output

Print $q + 1$ lines. In the first line, print "Alice" (without quotes) if Alice wins before any modifications with optimal play, and "Bob" (without quotes) otherwise. Then, in the $i$-th line, print the winner of the game after the $(i - 1)$-th modification in a similar format.

## Example

| standard input | standard output |
|----------------|-----------------|
| 5 5 3          | Alice           |
| 0 3            | Bob             |
| -4 -2          | Bob             |
| 1 -4           | Bob             |
| 5 0            |                 |
| 1 4            |                 |
| -4 2           |                 |
| 0 -1           |                 |
| -2 -1          |                 |
| -1 0           |                 |
| 0 -3           |                 |
| -1 2           |                 |
| + 4 0          |                 |
| + -2 2         |                 |
| + 0 2          |                 |

## Note

Consider the polygon before any modifications:

![](_page_1_Figure_6.jpeg)

On the first move, Alice can move a vertex of the polygon with coordinates (-4, -2), then the polygon will look like this:

![](_page_2_Figure_0.jpeg)

In this state of the polygon, Bob cannot make a move anymore, and therefore loses.

## Scoring

The tests for this problem consist of 6 groups. Points for each group are awarded only if all the tests in that group and some tests from the previous groups pass. Offline-testing means that the results of testing your solution on this group will only be available after the competition ends.

| Group | Score | Additional constraints |   |   | Required groups | Comment          |
|-------|-------|------------------------|---|---|-----------------|------------------|
|       |       | $n$                    | $m$ | $q$ |                 |                  |
| 0     | 0     | –                      | – | – | –               | Samples.         |
| 1     | 16    | $n = 3$                | $m \le 3$ | $q = 0$ | –               |                  |
| 2     | 13    | $n \le 18$            | $m \le 18$ | $q \le 1$ | 1               |                  |
| 3     | 15    | $n \le 18$            | $m \le 18$ | – | 0 – 2           |                  |
| 4     | 17    | $n \le 5000$          | $m \le 5000$ | $q \le 1$ | 1, 2            |                  |
| 5     | 21    | $n \le 5000$          | $m \le 100000$ | $q \le 5000$ | 0 – 2, 4        |                  |
| 6     | 18    | –                      | – | – | 0 – 5           | Offline-testing. |

Starter code:

Grader code:

Setup script:

Evaluation script: