1542번 - 체스 연습

세준이와 다솜이는 체스를 취미로 즐긴다. 하지만, 이제 국가대표가 되어야겠다는 목표로 오늘부터 연습을 하려고 한다. 오늘은 100×100크기의 체스판에서 퀸만 가지고 공격 기술을 연습하려고 한다.

체스판 위에는 퀸이 N개 올려져 있다. 이 연습은 세준이 먼저, 그다음에 다솜이, 그리고 다시 세준이와 같이 턴을 번갈아 가면서 진행된다.

하나의 턴에 하나의 퀸을 고른 후, 옮긴다. 만약 퀸이 (x,y)에 있었다면, 퀸은 (x-k,y), (x,y-k), (x-k,y-k)중에 하나로 옮길 수 있다. (k>0) 그리고, 퀸은 다른 퀸이 있는 칸을 통과 할 수도 있고, 한 칸에 여러 퀸이 있을 수도 있다.

이 연습은 (0,0)에 퀸을 하나라도 먼저 놓는 사람이 이긴다. 세준이와 다솜이가 항상 최적의 방법으로 연습한다고 가정할 때, 승자를 출력하는 프로그램을 작성하시오.

5개의 게임이 입력으로 들어오며, 각각의 게임은 다음과 같이 구성되어 있다. 첫째 줄에는 체스판 위에 있는 퀸의 개수 N이 주어진다. 이 값은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에는 퀸의 위치가 X Y의 순서로 들어온다. 퀸이 (0, 0)에 있는 경우는 없다.

각 게임의 승자가 세준이면 S, 다솜이면 D를 출력한다.