시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 0 0 0 0.000%

문제

당신은 지리산 등반 도중 장이 열리는 장터를 발견하였다. 많은 사람들이 모여있는 와중에, 어떤 사람이 게임을 주최하고 있었다.

이 게임에서는 탁자 위에 N줄 M열의 격자가 있는 게임판을 이용한다. 격자의 각 칸에 하나씩 K면 다면체가 있다.

게임은 다음과 같이 진행된다. 게임 주최자는 다면체 중 일부를 특정 면이 보이도록 고정시켜놓고, 일부는 자유로이 움직일 수 있도록 한다. 그후, 이 게임판을 흔드는데, 그러면 고정되지 않은 다면체들(이들을 '자유로운 다면체'라고 한다)은 흔들리다가 K면 중 한 면이 선택되어 보이게 된다. 이 때, K면 중 어떤 면이 보일 확률은 모든 면에 대해서 같으며 각각의 다면체에 대해 독립적이다.

게임판이 멈추면 각 칸에 대해 점수를 매기게 된다.

1) 이 칸의 다면체를 포함하여 가로/세로/대각선 으로 연속해서 4개가 같은 면을 가리키는 경우가 존재 - S4
2) 1)에 해당하지 않고 연속한 3개에 대해서는 이런 경우가 존재 - S3
3) 2)에 해당하지 않고 연속한 2개에 대해서는 이런 경우가 존재 - S2

각 다면체에 대해 나온 점수를 모두 합하면 그 게임의 점수가 된다.

어떤 게임 도중, 다면체를 고정시키는 작업이 완성되었고 이제 게임판을 흔드는 차례가 되었다.

당신은 이 게임의 결과가 궁금해졌다. 이 게임판을 흔들었을 때 얻을 수 있는 점수의 기대값은 몇 점일까?

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다.

각 테스트 케이스는 다음과 같이 주어진다.

N M K S4 S3 S2

F1,1 F1,2 ... F1,M

F2,1 F2,2 ... F2,M

...

FN,1 FN,2 ... FN,M

각 케이스의 첫 줄에는 다음과 같이 정수 6개가 주어진다: N은 게임판의 행 수, M은 열 수를 나타내며, K는 다면체의 면의 수이다. S4S3S2는 문제에 설명된 해당 점수이다.

두 번째 줄부터 N개의 줄은 순서대로 게임판의 가장 위부터 게임판의 각 행에 존재하는 다면체들의 상태를 나타낸다. 각 줄은 M개의 숫자로 이루어져 있으며, 그 행의 왼쪽부터의 다면체의 상태를 나타낸다. 고정된 다면체는 보여지는 면의 숫자 1부터 K까지의 한 자리 숫자로 나타내어지고, 자유로운 다면체는 '?'로 나타내어진다.

제한

  • 1 ≤ T ≤ 50.
  • 2 ≤ K ≤ 9.
  • 0 ≤ S2 ≤ S3 ≤ S4 ≤ 100.
  • 2 ≤ N ≤ 8, 2 ≤ M ≤ 8.
  • 각 입력 게임판에서, 자유로운 다면체의 수는 0개 이상 4개 이하이다.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 주어진 케이스에 대한 점수 기대값이다.

예제 입력 1

2
2 3 3 40 30 10
121
??1
4 3 4 100 30 20
2?2
4?1
3?3
1?4

예제 출력 1

Case #1: 53.3333333
Case #2: 187.7734375

힌트