[Solution] Letter Picking Codeforces Solution

D. Letter Picking

time limit per test

2 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

Alice and Bob are playing a game. Initially, they are given a non-empty string 𝑠$s$, consisting of lowercase Latin letters. The length of the string is even. Each player also has a string of their own, initially empty.

Alice starts, then they alternate moves. In one move, a player takes either the first or the last letter of the string 𝑠$s$, removes it from 𝑠$s$ and prepends (adds to the beginning) it to their own string.

The game ends when the string 𝑠$s$ becomes empty. The winner is the player with a lexicographically smaller string. If the players' strings are equal, then it's a draw.

A string 𝑎$a$ is lexicographically smaller than a string 𝑏$b$ if there exists such position 𝑖$i$ that 𝑎𝑗=𝑏𝑗$a_j=b_j$ for all 𝑗<𝑖$j<i$ and 𝑎𝑖<𝑏𝑖$a_i<b_i$.

What is the result of the game if both players play optimally (e. g. both players try to win; if they can't, then try to draw)?

Input

The first line contains a single integer 𝑡$t$ (1≤𝑡≤1000$1\le t\le 1000$) — the number of testcases.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

Each testcase consists of a single line — a non-empty string 𝑠$s$, consisting of lowercase Latin letters. The length of the string 𝑠$s$ is even.

The total length of the strings over all testcases doesn't exceed 2000$2000$.

Output

For each testcase, print the result of the game if both players play optimally. If Alice wins, print "Alice". If Bob wins, print "Bob". If it's a draw, print "Draw".