Alice and Bob's One‐Dimensional Chess Game

Alice and Bob play a game on a 1×N board. Initially, there are M chess pieces placed on distinct cells; each piece has a color. The game is played in turns with Alice moving first. In every turn a player can choose any chess piece and move it to the left by a positive number of cells subject to the following rule:

If the chosen piece is located at position (p_i), then along with this piece the player also moves all of the pieces immediately to its right that have a color different from the chosen piece – that is, all pieces up to (but not including) the first piece with the same color as the chosen one. During the move the entire block must shift left by (d (d\ge1)) cells, and the block cannot jump over or overlap the cell immediately to the left of it (i.e. the block can move at most as many cells as there are consecutive empty cells immediately before the block).

Formally, if the chosen piece is the first piece in a contiguous block of moved pieces and if the cell immediately to its left is either the board boundary (cell 0) or is occupied by a chess piece that is not moved, then the maximum distance allowed is [ d\le p_i - (p_{i-1} + 1) \quad (\text{with } p_0 \equiv 0), ] where (p_i) is the position of the chosen piece and (p_{i-1}) is the position of the chess piece immediately to its left (if any). Note that when a block is moved, only the left gap (the number of empty cells immediately before the block) can be reduced; the relative distances among the pieces within the block remain unchanged.

It can be shown that the game is equivalent to an impartial game whose outcome is determined by certain "nim-values". In particular, if we sort the pieces in increasing order of position (p_1, p_2, \ldots, p_k) and define a piece to be an independent move (or a chain leader) if it is either the leftmost piece or if its color is the same as the piece immediately to its left, then its nim value is defined as follows:

• For the first (leftmost) piece: (G = p_1 - 1).
• For any independent piece (p_i) (with (i>1)): (G = p_i - p_{i-1} - 1).

The overall nim sum is the XOR of the nim values of all independent pieces. Alice wins if and only if the nim sum is nonzero; otherwise Bob wins.

In addition, there are Q operations. Each operation is one of the two types:

1. “1 pos col”: Place a new chess piece of color col at position pos (guaranteed to be empty).
2. “2 pos”: Remove the chess piece from position pos (guaranteed to exist).

After each operation, determine the winner of the game under optimal play.

Note: All formulas must be written in (\LaTeX) format. The sample input and output below follow the input/output specifications.

inputFormat

The first line contains three integers (N), (M), and (Q) ( (1 \le N \le 10^9,\ 0 \le M \le N,\ 1 \le Q \le 10^5)) representing the board length, the initial number of chess pieces, and the number of operations, respectively.

The next (M) lines each contain an integer (pos) and a string (or integer) (col) representing the initial position and the color of a chess piece. It is guaranteed that all initial positions are distinct and lie in the range ([1, N]).

Each of the following (Q) lines describes an operation in one of the following two formats:

1. For insertion: 1 pos col
2. For deletion: 2 pos

It is guaranteed that in an insertion operation the cell (pos) is empty, and in a deletion operation there is a chess piece at cell (pos).

outputFormat

For each of the (Q) operations, output a single line containing either “Alice” if the current position is winning for Alice or “Bob” otherwise.

sample

10 2 6
1 1
5 2
1 3 1
2 1
1 2 2
2 3
2 2
2 5

Alice
Alice
Alice
Alice
Alice
Bob

</p>