/**
 * Created by Adrian Dumitrache on 10/28/16.
 */

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.File;
import java.util.LinkedList;
import java.util.Queue;

public class Game {
    private final int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
    private final int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
    Character ch1;
    Character ch2;
    CityMap city;
    static final int INF = 1000000;

    /**
     *
     * @param args nu am argumente pentru main
     */
    public static void main(String[] args) {

        Game game = new Game();
        /**
         * citesc toate datele
         */
        game.readData();
        /**
         * construiesc matricea time pentru ch1 si ch2
         */
        game.play(game.ch1);
        game.play(game.ch2);

        Queue sol = new LinkedList();

        /**
         * valoarea de referinta pentru prima comparatie ce va fi inlaturata
         * daca exista solutie
         */
        Pos min = new Pos(INF, INF);
        min.setVal(INF);
        sol.add(min);
        boolean flag = false;

        for (int i = 0; i < game.getCity().getN(); i++) {
            for (int j = 0; j < game.getCity().getM(); j++) {
                /**
                 * daca valoare din matricea timpilor lui ch1 si cea a lui ch2
                 * este egala si nu are valoarea limita
                 */
                if (game.ch1.getTime()[i][j] == game.ch2.getTime()[i][j] &&
                        game.ch1.getTime()[i][j] < INF) {
                    /**
                     * daca valoarea de pe pozitia candidat este mai mica decat
                     * cea din fata cozii, atunci golesc coada si adaug pozitia
                     * curenta in coada
                     */
                    if (game.ch1.getTime()[i][j] <
                            ((Pos) sol.peek()).getVal()) {
                        while (!sol.isEmpty()) {
                            sol.remove();
                        }
                        min = new Pos(i, j);
                        min.setVal(game.ch1.getTime()[i][j]);
                        sol.add(min);
                        flag = true;
                    }
                    /**
                     * altfel, daca gasesc o valoare egala cu cea din fata cozii,
                     * atunci adaug pozitia respectiva de asemenea in coada
                     */
                    else if (game.ch1.getTime()[i][j] ==
                            ((Pos) sol.peek()).getVal()) {
                        /**
                         * doresc o referinta noua pentru a
                         * nu suprascrie pe cea veche
                         */
                        min = new Pos(i, j);
                        min.setVal(game.ch1.getTime()[i][j]);
                        sol.add(min);
                    }
                }
            }
        }


        BufferedWriter output = null;
        try {
            File file = new File("maze.out");
            output = new BufferedWriter(new FileWriter(file));
            if (flag == true) {
                while (!sol.isEmpty()) {
                    /**
                     * am adaugat 1 la coordonatele x si y deoarece am lucrat cu
                     * matrice indentate de la 0 la n-1 respectiv de la 0 la m-1
                     */
                    output.write(((Pos) sol.peek()).getVal() + " "
                            + (((Pos) sol.peek()).getX() + 1) + " "
                            + (((Pos) sol.peek()).getY() + 1) + "\n");

                    sol.remove();
                }
            } else {/**
                     * nu s-a adaugat nimic in coada in afara de valoarea
                     * initiala de compartie
                     */
                try {
                    output.write("INF\n");
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }


        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (output != null) {
                try {
                    output.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    /**
     *
     * @param ch1 seteaza primul caracter
     */
    private void setCh1(Character ch1) {
        this.ch1 = ch1;
    }

    /**
     *
     * @param ch2 seteaza al doilea caracter
     */
    private void setCh2(Character ch2) {
        this.ch2 = ch2;
    }

    /**
     *
     * @return returneaza harta orasului de tip CityMap
     */
    protected CityMap getCity() {
        return city;
    }

    /**
     * citesc datele din "maze.in"
     */
    protected void readData() {

        FileReader fr = null;
        try {
            fr = new FileReader("maze.in");
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
        BufferedReader br = new BufferedReader(fr);
        String line = null;
        try {
            line = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        /**
         * am citit prima linie si o voi imparti in cuvinte
         * (ce reprezinta numere)
         */
        String[] noInStringArr;
        noInStringArr = line.split(" ");

        /**
         * setez dimensiunile citite pentru matricea city
         */
        city = new CityMap(Integer.parseInt(noInStringArr[0]),
                Integer.parseInt(noInStringArr[1]));

        /**
         * citesc restul liniilor matricei
         */
        for (int i = 0; i < city.getN(); i++) {
            try {
                line = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            for (int j = 0; j < city.getM(); j++) {
                setElem(i, j, line.charAt(j));
            }
        }
    }

    /**
     *
     * @param i linia i
     * @param j coloana j
     * @param val valoarea val
     *            in matricea city pe pozitia (i,j) pun true daca e perete
     *            si false daca e liber sau se se afla Romeo/Julieta acolo
     */
    protected void setElem(int i, int j, char val) {
        if (val == 'X') {
            city.getMap()[i][j] = true;
        } else {
            city.getMap()[i][j] = false;
        }

        if (val == 'R') {
            Character ch =
                    new Character("Romeo", i, j, city.getN(), city.getM());
            setCh1(ch);
        }

        if (val == 'J') {
            Character ch =
                    new Character("Julieta", i, j, city.getN(), city.getM());
            setCh2(ch);
        }
    }

    /**
     *
     * @param ch caracterul pentru care construiesc matricea de timpi
     * Algoritmul lui Lee (Parcurgere in latime)
     */
    private void play(Character ch) {
        Queue Q = new LinkedList();

        /**
         * now reprezinta pozitia curenta
         */
        Pos now = new Pos(ch.getX(), ch.getY());
        Q.add(now);

        while (!Q.isEmpty()) {
            now.setX(new Integer(((Pos) Q.peek()).getX()));
            now.setY(new Integer(((Pos) Q.peek()).getY()));
            Q.remove();
            /**
             * pentru tote cele 8 directii posibile
             */
            for (int i = 0; i < 8; i++) {
                Pos newPosition = new Pos(now.getX() + dx[i],
                        now.getY() + dy[i]);

                /**
                 * daca ies din matrice nu ma mai duc in acea directie
                 */
                if (!city.inLimits(newPosition.getX(), newPosition.getY()))
                    continue;

                /**
                 * daca pe noua pozitie este un perete nu ma mai duc pe acolo
                 */
                if (city.getMap()[newPosition.getX()][newPosition.getY()])
                    continue;

                /**
                 * altfel, daca nu e perete
                 * daca pe noua pozitie e o valoare mai mare decat valoarea de
                 * pe vechea pozitie + 1
                 */

                if (ch.getTime()[newPosition.getX()][newPosition.getY()] >
                        ch.getTime()[now.getX()][now.getY()] + 1) {
                    /**
                     * update pe noua pozitie cu valoarea de pe vechea pozitie +1
                     */
                    ch.getTime()[newPosition.getX()][newPosition.getY()] =
                            ch.getTime()[now.getX()][now.getY()] + 1;
                    /**
                     * adaug in stiva
                     */
                    Q.add(new Pos(newPosition.getX(), newPosition.getY()));
                }
            }
        }

    }
}