30041번 - Nice Cube Price

문제

종이에 $N$ 개의 정육면체 전개도가 그려져 있다. 각 주사위의 한 변의 길이는 5ドル$이며, 3ドル \times 3$ 크기의 각 면에는 1부터 9까지의 숫자가 적혀있다.

다음은 가능한 정육면체 전개도 중 하나다.

....+---+........
....|333|........
....|333|........
....|333|........
+---+---+---+---+
|111|222|656|876|
|111|222|565|947|
|111|222|656|798|
+---+---+---+---+
........|847|....
........|596|....
........|785|....
........+---+....

전개도를 접을 때에는 항상 인쇄된 면이 바깥에 오도록 한다. 즉, 위의 전개도를 접으면, 숫자 1ドル,ドル 2ドル,ドル 3ドル$이 적혀있는 면이 차례대로 반시계 방향을 이루게 된다.

종이에 인쇄된 전개도를 모두 오린 후 접어, 정육면체의 큐브를 만들자.

각 큐브의 가치는 다음과 같이 결정된다:

• 한 면에 대해, 그 면에 적혀있는 숫자의 제곱의 합을 $S$라고 하자. 또한, 그 면에 적혀있는 숫자를 배열하여 얻을 수 있는 (십진법으로) 가장 큰 수를 $L$이라고 하자. 그 면의 숫자의 가치는 $L\mod(S+15)$이다. 큐브 숫자의 가치는 여섯 면의 숫자의 가치 중 가장 큰 수와, 두 번째로 작은 수와, 가장 작은 수의 합이다.
• 한 면에 대해, 그 면 위에 놓인 아홉 개의 칸들 중, 적혀있는 숫자 값의 차이가 3ドル$ 이하면서 서로 한 변을 공유하는 칸 쌍의 개수에 1ドル$을 더한 값을 그 면의 이웃의 가치라고 하자. 큐브 이웃의 가치는 여섯 면의 이웃의 가치의 곱이다.
• 다섯 개의 숫자의 시너지 가치란, "각 숫자를 정확하게 한 번씩 사용하여 만들 수 있는 수면서 동시에 수열 $A$의 어떤 원소 $A_i$ $(1\le i\le K)$의 약수기도 한 수"들의 집합을 $S$라고 할 때, $S$의 크기의 제곱과 $S$의 모든 원소의 합을 더한 것이다. 여기서, 수열 $A$는 입력에서 주어진다. 3ドル\times 3$ 격자판에서 상하좌우 네 방향으로 연결되어 있도록 다섯 개의 칸을 선택하는 방법은 총 49ドル$ 가지가 있다. 한 면에 대해, 그 면에서 연결된 다섯 개의 칸을 고르고, 고른 칸에 적힌 다섯 개의 숫자의 시너지 가치를 모두 계산하면, 총 49ドル$ 개의 수를 얻을 것이다. 한 면의 T1의 가치는 이 49ドル$ 개의 시너지 가치의 최댓값과 최솟값과 중앙값의 합이다. 큐브 T1의 가치는 여섯 면 중 하나의 공통된 꼭짓점을 공유하는 세 면을 잡아, 그 세 면의 T1의 가치의 합 중 최댓값이다.
• 한 면에 대해, 그 면의 지뢰찾기의 가치는 8ドル$방향으로 인접한 “숫자 칸의 개수”와 “그 숫자들의 합을 9ドル$로 나눈 나머지”의 차이가 4ドル$ 이하인 그 면 내부의 칸의 개수다. 큐브 지뢰찾기의 가치는 각 12ドル$ 개의 모서리에 대해, 그 모서리를 가지는 두 면의 지뢰찾기의 가치의 곱의 합이다.
• 한 면에 대해, 그 면의 체스의 가치는 그 면을 3ドル\times 3$의 빈 체스판으로 생각할 때, 서로 공격하지 않도록 짝수가 적힌 칸에 비숍을 놓을 때 가능한 비숍의 최대 개수다. 큐브 체스의 가치는 여섯 면의 체스의 가치의 합이다.
• 큐브의 가치는 큐브 숫자의 가치, 큐브 이웃의 가치, 큐브 T1의 가치, 큐브 지뢰찾기의 가치, 그리고 큐브 체스의 가치의 합을 20ドル,円 010,円 610$으로 나눈 나머지다.

여러분은 큐브의 가치를 최대화하기 위하여 큐브를 섞을 수 있다. 큐브를 섞는다는 것은, 큐브의 한 바깥층을 잡고, 그 층을 90ドル$도, 180ドル$도, 270ドル$도 중 한 각도로 회전시킴을 뜻한다. (큐브에는 총 6ドル$ 개의 바깥층이 있고, 회전 각도는 세 가지이므로, 큐브를 섞는 방법은 총 6ドル\times 3=18$ 가지가 있다.) 단, 하나의 큐브에 대해 최대 한 번까지만 섞을 수 있다.

또한, 큐브를 너무 많이 섞게 되면 그만큼 손목이 아플 수 있다. 여러분은 총 $P$ 번까지만 큐브를 섞을 수 있다.

큐브를 섞어 얻을 수 있는 $N$ 개의 큐브의 가치의 합의 최댓값을 구하라. 여러분은 이 값을 각 $P=0,1,2,\cdots ,N$에 대해 독립적으로 계산해야 한다.

입력

첫 번째 줄에 두 정수 $H,ドル $W$가 공백으로 구분되어 주어진다.

두 번째 줄에는 정수 $K$가 주어진다.

세 번째 줄에는 $K$ 개의 정수 $A_1,\cdots ,A_K$가 공백으로 구분되어 주어진다.

네 번째 줄부터 $H$ 개의 줄에 걸쳐, 인쇄된 종이의 정보가 주어진다. 각 줄은 $W$ 개의 문자로 이루어져 있고, 각 문자는 1 부터 9 까지의 숫자, ., -, |, + 중 하나다.

출력

$N+1$ 개의 줄에 걸쳐, 답을 출력한다. $(i+1)$ 번째 줄에는 $P=i$일 때의 답을 출력한다. $\left( 0\le i\le N \right)$

제한

• 9ドル\le H \le 1,円 000$
• 9ドル\le W \le 1,円 000$
• 1ドル\le N$
• 1ドル\le K\le 100$
• 1ドル\le A_i\le 10^{18}$ $(1\le i\le K)$
• 종이에 주어지는 전개도는 모두 크기 3ドル\times 3\times 3$의 올바른 정육면체의 전개도다.
• 전개도가 겹쳐서 주어지지 않는다.
• 전개도가 차지하는 영역 밖에 있는 모든 문자는 .이다.

노트

큐브를 회전함으로 인해 6과 9를 혼동하는 일은 없다고 가정하라.