Find Places to Lie Down

Interview

Time limit2sMemory limit128 MB

Summary

Count maximal horizontal and vertical runs of at least two consecutive empty cells in an N x N grid.

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

Problem

There is a square room of size N x N. Each cell is either empty or blocked by luggage. An empty cell is written as ., and a blocked cell is written as X.

A person can lie down horizontally or vertically in a consecutive run of at least two empty cells. Think of the person as stretching across the whole run, from one end to the other. Therefore, each empty run whose length is at least 2 counts as exactly one place to lie down.

Given the room layout, find how many places are available horizontally and how many are available vertically.

Input

The first line contains the room size N. N is an integer between 1 and 100, inclusive.

Each of the next N lines contains a string of length N. . means an empty cell, and X means a blocked cell.

Output

Print two integers separated by a space: the number of horizontal places to lie down and the number of vertical places to lie down.

Examples1

Example 1
Input
```
5
....X
..XX.
.....
.XX..
X....
```
Expected output
```
5 4
```