Practice on Toph

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

Alice vs. Bob

By Sherlock221b · Limits 1s, 512 MB

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 A1,A2,A3,,AnA_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

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, A1,A2,A3,,AnA_1, A_2, A_3,…, A_n.

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

Constraints
1 <= N, Q <=
10510^5
|Ai| <=
10910^9
1 <= P, K <= N

Output

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.)

Sample

InputOutput
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.

    Discussion

    Statistics


    50% Solution Ratio

    Mehedi_HassanEarliest, 5M ago

    pathanFastest, 0.0s

    Deshi_TouristLightest, 6.3 MB

    BerlekampMassyShortest, 944B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.