만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

액티비티

시간 제한2초메모리 제한512 MB

요약
로라와 보비가 N칸 줄에서 번갈아 말을 움직이고, 같은 칸에 도착하면 상대 말을 K칸 뒤로 보냅니다. 최적으로 두었을 때 누가 이기는지, 또는 무승부인지 구합니다.
난이도

보통10점 중 7점

유형
게임 이론, 동적 계획법, BFS
정답자
아직 제출이 없습니다

문제

날씨가 나쁜 날이면 Lora와 Bobi는 함께 보드게임을 즐긴다. 그들이 가장 좋아하는 게임 중 하나가 Activity이다. 이 문제는 그 게임을 일반화한 버전을 다룬다.

게임은 1번부터 NN번까지 번호가 붙은 NN칸짜리 띠 위에서 진행된다. Lora와 Bobi는 각자 말을 하나씩 가지며, 두 말은 모두 1번 칸에서 출발한다. 두 플레이어는 번갈아 자기 말을 앞으로 옮긴다. 한 턴의 규칙은 다음과 같다.

  • Lora의 차례에는 말을 최소 1칸, 최대 LL칸 앞으로 옮겨 유효한 칸에 놓아야 한다. 이때 Lora의 말이 Bobi의 말과 같은 칸에 놓이면, Bobi의 말은 KK칸 뒤로 밀린다. 처음 KK칸 안에 있었다면 1번 칸으로 밀린다.
  • Bobi의 차례에는 말을 최소 1칸, 최대 BB칸 앞으로 옮겨 유효한 칸에 놓아야 한다. 이때 Bobi의 말이 Lora의 말과 같은 칸에 놓이면, Lora의 말은 KK칸 뒤로 밀린다. 처음 KK칸 안에 있었다면 1번 칸으로 밀린다.

매 턴마다 반드시 말을 움직여야 하며, 차례를 넘길 수는 없다. 자기 말을 먼저 NN번 칸에 도달시키는 플레이어가 이긴다. Lora가 먼저 둔다.

각 게임에서 두 플레이어가 최적으로 두었을 때 누가 이기는지 구하라. 최적으로 두어도 게임이 영원히 계속될 수 있다. 이 경우 무승부이다.

입력

첫 줄에는 게임의 개수를 나타내는 정수 TT가 주어진다. 이어지는 TT개의 줄에는 공백으로 구분된 정수 네 개 NN, LL, BB, KK가 한 줄에 하나씩 주어진다.

출력

각 게임마다 최적으로 두었을 때의 결과를 한 줄에 출력한다. Lora가 항상 이길 수 있으면 Lora, Bobi가 항상 이길 수 있으면 Bobi, 어느 쪽도 이기도록 강제할 수 없어 게임이 무한히 계속되면 Draw를 출력한다.

제한

1≤L,B≤N1 \le L, B \le N

1≤K≤min⁡(L,B)1 \le K \le \min(L, B)

예제1

  1. 예제 1

    입력
    3
    10 4 3 2
    5 2 3 1
    4 2 2 2
    
    예상 출력
    Lora
    Bobi
    Draw