Limits 1s, 512 MB

As all people know ICPC can be very dull sometimes for people other than contestants. Jodu, Modu, and Kodu visit the contest area and watch area. They are having fun. But after some time they became bored because contestants take so much time solving exceptionally hard problems. So they come up and started playing a game.

The game goes as follows,

  • Jodu and Modu will play against each other.

  • There will be an empty list with max capacity k\bf{k}.

  • There will be n\bf{n} rounds.

In each round:
Jodu guesses a number J\bf{J}
Modu guesses a number M\bf{M}

if M\bf{M} is smaller than J\bf{J}:

  1. M\bf{M} is added to Modu's score.

  2. Jodu will have to add the last element of the list to his score if it is smaller than J\bf{J}.

  3. After adding an element it must be removed.

  4. Jodu will have to do this until the list is empty or he cannot add any more.

  5. If the list is not full, then J\bf{J} is added to the last of the list.

else:

  1. J\bf{J} is added to Jodu's score.

  2. Modu will have to add the last element of the list to his score if it is smaller than M\bf{M}.

  3. After adding an element it must be removed.

  4. Jodu will have to do this until the list is empty or he cannot add any more.

  5. If the list is not full, then M\bf{M} is added to the last of the list.

Then the round ends.
The one having the more score will be in the lead.

Kodu have to track who is in the lead.

They have been playing for a long time. Keeping track manually Kodu got bored and started making mistakes.

Kodu has asked you to write him a program that will keep track of each round’s leading player, given J\bf{J} and M\bf{M} of each round.

Input

The first line will be an integer T\bf{T} indicating the number of test cases. Every test case starts with Two integers n\bf{n}and k\bf{k} denoting the number of rounds they are playing and the maximum capacity. The following n\bf{n} lines will contain two integers J\bf{J} and M\bf{M} separated by spaces.

1T1031 \le T \le 10^3

1n,k1051 \le n, k \le 10^5

1J,M1071 \le J, M \le 10^7

Output

For every test case, first print a line in the format  “Case X:” where XX is the number of test cases starting from 11. Next, You have to output n\bf{n} lines. In the next n lines, you have to print the ith\bf{i^{th}} round’s leading player name “Jodu“, “Modu“ or “Draw“, if both players’ scores are same.

Samples

InputOutput
1
4 3
2 3
3 2
4 6
2 5
Case 1:
Jodu
Draw
Modu
Draw

Initially,
Jodu's Score = 00
Modu's Score = 00
List = [][]

After 1st round,
( J=2J = 2 and M=3M = 3)
Jodu's Score = 2\bf{2}
Modu's Score = 00
List = [3][3]
Jodu is leading

After 2nd round,
( J=3J = 3 and M=2M = 2)
Jodu's Score = 22
Modu's Score = 22
List = [3,3][3,3]
It is a draw

After 3rd round,
( J=4J = 4 and M=6M = 6)
Jodu's Score = 66
Modu's Score = 2582 \rightarrow 5 \rightarrow \bf{8}
List = [3,3][3][][6][3,3] \rightarrow [3] \rightarrow [] \rightarrow [6]
Modu is leading

After 4th round,
( J=2J = 2 and M=5M = 5)
Jodu's Score = 88
Modu's Score = 88
List = [6,5][6,5]
It is a draw

InputOutput
1
4 3
1000 2000
2048 1024
48 2928
1 100000
Case 1:
Jodu
Jodu
Modu
Modu

Submit

Login to submit.

Statistics

80% Solution Ratio
steinumEarliest, Dec '22
steinumFastest, 0.1s
shafin1196Lightest, 4.9 MB
steinumShortest, 735B
Toph uses cookies. By continuing you agree to our Cookie Policy.