Water?

Time limit1sMemory limit128 MB

Summary

Given an h by w grid of letters and a set of special letters, find the subrectangle with both sides at least m whose fraction of special pixels is maximum, breaking ties by larger area.

Level: Medium7 of 10
Topics: Prefix sum, Brute force, Math, Implementation
Solved: No attempts yet

Problem

One of the main goals of sending the Curiosity rover to Mars is to look for more evidence that Mars may have had water on its surface in the past, or perhaps still does today. To decide whether water was present, scientists rely on clues in the images, such as rust and other signs of oxidation. In this problem you examine pictures of the Martian surface and find evidence of water in them if it exists.

Each picture is given as a rectangle of $h \times w$ pixels, with $1 \le h, w \le 50$ . Every pixel indicates a type of material, written as one upper-case letter from A to Z (no other characters appear). Some of these letters are marked as special: they are the clues for water. Given a minimum size $m$ with $1 \le m \le \min(h, w)$ , find the largest density of special letters over all axis-aligned subrectangles whose height and width are both at least $m$ .

The density of a rectangle is the number of special pixels it contains divided by its total number of pixels.

Input

The first line contains the number $K$ of data sets. Each of the $K$ data sets has the following form:

One line with three integers $h$ , $w$ , $m$ : the image height, the image width, and the minimum rectangle size.
One line with a string of $1$ to $26$ distinct upper-case letters (A–Z, not necessarily sorted). These are the special, water-indicating letters.
$h$ lines follow, each consisting of exactly $w$ upper-case letters describing one row of the image.

Output

For each data set, print Data Set x: on its own line, where $x$ is the data set number (starting from $1$ ). On the next line print the maximum density as a fraction a/b, where $a$ is the number of special pixels and $b$ is the total number of pixels of the chosen rectangle, considering only rectangles whose height and width are both at least $m$ .

The fraction is written exactly as counted and is not reduced (for example 8/16, not 1/2). If several rectangles reach the same maximum density, choose the one with the largest total number of pixels $b$ ; this makes the answer unique.

Separate consecutive data sets with a blank line.

Examples7

Example 1

Input

1
6 13 3
YX
ITTTTHHHHTTTT
IXYOXOOOOOOXI
IOOOXOOOOOXXJ
IYOOOOXOOOOOI
IXXOYOOYOOOOI
IAAAAAXAXAAAJ

Expected output

Data Set 1:
8/16

Example 2
Input
```
1
1 1 1
A
A
```
Expected output
```
Data Set 1:
1/1
```
Example 3
Input
```
1
1 1 1
Z
A
```
Expected output
```
Data Set 1:
0/1
```

Example 4

Input

1
4 5 2
A
AAAAA
AAAAA
AAAAA
AAAAA

Expected output

Data Set 1:
20/20

Example 5
Input
```
1
3 3 3
X
XOX
OXO
XOX
```
Expected output
```
Data Set 1:
5/9
```
Example 6
Input
```
1
2 4 2
X
XOXO
OXOX
```
Expected output
```
Data Set 1:
4/8
```

Example 7

Input

2
1 1 1
X
X
2 4 2
X
XOXO
OXOX

Expected output

Data Set 1:
1/1

Data Set 2:
4/8