체스 연습

세준이와 다솜이는 체스를 취미로 즐긴다. 이제 두 사람은 국가대표를 목표로 훈련을 시작한다. 오늘은 100×100 크기의 체스판에서 퀸만 사용해 공격 기술을 연습한다.

체스판에는 퀸 N개가 놓여 있다. 세준이가 먼저 시작하고, 이후 다솜이와 세준이가 번갈아 턴을 진행한다.

한 턴에는 퀸 하나를 골라 이동한다. 퀸이 (x, y)에 있다면 양의 정수 k를 골라 (x-k, y), (x, y-k), (x-k, y-k) 중 하나로 옮길 수 있다. 퀸은 다른 퀸이 있는 칸을 지나갈 수 있고, 여러 퀸이 같은 칸에 있어도 된다.

먼저 어떤 퀸이라도 (0, 0)에 놓는 사람이 이긴다. 두 사람이 항상 최적으로 플레이할 때 각 게임의 승자를 구하라.

입력에는 5개의 게임이 주어진다. 각 게임은 다음 형식이다.

첫 줄에는 체스판 위의 퀸 개수 N이 주어진다. N은 50 이하이다. 이어지는 N개의 줄에는 퀸의 위치 X Y가 주어진다. 처음부터 퀸이 (0, 0)에 있는 경우는 없다.

각 게임마다 승자가 세준이면 S, 다솜이면 D를 한 줄에 하나씩 출력한다.