Mahjong Tactics: The Quest for Four Concealed Triplets

Alice and Bob love playing mahjong. After mastering the rules, they became fascinated with the "\(\text{四暗刻单骑}\)" (Four Concealed Triplets with a Single Wait) hand. In this simplified game:

• A mahjong tile is represented by a positive integer in the range \( [1,k] \). Tiles with the same number are identical.
• Alice and Bob each start with one tile in hand, given as \(x\) and \(y\) respectively.
• They take turns drawing tiles from a deck. The deck is a sequence of \(n\) tiles given by an array \(a\). For each query the deck is the subarray \(a_l, a_{l+1}, \dots, a_r\) (with \(a_l\) on top). Alice draws first.
• On a turn, the current player draws the top tile. Let the drawn tile be \(d\). Immediately after drawing, if the two tiles in hand are equal (i.e. if the current hand tile equals \(d\)), then the player wins immediately.
• If not, the player must discard one of the two tiles. The discard is public. After discarding, the player keeps the other tile in hand.
• As soon as a player discards a tile \(p\), the opponent checks: if the opponent's current hand equals \(p\), then the opponent wins immediately.
• If no one wins by the time the deck is exhausted, the game is declared a draw.

Both Alice and Bob are supremely intelligent. They know the full order of the deck and the opponent's initial tile and will play optimally: each aims to win if possible; if not, they choose moves that delay or prevent the opponent’s win.

Given the deck \(a\) of \(n\) tiles and \(m\) queries, each query provides integers \(x, y, l, r\): if Alice's initial hand is \(x\), Bob's is \(y\), and the game deck is the subarray \(a_l, a_{l+1}, \dots, a_r\) (\(a_l\) is at the top, and it is guaranteed that \(l\) is odd), determine the outcome of the game: does Alice win, Bob win, or is it a draw?

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(k\) where \(n\) is the number of tiles in array \(a\), \(m\) is the number of queries, and \(k\) is the maximum tile number (tiles are in the range \([1,k]\)).

The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the deck of tiles.

Each of the following \(m\) lines contains four integers \(x\), \(y\), \(l\), and \(r\) representing a query: Alice's initial tile \(x\), Bob's initial tile \(y\), and the subarray indices \([l,r]\) (1-indexed) that form the game deck (with \(a_l\) as the top tile). It is guaranteed that \(l\) is odd.

outputFormat

For each query, output a single line:

• Alice if Alice can force a win,
• Bob if Bob can force a win, or
• Draw if neither can force a win (i.e. if the game ends in a draw).

sample

6 3 3
2 1 2 1 2 3
1 2 1 4
2 2 1 4
1 1 3 6

Alice
Alice
Bob