A fleet was placed uniformly at random on an n x n grid among all valid placements: k ships of lengths l_1, ..., l_k, each occupying l_i consecutive cells in a row or column, with no two ships overlapping (touching is allowed). You are playing battleship against this hidden placement and it is your turn to shoot.

Your shot should maximize the probability of an immediate hit: among all cells that have not been shot, find the cell whose probability of being occupied by a ship — conditional on all observed hits and misses — is maximal. If several cells attain the maximum, output the one with the smallest row index, breaking remaining ties by the smallest column index.

Input

The first line contains n and k. The second line contains l_1, ..., l_k. Each of the next n lines contains n characters describing the current board: . (not yet shot), M (shot, miss) or H (shot, hit).

The board is guaranteed to be consistent with at least one valid placement, and at least one unshot cell has positive hit probability.

Output

The row and column of the cell to shoot, 1-indexed, separated by a space.

Constraints

5 <= n <= 10 1 <= k <= 3 2 <= l_i <= n

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.