Under construction

Still being built. Things may change

Measuring the Cookie's Body

Interview

Time limit1sMemory limit1024 MB

Summary
Given an N by N grid of '*' and '_' forming a cookie shape, find the heart cell and the lengths of both arms, the waist, and both legs.
Level

Medium4 of 10

Topics
Implementation, Simulation, Array, Math
Solved
No attempts yet

Problem

Cookie Run is a mobile running action game made by Devsisters. In it, players set off on an adventure with cookies that escaped from a witch's oven, and the game can be played easily with just two buttons: jump and slide.

Kim Gangsan, an alumnus who graduated from Yonsei University, got a job at Devsisters and spread Cookie Run to the people around him. While spreading the game, however, he discovered that the cookies were developing physical abnormalities. Their arms and legs had changed to arbitrary lengths. Because of this, he urgently needs to measure each cookie's body.

To have their bodies measured, the cookies lie on a square board whose side length is N, and no body part extends outside the board. The cell at row x and column y of the board is denoted (x, y). The top-left cell of the board is (1, 1) and the bottom-right cell is (N, N).

As the figure shows, a cookie's body consists of a head, a heart, a waist, and left and right arms and legs. The part colored red in the figure is the heart. The head is one cell in size and sits in the cell directly above the heart. The left arm is attached directly to the left of the heart and extends to the left, and the right arm is attached directly to the right of the heart and extends to the right. The waist is attached directly below the heart and extends downward. The left leg is attached directly below and to the left of the waist, and the right leg is attached directly below and to the right of the waist, and each leg extends downward. No body part is ever broken apart, and none is bent. Also, the waist, arms, and legs each have length at least 1, and their width is always 1.

Given a cookie's body, find the location of the heart and the lengths of the arms, legs, and waist.

Input

The input is given as follows.

N
a1,1 . . . a1,N
. . . . . .
aN,1 . . . aN,N

Output

On the first line, print the row number x and the column number y of the heart, separated by a space.

On the second line, print the lengths of the left arm, right arm, waist, left leg, and right leg, separated by spaces.

Constraints

  • 5 ≤ N ≤ 1,000. N is a positive integer giving the side length of the board.
  • ai,j is either * or _. * is a part of the cookie's body, and _ is a cell where no part of the cookie's body lies. (1 ≤ i, j ≤ N)
  • The input never violates the conditions on a cookie's body.

Examples3

  1. Example 1

    Input
    5
_____
__*__
_***_
__*__
_*_*_
    Expected output
    3 3
1 1 1 1 1

  2. Example 2

    Input
    10
__________
_____*____
__******__
_____*____
_____*____
_____*____
____*_*___
____*_____
____*_____
____*_____
    Expected output
    3 6
3 2 3 4 1

  3. Example 3

    Input
    9
____*____
*********
____*____
____*____
____*____
___*_*___
___*_*___
___*_*___
___*_*___
    Expected output
    2 5
4 4 3 4 4