ARMIES - Armies

Two enemy countries - Bajtocja and Megabajtolandia - are preparing for crucial war with each other. Each country has built an army consisting of some number of divisions, and each division consists of some number of soldiers. The way of waging the war, given by strategists from each country, consists of sending the division with the most man power to fight, i.e. starting from the most numerous division to the least.

Thus, first each country will send its division with the most man power. If one of these divisions has more soldiers than the other, then the war is over and the winner is the owner of the larger division. If the man power of each of the divisions sent is the same then all the soldiers will kill each other and the next most numerous division is sent to fight. The man powers of the second divisions decide the war if and only if they are not the same. If not, the battle is carried on in aforementioned way. If, at some moment, one army runs out of divisions and the second one does not, then the war is over and the first army is the loser. If both armies run out of divisions then the war is over and there is a draw.

Give the result of the war, without any blood and murder.

Write a program, which:

  • reads from standard input the description of Bajtocja's and Megabajtolandia's army, respectively,
  • computes the result of the war,
  • writes it to standard output.

Input

The first line of input contains one integer D (1<=D<=30) meaning the number of test cases. The description of each test case contains 4 lines. In the first, there is one integer B (1 <= B <= 50 000) meaning the number of divisions in Bajtocja's army. The second line contains B integers bi (1 <= bi <= 1 000 000 000) (separated by single space) meaning the man power (the number of soldiers) of consecutive divisions of Megabajtolandia's army. In the third line, there is one integer M (1 <= M <= 50 000) meaning the number of divisions of Megabajtolandia's army. The fourth line contains M integers mi (1 <= mi < = 1 000 000 000) (separated by single space) meaning the man power of consecutive divisions of Megabajtolandia's army.

Output

For each test case, your program should write, in separate lines, exactly one word:

  • "Bajtocja" in case the winner is Bajtocja,
  • "Megabajtolandia" in case the winner is Megabajtolandia,
  • "Draw" in case of a draw.

Example

Sample input:
3
3
1 3 4
3
4 4 1
4
2 5 3 4
3
5 6 4
4
6 1 2 5
4
5 2 6 1

Sample output:
Megabajtolandia
Megabajtolandia
Draw

Added by:Rafal Nowak
Date:2005-02-07
Time limit:1s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:Winter sparing in Poznan, Poznan 2005 (22th January)

hide comments
2020-04-24 00:22:38
.17 sec python3
2015-10-09 15:06:01
getting wrong answer inspite of it working on ideone ( PyPy )... any clues ?
2013-02-10 06:26:38 Neelmay Desai
no, amandeep
the Megabajtolandia army has a division wit more man power (i.e. 6) soo they win...
got the catch ?
2011-11-13 16:13:38 Amndeep
Looked at some forum posts, I've realized that the problem is just looking for a comparison based upon the total number of soldiers, not what the problem stated.
2011-11-13 15:59:52 Amndeep
Also, if the samples are based on each other, the last line should be Bajtocja.
2011-11-13 15:30:45 Amndeep
If I'm not mistaken, the second line should be for Bajtocja's army.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.