12867번 - N차원 여행

수빈이는 여행을 좋아한다. 더 이상 지구에서 여행할 곳이 없어진 수빈이는 N차원 우주로 여행을 떠났다. 우주의 각 점은 좌표 N개로 이루어 지며, 각각의 좌표는 1부터 N까지 인덱스가 매겨져 있다.

수빈이는 원점(모든 좌표가 0인 곳)에서  여행을 시작하며, 아래와 같은 방법으로 움직인다.

• 첫 번째로 움직일 좌표의 인덱스를 고른다. (1부터 N까지 중의 하나)
• 그 다음, 그 좌표의 값을 1만큼 증가시킨 곳이나 감소시킨 곳으로 이동한다. (다른 좌표는 이동하기 전과 같아야 한다)

수빈이는 여행을 떠나기 전에 여행 계획을 작성해 놓았고, 같은 점을 두 번 이상 방문하는지 아닌지 알아보려고 한다.

수빈이가 여행 계획에서 고른 좌표 인덱스와, 좌표가 증가하는 방향으로 이동했는지, 감소하는 방향으로 이동했는지가 주어진다. 수빈이가 첫 번째 점과 마지막 점을 포함한 모든 점을 중복해서 방문하지 않게 방문할 수 있다면 1을, 아니면 0을 구하는 프로그램을 작성하시오.

첫째 줄에 N (1 ≤ N ≤ 1,000,000,000)이 주어진다.

둘째 줄에는 수빈이의 여행 계획의 길이 M (1 ≤ M ≤ 50)이 주어진다.

셋째 줄에는 수빈이가 여행 계획에서 고른 좌표의 인덱스가 순서대로 주어진다.

넷째 줄에는 증가하는 방향으로 이동할 것인지, 감소하는 방향으로 이동할 것인지를 나타내는 문자열이 주어지며, +는 증가하는 방향, -는 감소하는 방향을 나타낸다.

모든 점을 중복해서 방문하지 않을 수 있으면 1을, 아니면 0을 출력한다.

예제 2의 경우에 (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,0)으로 이동하게 되어서 (0, 0)을 두 번 방문하게 되고, 예제 3의 경우에는 (0,0,0) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,0,1) 으로 방문하게 되어서 모든 점을 중복하지 않게 방문한다.