B - Board Game

Time limit: 3 s
Memory limit: 1024 MiB
Languages: C, C++, Java, Python, ... (details)

Alice and Bob decide to try a new board game. The game has a board of dimensions $n \cdot m$, $c$ coins located in specific cells on the board and an integer $r$ ($1 \le r \le m$), chosen by Alice and Bob at the beginning of each match.

The board game is a turn-based game, and courtesy of Bob, Alice is the first player in every match. On its turn, the player must choose a coin located in a cell $(i, j)$ such that $(1 \le i \le n, 1 \le j \le r)$ and move it to another cell $(i, k)$ of the same row of the board that is to the left of $(i, j)$, it does not matter if this new cell already contains another coin. The player who cannot make a move loses.

Alice and Bob decide to play $q$ matches, it is wanted to determine the winner of each match, knowing that both players play optimally.


First line contains four integers $n$, $m$, $c$ and $q$ $(1 \leq n , m, c, q \leq 10^5)$, which represent the dimensions of the board, the number of coins and number of matches, respectively.

Next $c$ lines contain two integers $x, y$ ($1 \leq x \leq n$, $1 \leq y \leq m$) each, the cell where the $i$-th coin is located.

The next $q$ lines contain an integer $r$ ($1 \leq r \leq m$), the integer chosen by Alice and Bob for each match.


For each of the $q$ matches, print the winner of the game, "Alice" or "Bob".

Sample test(s)

4 4 3 3 1 1 1 3 2 4 3 4 2
Alice Alice Bob