접어 만드는 입체 전개도

정육면체나 정팔면체 같은 입체를 만드는 전개도는 여러 기하학 책에서 볼 수 있지만, 실제로 접어 보기 전에는 그 전개도가 정말로 입체를 이루는지 판단하기 어렵습니다. 이 문제에서는 그러한 전개도 가운데 특별한 한 부류를 다룹니다.

평면 위에 놓인 단위 정사각형들로 이루어진 전개도와, 각 변을 어느 방향으로 접어야 하는지에 대한 설명이 주어집니다. 이 전개도를 접었을 때 3차원 입체의 닫힌 표면이 만들어지는지 판단하고, 만들어진다면 그 입체의 부피를 구하세요.

좀 더 정확히 말하면, 전개도는 평면 위에서 서로 연결된 단위 정사각형들의 집합입니다. 연결된 두 정사각형을 잇는 각 변에 대해, 그 변을 앞으로 접을지, 뒤로 접을지(접을 때는 항상 직각으로), 아니면 접지 않을지가 주어집니다. 인접한 두 정사각형 사이의 변이 입력에 나오지 않으면, 그 두 정사각형은 그 변에서 연결되어 있지 않으며 접는 동안 떨어져도 됩니다. 반면 연결된 변은 반드시 설명대로 접어야 합니다.

여기서 닫힌 표면이란, 모든 정사각형이 안쪽과 바깥쪽을 나누는 표면을 말합니다. 전개도를 접고 나면 정사각형들은 3차원 단위 격자 위에 놓이고, 각 정사각형은 안쪽에 있는 한 칸(한 변의 길이가 1인 정육면체)과 바깥쪽에 있는 한 칸을 나눕니다. 모든 칸에 대해 그 칸이 안쪽인지 바깥쪽인지가 명확해야 합니다.

내부가 하나로 이어져 있지 않은 전개도라도 닫힌 표면이 될 수 있음에 유의하세요.

서로 다른 두 정사각형이 공간에서 완전히 같은 위치를 차지할 수는 없지만, 변이나 꼭짓점에서 맞닿을 수는 있습니다(닫힌 표면이라면 실제로 맞닿습니다). 연결된 변을 통해 전개도가 자기 자신을 관통하지 않도록 해야 합니다. 그 밖에는 접는 과정 자체, 예를 들어 어떤 변을 먼저 접는지나 일부 구조가 나머지 접기를 방해하는지 등은 신경 쓰지 않아도 됩니다.

입력은 여러 개의 시나리오로 이루어집니다.

각 시나리오의 첫 줄에는 두 정수 $n$과 $e$가 주어집니다. $n$은 전개도에 있는 정사각형의 수($1 \le n \le 200$), $e$는 변의 수($0 \le e \le 300$)입니다. 정사각형에는 $0$부터 $n-1$까지 번호가 붙습니다. 이어지는 $e$개의 줄에는 각 변이 네 정수 $s_1\ s_2\ p\ f$로 하나씩 주어집니다.

• $s_1$과 $s_2$ ($0 \le s_1 < s_2 < n$): 변이 잇는 두 정사각형.
• $p$: 정사각형 $s_1$을 기준으로 한 정사각형 $s_2$의 위치. $p = 0, 1, 2, 3$은 각각 $s_2$가 $s_1$의 위, 왼쪽, 아래, 오른쪽에 있음을 뜻합니다.
• $f$: 그 변을 접는 방법. $f = 0, 1, 2$는 각각 접지 않음, 앞으로 접음, 뒤로 접음을 뜻합니다.

전개도는 항상 연결되어 있으며, 평면 위에서 서로 겹치지 않게 그릴 수 있다고 가정해도 됩니다.

입력의 끝에는 $n$과 $e$ 자리에 두 개의 $0$이 있는 줄이 옵니다. 이 줄은 처리하지 마세요.

각 시나리오마다 Test case #k:를 출력하세요. 여기서 k는 시나리오 번호이며 1부터 시작합니다. 같은 줄에, 전개도가 닫힌 표면을 이루지 않으면 not a closed surface를, 이루면 closed surface, volume=V를 출력하세요. 여기서 V는 부피를 나타내는 정수입니다.