30426번 - Rebirth

문제

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

어느 날, 시이는 문제에 제출을 할 때마다 다른 차원으로 전생하는 능력을 얻었다.

시이가 문제에 제출할 때마다 전생하는 규칙은 다음과 같다.

• 시이가 사는 기행 우주에는 $N$개의 차원이 있다. 차원에는 각각 0ドル$ 이상 $N$ 미만의 서로 다른 번호가 매겨져 있으며, 처음에 시이는 $M$번 차원에 있다.
• 시이는 첫 번째 문제부터 $K$번째 문제까지 $K$개의 PS문제에 순서대로 정확히 한 번씩 제출한다. 각 문제에 제출할 때 시이는 채점 결과로 맞았습니다!! 또는 틀렸습니다를 받게 되며, 이외의 채점 결과는 존재하지 않는다. 의지력이 약한 시이는 틀렸습니다를 받더라도 같은 문제에 다시 제출하지 않는다.
• $i$번째 문제에 제출하여 시이가 맞았습니다!!를 받았을 때 이동하는 차원의 수 $G_i$와 틀렸습니다를 받았을 때 이동하는 차원의 수 $Y_i$가 존재한다. 시이가 $C$번 차원에 있을 때 $i$번째 문제에 제출하여 채점 결과로 맞았습니다!!를 받으면 $(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$가 주어진다.

출력

첫 번째 줄에, 시이가 성공적으로 유토피아로 갈 수 있으면 utopia, 그렇지 못하면 dystopia를 출력한다.

제한

• 1ドル \le N \le 3000$
• 0ドル \le M \lt N$
• 1ドル \le K \le 3000$
• 0ドル \le G_i, Y_i < N$
• 0ドル \le L < N$
• 0ドル \le X_i < N$
• 0ドル$번 차원과 $M$번 차원은 불안정하지 않다.

힌트