J. Pawn Game
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Alice and Bob play a game on $$$N$$$ squares numbered from $$$1$$$ to $$$N$$$ from left to right. The squares can either be empty or have a pawn. Initially, there are $$$M$$$ pawns, each having a position and a color. Two pawns cannot have the same position at any given time.

The game is played by taking turns and Alice is the first one to move. A player's turn consists of choosing a pawn with at least one empty square to the left. The player can move this pawn to the left any strictly positive number of squares, but it cannot move over or to the position of another pawn. Also, a pawn cannot go over square $$$1$$$, since square $$$1$$$ has no other squares to the left.

After a pawn of color $$$C$$$ is moved by $$$X$$$ squares to the left, all the pawns to the right of the moved pawn until the next pawn of color $$$C$$$ (or all the pawns to the right if there are no more pawns of color $$$C$$$) will move $$$X$$$ squares to the left as well.

A player will lose if there are no more valid moves at the turn (there are no pawns with at least one empty square to the left). It is assumed that both players play optimally.

Let's provide an example of a player turn. We have the following configuration of $$$17$$$ squares where a number represents a pawn of that color:

$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$1$$$

If the pawn at square $$$3$$$ is moved by $$$1$$$ square, it will result in the following configuration:

$$$ \ $$$$$$2$$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$1$$$

You are given $$$Q$$$ queries of two types:

  • Add a pawn to the position $$$pos$$$ of color $$$col$$$.
  • Remove a pawn from position $$$pos$$$.

After each query, you should print the name of the player that will win with the newly created configuration.

Input

The first line of input will contain two integers $$$N$$$ ($$$1\leq N \leq 10^9$$$), $$$M$$$ ($$$1\leq M \leq 10^5$$$) representing the number of squares and pawns.

The next $$$M$$$ lines will each contain a pair of integers $$$pos$$$ ($$$1\leq pos \leq N$$$) and $$$col$$$ ($$$1\leq col \leq 5$$$) which means that there is a pawn of color $$$col$$$ at position $$$pos$$$.

The next line will contain $$$Q$$$ ($$$1\leq Q \leq 10^5$$$), the number of queries

The next $$$Q$$$ lines will each contain a query:

  • $$$1 $$$ $$$pos $$$ $$$col$$$, meaning that a pawn of color $$$col$$$ is added at position $$$pos$$$. It is guaranteed that there are no pawns at position $$$pos$$$. ($$$1\leq pos \leq N$$$, $$$1\leq col \leq 5$$$)
  • $$$2 $$$ $$$pos$$$, meaning that the pawn at position $$$pos$$$ is removed. It is guaranteed that there is a pawn at position $$$pos$$$. ($$$1\leq pos \leq N$$$)
Output

The output should contain $$$Q$$$ lines. On line $$$i$$$, print out the answer corresponding to query $$$i$$$.

Example
Input
30 6
3 1
6 2
11 3
14 2
17 3
27 1
4
1 24 1
2 24
1 23 1
1 29 2
Output
Bob
Alice
Alice
Bob
Note

Initial configuration:

$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$

After query $$$1$$$:

$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$

After query $$$2$$$:

$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$

After query $$$3$$$:

$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$

After query $$$4$$$:

$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$2$$$$$$ \ $$$$$$ \ $$$$$$3$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$ \ $$$$$$ \ $$$$$$1$$$$$$ \ $$$$$$2$$$$$$ \ $$$