Problem4123--USACO 2019 US Open Contest, Silver Problem 1. Left Out

4123: USACO 2019 US Open Contest, Silver Problem 1. Left Out

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Farmer John is attempting to take a photograph of his herd of cows. From past experience, he knows this particular endeavor never usually ends well.

This time, Farmer John has purchased an expensive drone in order to take an aerial photo. To make the photo look as good as possible, he wants his cows all to be facing the same direction when the photo is taken. The cows are currently arranged in an N×NN×N grid (2≤N≤10002≤N≤1000) inside a fenced-in square pasture, for example: 

RLR
RRL
LLR

Here, an 'R' means a cow facing right, and an 'L' means a cow facing left. Since the cows are packed together, Farmer John cannot walk up to an individual cow to make it turn around. All he can do is shout at any row or column of cows to turn around, causing L's to change to R's and R's to L's within the row or column in question. Farmer John can yell at as many rows or columns as he wants, even at the same row or column more than once.

As expected, Farmer John observes that he is unable to make his cows all face one common direction. The best he can do is get all but one of the cows to face the same direction. Please determine the identity of such a cow.



Input

INPUT FORMAT (file leftout.in):

The first line contains NN. The next NN lines describe rows 1…N1…N in the grid of cows, each containing a string of length NN.



Output

OUTPUT FORMAT (file leftout.out):

Print the row and column index of a cow such that if that cow were flipped, Farmer John could make all his cows face the same direction. If no such cow exists, print -1. If multiple such cows exist, print the one with the smallest row index, or if multiple such cows have the same smallest row index, print the one with the smallest column index.

Sample Input Copy 

SAMPLE INPUT:
3
RLR
RRL
LLR

Sample Output Copy 

SAMPLE OUTPUT:
1 1

In the example above, the cow in row 1, column 1 (the upper-left corner) is the offending cow, since Farmer John can shout at row 2 and column 3 to make all other cows face left, with just this cow facing right.

Source/Category

USACO Silver 
[Submit] [Status]