액티비티
시간 제한2초메모리 제한512 MB
로라와 보비가 N칸 줄에서 번갈아 말을 움직이고, 같은 칸에 도착하면 상대 말을 K칸 뒤로 보냅니다. 최적으로 두었을 때 누가 이기는지, 또는 무승부인지 구합니다.
문제
날씨가 나쁜 날이면 Lora와 Bobi는 함께 보드게임을 즐긴다. 그들이 가장 좋아하는 게임 중 하나가 Activity이다. 이 문제는 그 게임을 일반화한 버전을 다룬다.
게임은 1번부터 번까지 번호가 붙은 칸짜리 띠 위에서 진행된다. Lora와 Bobi는 각자 말을 하나씩 가지며, 두 말은 모두 1번 칸에서 출발한다. 두 플레이어는 번갈아 자기 말을 앞으로 옮긴다. 한 턴의 규칙은 다음과 같다.
- Lora의 차례에는 말을 최소 1칸, 최대 칸 앞으로 옮겨 유효한 칸에 놓아야 한다. 이때 Lora의 말이 Bobi의 말과 같은 칸에 놓이면, Bobi의 말은 칸 뒤로 밀린다. 처음 칸 안에 있었다면 1번 칸으로 밀린다.
- Bobi의 차례에는 말을 최소 1칸, 최대 칸 앞으로 옮겨 유효한 칸에 놓아야 한다. 이때 Bobi의 말이 Lora의 말과 같은 칸에 놓이면, Lora의 말은 칸 뒤로 밀린다. 처음 칸 안에 있었다면 1번 칸으로 밀린다.
매 턴마다 반드시 말을 움직여야 하며, 차례를 넘길 수는 없다. 자기 말을 먼저 번 칸에 도달시키는 플레이어가 이긴다. Lora가 먼저 둔다.
각 게임에서 두 플레이어가 최적으로 두었을 때 누가 이기는지 구하라. 최적으로 두어도 게임이 영원히 계속될 수 있다. 이 경우 무승부이다.
입력
첫 줄에는 게임의 개수를 나타내는 정수 가 주어진다. 이어지는 개의 줄에는 공백으로 구분된 정수 네 개 , , , 가 한 줄에 하나씩 주어진다.
출력
각 게임마다 최적으로 두었을 때의 결과를 한 줄에 출력한다. Lora가 항상 이길 수 있으면 Lora, Bobi가 항상 이길 수 있으면 Bobi, 어느 쪽도 이기도록 강제할 수 없어 게임이 무한히 계속되면 Draw를 출력한다.
제한