전생

면접 대비

시간 제한1초메모리 제한512 MB

요약

각 문제의 정답 여부를 골라 시작 차원 M에서 출발해 불안정한 차원을 피하고 차원 0에 도달할 수 있는지 판별합니다.

문제

돌림노래를 부르고 만족한 시이는 다시 평소처럼 PS 문제를 푸는 일상으로 돌아갔다.

어느 날부터 시이는 문제에 제출할 때마다 다른 차원으로 전생하는 능력을 얻었다. 전생 규칙은 다음과 같다.

시이가 사는 기행 우주에는 $N$ 개의 차원이 있다. 차원에는 $0$ 이상 $N$ 미만의 서로 다른 번호가 매겨져 있으며, 처음에 시이는 $M$ 번 차원에 있다.
시이는 첫 번째 문제부터 $K$ 번째 문제까지 $K$ 개의 PS 문제에 순서대로 정확히 한 번씩 제출한다. 제출하면 맞았습니다!! 또는 틀렸습니다 중 하나의 채점 결과를 받으며, 다른 결과는 없다. 의지가 약한 시이는 틀렸습니다를 받아도 같은 문제에 다시 제출하지 않는다.
$i$ 번째 문제에서 맞았습니다!!를 받으면 $G_i$ 만큼, 틀렸습니다를 받으면 $Y_i$ 만큼 차원을 이동한다. $C$ 번 차원에 있을 때 맞았습니다!!를 받으면 $(C+G_i) \bmod N$ 번 차원으로, 틀렸습니다를 받으면 $(C+Y_i) \bmod N$ 번 차원으로 전생한다.
불안정한 차원이 $L$ 개 있다. 시이가 이 차원들 중 하나로 전생하면 차원 미아가 된다. 차원 미아가 된 뒤에는 문제에 제출하더라도 더 이상 전생할 수 없다.
시이는 유토피아로 알려진 $0$ 번 차원으로 가고 싶다. 다만 PS를 좋아하는 시이는 모든 문제에 적어도 한 번 제출하지 않으면 만족하지 못한다. 즉, 모든 문제를 순서대로 시도한 뒤 차원 미아가 되지 않고 $0$ 번 차원에 있어야 유토피아에 도달한 것이다.
$0$ 번 차원과 $M$ 번 차원은 불안정한 차원이 아니다.

위의 정보가 주어졌을 때, 시이가 각 문제에서 맞았습니다!!와 틀렸습니다 중 하나를 받아 유토피아인 $0$ 번 차원에 도달할 수 있는지 구하여라.

첫 번째 줄에 총 차원의 개수 $N$ , 시이가 현재 있는 차원 $M$ , 시이가 풀고자 하는 문제의 개수 $K$ 가 공백으로 구분되어 주어진다.

두 번째 줄부터 $K$ 개 줄 중 $i$ 번째 줄에는 맞았습니다!!를 받았을 때 이동하는 차원의 수 $G_i$ 와 틀렸습니다를 받았을 때 이동하는 차원의 수 $Y_i$ 가 공백으로 구분되어 주어진다.

그다음 줄에는 불안정한 차원의 수 $L$ 이 주어진다. 이어지는 $L$ 개 줄 중 $i$ 번째 줄에는 불안정한 차원의 번호 $X_i$ 가 주어진다.

시이가 유토피아인 $0$ 번 차원으로 갈 수 있으면 utopia, 그렇지 못하면 dystopia를 출력한다.