만드는 중입니다

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

코드마스터, 슬라이딩 퍼즐 마스터, 보드게임 마스터

시간 제한1초메모리 제한1024 MB

요약
큰 격자에서 말이 (r,c) 칸에 있을 때, 행이나 열을 줄이는 이동만 허용하는 게임의 선공 승패를 판정하고 이기는 첫 수를 구합니다.
난이도

보통10점 중 5점

유형
게임 이론, 비트 연산
정답자
아직 제출이 없습니다

문제

진서는 진짜 유명한 코드마스터이고, 도훈이는 진짜 유명한 슬라이딩 퍼즐 마스터이다.

둘은 이제 보드게임 마스터 타이틀을 노리고 있다. 그래서 그 타이틀을 걸고 아래 규칙의 보드게임을 하기로 했다.

보드게임은 가로 방향으로 10510^5개의 행, 세로 방향으로 10510^5개의 열로 이루어진 격자판 위에서 진행된다. (i,j)(i,j)는 위에서 ii번째 행과 왼쪽에서 jj번째 열이 만나는 칸을 가리킨다. 예를 들어 (1,105)(1,10^5)은 우측 상단, (105,1)(10^5,1)은 좌측 하단에 있다.

(3,3)(3,3)에 놓인 말의 모습. 왼쪽 (3,1),(3,2)(3,1),(3,2) 또는 위쪽 (1,3),(2,3)(1,3),(2,3)로만 이동할 수 있다.

  • 말이 격자판의 (r,c)(r,c) 칸에 놓인 상태에서 게임이 시작된다.
  • 각 턴마다 플레이어는 말을 같은 행의 왼쪽으로 1칸 이상 옮기거나, 같은 열의 위쪽으로 1칸 이상 옮겨야 한다. 말은 격자판 밖으로 나가면 안 된다.
  • 자신의 턴에 말을 더 이상 옮길 수 없으면 그 플레이어가 패배하고 상대가 이긴다.
  • 선공은 진서이다.

말의 처음 위치가 주어졌을 때 진서와 도훈 중 누가 이기는지 알아내고, 진서가 이긴다면 이기는 방법도 구해보자. 자, 이제 누가 보드게임 마스터지?

입력

첫 번째 줄에 테스트케이스의 개수 tt가 주어진다.

이어서 tt개의 각 줄에는 그 테스트케이스에서 말의 위치를 나타내는 두 정수 r,cr,c가 공백으로 구분되어 주어진다.

출력

각 테스트케이스마다 다음 정보를 출력한다.

첫 번째 줄에 보드게임에서 이기는 사람을 출력한다. 진서가 이기면 jinseo, 도훈이가 이기면 dohoon을 출력한다.

진서가 이기는 경우, 두 번째 줄에 이기기 위해 첫 턴에서 말을 옮길 위치를 나타내는 두 정수 r′,c′r',c'를 공백으로 구분하여 출력한다. 즉, 첫 턴에 (r,c)(r,c)에 있는 말을 (r′,c′)(r',c')으로 옮긴다는 뜻이다.

제한

  • 1≤t≤1001\le t\le 100.
  • 1≤r,c≤1051\le r,c\le 10^5.

예제1

  1. 예제 1

    입력
    2
    1 2
    2 2
    
    예상 출력
    jinseo
    1 1
    dohoon