Subsequence Game

Two players, Alice and Bob, play a game using two integer arrays, \(a\) and \(b\). The array \(a\) has length \(N\) and array \(b\) has length \(M\); all numbers are in the range \([1,k]\). In addition, an initially empty array \(c\) is maintained.

The game is played as follows. Players take turns appending a number to the end of \(c\) with the restriction that \(c\) must remain a subsequence of both \(a\) and \(b\) after the move. If a player cannot make a move, they lose. Alice always goes first and both players play optimally.

The game is played for \(q\) rounds. In the \(i\)th round, two numbers \(x_i\) and \(y_i\) are chosen (with \(0 \le x_i < N\) and \(0 \le y_i < M\)). Then the first \(x_i\) elements are removed from \(a\) and the first \(y_i\) elements are removed from \(b\). It is guaranteed that after deletion, the remaining parts of \(a\) and \(b\) start with the same value. The game is played on these remaining portions, and the array \(c\) is cleared before each round. Note that the arrays \(a\) and \(b\) are restored to their initial state after each round.

Your task is to determine for each round whether Alice can force a win.

Input arrays in compressed form: Instead of listing all elements, each array is given as a sequence of segments. In array \(a\), there are \(n\) segments and in array \(b\) there are \(m\) segments. Each segment is specified by its length and the value (which appears repeatedly in that segment).

Game interpretation: Let \(dp(i,j)\) be true if the current player can force a win starting from state \((i,j)\), where \(i\) and \(j\) denote the current starting indices in arrays \(a\) and \(b\) respectively. If no valid move exists from the current state the player loses. A move consists of selecting a digit \(d\) (in the range \([1,k]\)) such that there exists an occurrence of \(d\) in \(a\) at an index \(p \ge i\) and in \(b\) at an index \(q \ge j\). After choosing \(d\), the state becomes \((p+1, q+1)\) and the game continues. Determine whether the starting state for each query is winning for Alice.

Note: The arrays can be very long, so they are input in a compressed segment format.

inputFormat

The input is given as follows:

N M k
n
L1 v1
L2 v2
... 
Ln vn
m
L1' v1'
L2' v2'
... 
Lm' vm'
q
x1 y1
x2 y2
...
 xq yq

Here, the first line contains three integers: \(N\) and \(M\) (the lengths of arrays \(a\) and \(b\)) and \(k\) (the maximum value in the arrays). Then, the integer \(n\) indicates the number of segments in array \(a\), followed by \(n\) lines each containing two integers: the segment length and the repeated value. Similarly, \(m\) indicates the number of segments in array \(b\), followed by \(m\) lines of segments. Finally, \(q\) denotes the number of rounds. For each round, two integers \(x_i\) and \(y_i\) are given (with \(0 \le x_i < N\) and \(0 \le y_i < M\)). It is guaranteed that for each query the remaining parts of \(a\) and \(b\) (starting at indices \(x_i\) and \(y_i\) respectively) start with the same value.

outputFormat

For each of the \(q\) rounds, output a single line. Print Alice if Alice can force a win with optimal play from that round’s starting position, or Bob otherwise.

sample

5 5 3
2
3 1
2 2
2
2 1
3 3
3
0 0
1 1
2 0

Bob
Alice
Alice