Oil Exploration

Interview

Time limit1sMemory limit128 MB

Summary

For each column of a grid, scan downward and sum drilling costs (H costs 3, S costs 1) until the first oil cell, or print N if none exists.

Level: Easy2 of 10
Topics: Array, Simulation, Implementation
Solved: No attempts yet

Problem

Before oil can be extracted, someone first has to find it. Oil companies want to find oil they can extract as cheaply as possible. A major part of the price is how deep, and through what material, one must drill before reaching oil. For this problem the size of the oil reservoir is ignored. Given a map of the seafloor, compute the cost of drilling at each position.

Input

The first line contains the number of data sets $K$ . Then $K$ data sets follow, each in the format below.

The first line of each data set contains two integers $h$ and $w$ ( $1 \le h, w \le 40$ ): the height and width of the seafloor map. This is followed by $h$ lines, each a string of $w$ upper-case letters. Each letter is one of:

X: oil is present at that location
H: hard rock
S: soft rock

Drilling through one cell of hard rock costs $3$ , and through one cell of soft rock costs $1$ . For each of the $w$ columns, drill straight down from the top and compute the total cost until the first oil is reached. Some columns may contain no oil at all; for those, output the letter N instead of a cost.

Output

For each data set, first output a line of the form Data Set x:, where $x$ is the data set's number (starting from 1). On the next line, output the $w$ drilling costs from left to right, separated by a single space (with no trailing space). For a column with no oil, output N. Print a blank line between the outputs of two consecutive data sets (there is no blank line after the last data set).

Examples1

Example 1

Input

2
1 1
H
3 5
XXHSS
XHSSX
XHXSS

Expected output

Data Set 1:
N

Data Set 2:
0 0 4 N 1