30210번 - BX 내기

문제

BX란 Base exchange의 약자로, 공군 장병들이 간식 등을 구매할 수 있는 매점을 의미한다. 하루에도 많은 병사들이 BX를 이용하며, 그중 일부 병사들은 가위바위보 등의 게임을 통해 맛있는 음식들을 걸고 내기를 하기도 한다.

전역이 얼마 남지 않은 말년 병장인 준형이와 상민이도 BX의 인기 제품 "슈넬치킨"을 걸고 내기를 하기로 했다. 그러나, 가위바위보가 지겨워진 두 병장은 새로운 게임을 개발했는데, 게임의 규칙은 다음과 같다.

1. 준형이와 상민이는 점수를 0점을 가지고 게임을 시작한다.
2. 준형이부터 시작하여 각 플레이어는 번갈아 가며 턴을 진행하며, 본인의 턴이 되면 최대 $N$자리의 대표 수 하나를 무작위로 생성한다.
3. 이후, 본인의 첫 턴이 아니라면, (이번 턴에 생성된 본인의 대표 수) $+$ (현재 시점까지 상대가 생성한 대표 수 중 본인이 선택한 하나)가 이번 턴의 점수가 된다. 이렇게 만든 점수는 본인의 점수로 갱신하거나 버리고 기존 점수를 유지할 수 있다. 단, 본인의 두 번째 턴이라면 무조건 갱신해야 한다.
4. 각자 $M$턴을 진행한 후, 점수가 더 높은 플레이어가 승리한다.

그러나 게임을 반복적으로 진행하면서 지루해진 두 병장은, 다음과 같이 규칙을 바꾸었다!

• 3ドル$번 규칙의 $+$에서 받아올림을 진행하지 않는다. 즉, 각 자릿수의 합이 10ドル$ 이상인 경우 해당 자릿수는 10ドル$으로 나눈 나머지가 된다. 이를테면 3809ドル + 8315$는 기존 규칙에선 12124ドル$지만, 새로운 규칙에선 1114ドル$가 된다.

하지만, 게임 도중에 둘 다 한 번씩 작업을 나갔다 오면서 게임의 결과를 잊어버렸다! 다행히 둘은 생성한 대표 수들을 수첩에 순서대로 전부 적어두어 놓았다. 그러나 누가 이겼는지 계산하기 귀찮았던 준형이와 상민이는 당신에게 수첩을 보여주며 누가 이겼는지 알려달라고 했다. 두 플레이어 모두 최선을 다했다고 가정할 때, 누가 이겼는지 알아보자.

입력

첫 번째 줄에 대표 수가 가질 수 있는 최대 자릿수 $N$과 게임을 진행한 턴 횟수 $M$이 주어진다.$(1 \le N \le 15;$ 2ドル \le M \le 50,000円)$

두 번째 줄에 준형이가 각 턴에 생성한 대표 수 $a_1, a_2, \cdots, a_M$이 공백으로 구분되어 정수로 주어진다. $a_i$는 준형이가 $i$번째 턴에 생성한 대표 수를 의미한다. $(0 \le a_i \lt 10^{N})$

세 번째 줄에 상민이가 각 턴에 생성한 대표 수 $b_1, b_2, \cdots, b_M$이 공백으로 구분되어 정수로 주어진다. $b_i$는 상민이가 $i$번째 턴에 생성한 대표 수를 의미한다. $(0 \le b_i \lt 10^{N})$

출력

준형이가 이겼으면 J를, 상민이가 이겼으면 S를 출력한다.

둘의 최종 점수가 동일하다면 D를 출력한다.

제한

힌트