33517번 - 징검다리 게임

문제

상혁이는 징검다리 게임을 하고 있다. 이 게임에는 $N$개의 칸으로 구성된 징검다리가 있으며, 플레이어는 첫 번째 칸에서 출발하여 마지막 칸에 도달하면 게임에서 승리한다.

징검다리의 각 칸은 비어 있거나 곰 또는 지뢰 중 하나가 존재하며, 모든 곰의 체력은 1ドル$ 이상의 정수이다. 또한 첫 번째 칸과 마지막 칸은 비어 있다. 징검다리 게임의 명령어는 아래와 같다.

• 점프 (J): 다음 칸으로 이동한다. 이동한 칸에 곰이나 지뢰가 있다면 플레이어는 패배한다.
• 공격 (A): 다음 칸에 있는 곰의 체력을 1ドル$ 깎는다. 곰의 체력이 0ドル$이 되면 다음 칸의 곰은 사라진다. 다음 칸이 빈칸이라면 아무 일도 일어나지 않으며, 다음 칸에 지뢰가 있다면 지뢰가 폭발하여 플레이어는 패배한다.
• 지뢰 제거 (D): 다음 칸에 있는 지뢰를 제거한다. 다음 칸에 지뢰가 없다면 아무 일도 일어나지 않는다.

상혁이는 징검다리 게임에서 승리하기 위해 키 매크로를 개발했다. 키 매크로는 점프(J), 공격(A), 지뢰 제거(D)로 구성된 길이 $K$의 문자열을 입력받으면 문자열의 첫 번째 명령어부터 차례대로 실행한다. 마지막 명령어를 수행한 이후에는 첫 번째 명령어부터 다시 실행한다. 명령어를 10ドル^{100}$회 실행했을 때 마지막 칸에 도달하지 못했다면 플레이어는 패배하며, 키 매크로는 실행 중 게임에서 승리하거나 패배할 경우 즉시 종료된다.

징검다리의 상태와 상혁이가 입력한 문자열이 주어졌을 때, 상혁이가 마지막 칸에 도달하여 게임에서 승리할 수 있다면 YES, 승리할 수 없다면 NO를 출력하시오.

입력

첫 번째 줄에 징검다리의 칸의 개수 $N$이 주어진다. $(3 \leq N \leq 500,000円)$

두 번째 줄에 징검다리의 각 칸의 상태를 의미하는 정수 $A_1, A_2, \cdots, A_N$가 공백으로 구분되어 주어진다. $(-1 \leq A_i \leq 500,000円$; $A_1 = A_N = 0)$

• $i$번째 칸은 $A_i = -1$이면 지뢰가 있는 칸, $A_i \geq 1$이면 체력이 $A_i$인 곰이 있는 칸, $A_i = 0$이면 빈칸이다.

세 번째 줄에 상혁이가 키 매크로에 입력한 문자열의 길이 $K$가 주어진다. $(1 \leq K \leq 1,000円,000円)$

네 번째 줄에 점프(J), 공격(A), 지뢰 제거(D)로 구성된 길이 $K$의 문자열이 주어진다.

출력

상혁이가 마지막 칸에 도달하여 게임에서 승리할 수 있다면 YES, 승리할 수 없다면 NO를 출력한다.

제한

힌트