서브프라임

최근 경제 위기의 원인 중 하나는 은행이 상환 능력이 없는 사람에게 돈을 빌려주고, 그 대출을 채권으로 묶어 다른 은행에 다시 팔았다는 점이다. 돈을 빌린 사람이 갚지 못하게 되자 이 구조 전체가 무너졌다.

위기는 Nlogonia까지 번졌다. 총리 Man Dashuva는 중앙은행 총재에게 해결책을 요구했고, 총재는 이런 방안을 내놓았다. 모든 은행이 자기 준비금과 자기가 받을 채권만으로 자기가 발행한 채권을 전부 청산할 수 있다면 구제 금융은 필요 없다.

은행과 채권의 수가 많아 손으로는 확인하기 어렵다. 은행 목록과 은행이 발행한 채권 목록이 주어질 때, Nlogonia 중앙은행의 구제 금융 없이 모든 채권을 청산할 수 있는지 판정하는 프로그램을 작성하라.

청산은 모든 채권을 동시에 정산하는 방식으로 이루어진다. 정산을 마친 뒤 은행 $i$가 보유한 금액은 준비금 $R_i$에서 자기가 발행한 채권 금액의 합을 빼고, 자기가 채권자인 채권 금액의 합을 더한 값이다. 이 금액이 음수인 은행이 하나라도 있으면 구제 금융이 필요하고, 모든 은행이 $0$ 이상이면 필요하지 않다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 은행의 수 $B$와 은행이 발행한 채권의 수 $N$이 공백으로 구분되어 주어진다 ($1 \le B \le 20$, $1 \le N \le 20$). 은행은 $1$부터 $B$까지의 정수로 구분한다. 둘째 줄에는 $B$개의 정수 $R_i$가 공백으로 구분되어 주어지며, $i$번 은행의 준비금을 뜻한다 ($0 \le R_i \le 10^4$). 이어지는 $N$개의 줄에는 각각 세 정수 $D$, $C$, $V$가 공백으로 구분되어 주어진다. $D$는 채무자 은행 ($1 \le D \le B$), $C$는 채권자 은행 ($1 \le C \le B$, $D \ne C$), $V$는 채권 금액 ($1 \le V \le 10^4$)이다.

같은 두 은행 사이에 채권이 여러 개 있을 수 있다.

입력의 끝은 공백으로 구분된 두 개의 $0$만 있는 줄로 표시한다. 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 문자 하나를 출력한다. Nlogonia 중앙은행의 구제 금융 없이 모든 채권을 청산할 수 있으면 S, 구제 금융이 필요하면 N을 출력한다.