Elderly Bajtazar owns an orchard where apple trees bearing pure gold fruit grow. Unfortunately, working in the orchard is hard, and Bajtazar no longer has as much strength as he used to, so he has decided to divide his orchard into plots to be cultivated by his sons. Bajtazar wants to ensure a prosperous life for each of his sons, so he desires that each of them receives at least one precious apple tree.

Bajtazar's orchard is a rectangle with dimensions $n \times n$ meters. For simplicity, we introduce a rectangular coordinate system where the bottom-left corner of the orchard has coordinates $(0, 0)$ and the top-right corner has coordinates $(n, n)$. We know in which unit squares of the orchard the apple trees grow. The plots resulting from the division of the orchard must be rectangles with sides aligned with the grid lines of the coordinate system. The plots cannot overlap—they may only touch at their sides or vertices—and they must cover the entire orchard. The dimensions of the plots do not matter; it is only important that each plot contains at least one apple tree.

You may assume that the requested division of the orchard is possible.

Input

The first line of input contains two integers $n$ and $k$ ($1 \le n \le 1\,000$, $1 \le k \le n^{2}$), representing the side length of the orchard and the number of Bajtazar's sons. The next $n$ lines contain the description of the contents of the individual squares of the orchard. Each of these lines contains $n$ characters x and/or ., representing a square containing an apple tree and a square not containing an apple tree, respectively.

Output

Your program should output $k$ lines describing an example division of the orchard into plots. Each line should contain four integers $x_{1}$, $y_{1}$, $x_{2}$, $y_{2}$ representing the coordinates of the bottom-left $(x_{1}, y_{1})$ and top-right $(x_{2}, y_{2})$ vertices of the plot. The order in which the plots are provided in the output does not matter—Bajtazar will know which plot to assign to which son.

Examples

Input 1

6 5
..x..x
..x...
....x.
xx.x.x
......
......

Output 1

0 0 3 4
0 4 5 5
5 4 6 6
3 0 6 4
0 5 5 6