Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

We have found an Idea to end the everlasting rivalry between Alice and Bob. We will give them a list of **N** numbers, denoted as $A_1, A_2, A_3,…, A_n$. And they play **Q** independent games.

In each game, we will give them two integers **P** and **K**. Then Alice makes the first move, she will take the first **K** number starting from **P'th** position of the list, then Bob will take the next **K** numbers starting from **(K+P)'th** position, then again Alice will take next **K** numbers starting from **(2K + P)'th** position and so on. They will keep playing alternatively until one of them takes the last number from the list.

Now, after a game ends, we will sum up all the numbers Alice had taken and also sum up all the numbers Bob had taken as well. Whoever has the greater sum, wins the game. A game is tied if both of them have an equal sum. So in this problem, you will help us find the result of each game.

Input starts with two integers, **N** and **Q** which are the number of integers in the given list and the number of games to be played respectively.

The next line will contain **N** integers, $A_1, A_2, A_3,…, A_n$.

Each of the next **Q** lines will contain two Integers **P** and **K**, which are described above.

**Constraints1 <= N, Q <=** $10^5$

|Ai| <=

1 <= P, K <= N

Print **Q** lines, name of the winner of each game which will be either "Alice" or "Bob", or print "Draw" if both of them have the same score. (Print without quotes, see the sample Input & Output for better understanding.)

Input | Output |
---|---|

5 3 1 4 3 5 2 2 4 1 2 3 1 | Alice Bob Draw |

**Explanation of sample case:****First game**: Alice starts from the 2nd number, she takes the 2nd, 3rd, 4th, and 5th number. So overall Alice’s score is 4 + 3 + 5 + 2 = 14 and Bob's score is 0, so Alice wins this game.**Second game**: Alice starts from the 1st number, she takes the 1st and 2nd number. Then, Bob starts from the 3rd number, he takes the 3rd and 4th number. Then, again Alice starts from the 5th number, she takes the 5th number. So overall Alice’s score is 1 + 4 + 2 = 7 and Bob’s score is 3 + 5 = 8, so Bob wins this game.

43% Solution Ratio

Mehedi_HassanEarliest,

BerlekampMassyFastest, 0.1s

BerlekampMassyLightest, 259 MB

BerlekampMassyShortest, 944B

Login to submit