접는 기계

튜링 기계가 더 단순한 계산 모형보다 계산 능력이 강한 이유 하나는 정보를 칸 단위로 저장하는 무한 테이프다.

접는 기계는 튜링 기계에서 착안한 기계다. 테이프의 길이가 유한하고, 각 칸에는 정수가 들어 있으며, 원래 튜링 기계의 동작 대신 테이프를 접는 연산만 수행한다.

접기 연산은 이렇게 진행된다. 기계는 인접한 두 칸 사이 또는 테이프의 양 끝 중 한 곳을 접는 선으로 고르고, 한쪽을 다른 쪽 위로 접는다. 겹친 칸의 값은 서로 더해지고, 접힌 결과가 새 테이프가 된다. 새 테이프의 길이는 두 부분 중 긴 쪽의 길이다.

접는 선이 테이프 가운데일 필요는 없다. 접히는 쪽이 더 짧으면 긴 쪽의 남은 칸은 값을 그대로 유지한다.

테이프의 맨 앞이나 맨 뒤를 접는 선으로 고르면 값은 그대로 남고 테이프의 순서만 뒤집힌다.

Science of Bends 사는 접는 기계의 상용 모델을 개발하고 있고, 최근 생산량이 크게 늘었다. 그런데 마지막 생산 물량 중 일부가 제대로 동작하지 않는다. 결함이 있는 기계를 팔면 회사 이미지가 나빠지므로 출하 전에 추가 검사가 필요하다.

검사에서는 여러 테이프를 기계에 넣고 계산 결과를 받는다. 검사를 맡은 기술자는 결과를 기록해 두었지만, 각 검사에서 어떤 접기를 했는지는 적어 두지 않았다. 모든 기계를 처음부터 다시 검사하는 대신, 기술자들은 입력 테이프에서 기록된 출력 테이프가 나오는 접기 순서가 하나라도 있으면 그 검사를 통과로 인정하기로 합의했다. 입력 테이프와 출력 테이프가 주어질 때, 입력 테이프에서 출력 테이프를 만드는 접기 순서가 존재하는지 판정하는 프로그램을 작성한다. 한 번도 접지 않는 것도 허용하므로, 두 테이프가 이미 같으면 통과다.

입력은 네 줄이다. 앞의 두 줄은 입력 테이프를, 뒤의 두 줄은 출력 테이프를 나타낸다.

첫째 줄에 입력 테이프의 길이 $N$이 주어진다. 둘째 줄에 입력 테이프의 내용인 정수 $N$개 $v_1, \dots, v_N$이 주어진다. 셋째 줄에 출력 테이프의 길이 $M$이 주어진다. 넷째 줄에 출력 테이프의 내용인 정수 $M$개 $w_1, \dots, w_M$이 주어진다.

제한

• $1 \le M \le N \le 15$
• $1 \le i \le N$인 모든 $i$에 대해 $0 \le v_i \le 10^8$
• $1 \le j \le M$인 모든 $j$에 대해 $0 \le w_j \le 10^8$

한 줄에 문자 하나를 출력한다. 입력 테이프에서 출력 테이프를 만드는 접기 순서가 존재하면 S, 존재하지 않으면 N을 출력한다.