타일 맞추기

세계적으로 유명한 타일 생산 회사인 오썸타일 사에서는 창사 $100$주년을 맞아 한글을 무늬로 넣은 흥미있는 타일을 생산한다. 정사각형 모양의 각 타일은 $3 \times 3$ 격자모양으로 되어 있고, 아래 그림에서 보듯이 격자의 각 칸에는 [풀], [물], [길], [흙] 중 한 글자가 새겨져 있다.

글자가 새겨진 타일들을 여러 장 이어 붙여 지도를 제작하고자 한다. 아래 그림은 $4$장의 타일을 이어 붙여 얻은 지도의 한 형태를 보여 준다. 한 격자 칸에서 상하좌우에 연결된 격자 칸을 인접한 칸이라고 부른다. 또한 한 타일에서 상하좌우에 연결된 타일을 인접한 타일이라 부른다.

여러 장의 타일을 이어 붙여 지도를 만들 때, 아래에서 설명한 규칙을 따라서 제작된 지도는 ‘바른 지도’, 그렇지 않은 지도는 ‘엉터리 지도’라고 부른다.

지도 제작 규칙은 다음과 같다.

1. 한 타일 안에 있는 [길]들끼리는 반드시 서로 인접해야 한다.
2. [길]을 포함한 타일의 [길] 중 하나는, 적어도 하나 이상의 다른 타일의 [길]과 연결되어야 한다
3. [길]의 폭은 반드시 한 칸이어야 한다. (임의의 $2\times 2$ 격자 칸이 모두 [길]로만 이뤄지는 경우가 있어선 안 된다.)
4. [물]과 [흙]은 인접해선 안 된다.
5. [풀]은 [물]이나 [길]에 반드시 인접해야 한다.

지도에 대한 정보가 주어질 때, 이 지도가 ‘바른 지도’인지 ‘엉터리 지도’인지를 판별하는 프로그램을 작성하고자 한다.

입력 형식

첫 번째 줄에는 타일 종류의 수를 나타내는 정수 $N$ ($1 \le N \le 100,000$)이 주어진다.

다음 $N$개의 각 줄에는 타일 정보가 주어진다. 타일 정보는 타일의 고유 아이디를 나타내는 정수 $K$와, $3\times 3$ 격자의 각 칸에 적인 글자 정보로 구성된다. 격자에 적힌 한글 정보는 편의상 영어 알파벳 G(풀), W(물), R(길), D(흙)으로 이뤄져 있고, 좌에서 우로, 위에서 아래로의 순서로 적힌다.

참고로, 타일 아이디 $K$는 중복되지 않는 고유한 값이다. 아래 그림은 아이디가 $283$인 타일에 대한 그림이며 이를 위한 입력 예는 다음과 같다. ($1 \le K \le 100\,000$)

283 G R D G R R W W W

다음 줄에는 지도의 크기를 나타내는 두 정수 $C$와 $R$이 주어진다. 즉, $C$개의 타일이 한 가로줄에 이어 붙여 놓여 있으며, 이런 줄 수가 $R$개임을 나타낸다. ($1 \le C, R \le 300$)

이어지는 $R$ 줄 각각엔 $C$개의 정수가 공백으로 구분되어 주어지는데, 각 값은 타일 고유 아이디를 나타내는 정수이다.

출력 형식

주어진 지도가 바른 지도이면 Good, 그렇지 않은 경우엔 Bad를 표준 출력으로 출력한다.

예제

4
33 G G G R R G G R G
71 G R D G R R G R D
65 G R G W R R W W W
92 G R D R R R W W W
2 2
33 71
65 92

Bad

채점 방식

전체 입력 케이스들 중 답을 맞춘 입력 케이스 개수에 비례하여 점수를 받는다.

해설