Under construction

Still being built. Things may change

Overwatch World Cup

Interview

Time limit2sMemory limit512 MB

Summary
One seat in an N by N grid breaks the rule that every row and column holds each team once; find the seat and the correct shirt.
Level

Medium4 of 10

Topics
Implementation, Hash map
Solved
No attempts yet

Problem

You went to the Overwatch World Cup with your friends. The best Overwatch players from every country gathered there to decide who is the strongest.

The matches are fun, and cheering from the stands is just as fun. The stands at this tournament have an unusual shape: they form a square, and each side seats exactly as many people as there are teams in the tournament. Every spectator wears the shirt of the team they support.

The stands have one more rule. Each row and each column must seat exactly one fan of every team. Everyone looked like they had followed the rule, but one spectator came wearing the wrong shirt. Given the seating chart and the shirt each spectator wears, find the seat of that spectator and the team shirt they should have worn.

Input

The input holds several test cases and continues to the end of the file.

The first line of each test case has the number of teams in the tournament, NN (3≤N≤263 \le N \le 26). The next NN lines give the seating from the top row down. Each line is a string of length NN, and its jj-th character is the team shirt worn by the spectator in the jj-th seat of that row. A team is written as an uppercase letter from A to Z.

Exactly one spectator in each test case wears the wrong shirt. That shirt may belong to a team that is not in the tournament.

Output

For each test case, print RR, CC and VV on one line, separated by single spaces.

RR is the row number and CC is the column number of the seat where the spectator with the wrong shirt sits, counting rows and columns from 1. VV is the team whose shirt that spectator should have worn.

Examples2

  1. Example 1

    Input
    6
    OEYCDK
    EYOKCD
    KDCEOY
    CKHOYE
    YOEDKC
    DCKYEO
    3
    IWL
    GIW
    WLI
    
    Expected output
    4 3 D
    2 1 L
    
  2. Example 2

    Input
    3
    OLH
    LHG
    HGL
    
    Expected output
    1 1 G