아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

지루한 게임

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

요약
N×N 보드에서 오른쪽 아래 칸이 앞면인 직사각형을 뒤집는 게임을 하고, 앞면 칸이 M개의 직사각형의 합집합으로 주어질 때 승자를 판정한다.
난이도

어려움10점 중 8점

유형
게임 이론, 조합론, 수학, 기하
정답자
아직 제출이 없습니다

문제

용철이는 동생과 게임을 하고 있다. 게임판은 N×NN \times N 격자이다. 격자의 각 칸에는 동전이 하나씩 들어 있다. 각 동전은 앞면 또는 뒷면이 위로 향해 있다. 두 사람은 번갈아 가며 동전을 뒤집는다. 각 차례에 플레이어는 앞면이 위로 향한 동전이 있는 칸 (x,y)(x, y) (1≤x,y≤N1 \le x, y \le N)와 두 정수 ww, hh (1≤w≤x1 \le w \le x, 1≤h≤y1 \le h \le y)를 고른다. 그다음 플레이어는 두 모서리 칸 (x−w+1,y−h+1)(x - w + 1, y - h + 1)과 (x,y)(x, y)를 마주 보는 꼭짓점으로 하는 직사각형 영역을 보고, 이 직사각형에 속한 모든 동전을 뒤집어 앞면은 뒷면으로, 뒷면은 앞면으로 바꾼다.

차례를 진행할 수 없는 플레이어가 게임에서 진다.

동생과의 게임이 너무 지루해진 용철이는 게임을 곧바로 끝내고 싶어 한다. 그 전에 용철이는 지금부터 두 사람이 최선의 전략으로 플레이할 때 누가 이기는지 알고 싶어 한다. 게임판이 꽤 클 수 있으므로, 현재 상태는 앞면이 위로 향한 동전이 있는 칸들의 합집합을 나타내는 직사각형들의 목록으로 주어지고, 나머지 칸에는 모두 뒷면이 위로 향한 동전이 있다. 다음 차례는 용철이가 둔다. 누가 이기는지 알아낼 수 있겠는가?

입력

입력의 첫 줄에는 테스트 케이스의 수 TT가 주어진다 (1≤T≤2001 \le T \le 200).

각 테스트 케이스의 첫 줄에는 게임판의 크기 NN과 직사각형의 수 MM을 나타내는 두 정수가 주어진다 (1≤N≤1091 \le N \le 10^9, 1≤M≤1051 \le M \le 10^5).

다음 MM개의 줄에는 각각 직사각형의 마주 보는 두 꼭짓점의 좌표 x1x_1, y1y_1, x2x_2, y2y_2가 주어진다 (1≤xi,yi≤N1 \le x_i, y_i \le N, x1≤x2x_1 \le x_2, y1≤y2y_1 \le y_2).

모든 테스트 케이스에 걸친 MM의 합은 6⋅1056 \cdot 10^5을 넘지 않는다. 테스트 케이스의 최소 9090퍼센트에서는 MM이 600600보다 작다.

출력

각 테스트 케이스에서 용철이가 게임을 이기면 "Yong Chol"을, 그렇지 않으면 "Brother"를 출력한다.

예제1

  1. 예제 1

    입력
    2
    3 2
    1 2 1 3
    2 1 3 1
    2 1
    1 1 2 2
    
    예상 출력
    Brother
    Yong Chol