Ghent University (UGent) was founded on October 9, 1817 in the city hall of Ghent, Belgium. Many activities were organized in 2017 to celebrate the 200th anniversary of the UGent. On this occasion, we have designed a prime number dedicated to Ghent University.

The prime number only contains the digits 1 and 8 — 9000 in total, as a reference to the postal code of Ghent, Belgium — but if you look carefully you'll also notice a single occurrence of the digit 2 in the prime number (marked in yellow in the figure above).

### Input

The input describes a rectangular image that has at least three rows and at least three columns. The image is constructed using three different characters: two of these characters each occur at least twice in the image and the other character occurs just once in the image.

The first line of input contains the two characters that each occur at least twice in the image. This is followed by lines that represent the rows of the image. Each row contains the same number of characters (corresponding to the number of columns of the image).

### Output

A line containing the text

character 's' only occurs at row r and column c

with the character that occurs just once in the image filling up the placeholder s. The index of the row (resp. column) where this character occurs in the image must replace the placeholder r (resp. c). Rows are indexed from top to bottom, and columns are indexed from left to right, starting at 1 in both cases.

### Example

In the sample input below, the character that occurs just once has been marked in yellow.

Input:

.8
...........................................
...........................................
....................88.....................
.................88888888..................
...............888888888888................
............888888......888888.............
.........888888............888888..........
......888888..................888888.......
....888888......................888888.....
....888............................888.....
...........................................
......888888888888888888888888888888.......
........88888888888888888888888888.........
...........................................
...........................................
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..82..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
........88..88..88..88..88..88..88.........
...........................................
...........................................
......888888888888888888888888888888.......
......888888888888888888888888888888.......
...........................................
....8888888888888888888888888888888888.....
....8888888888888888888888888888888888.....
...........................................
...........................................


Output:

character '2' only occurs at row 21 and column 30


### Epilogue

The design of the Ghent University prime number has been inspired by this video published by Numberphile1.

The video features a startling wall hanging in the Senior Combination Room at Trinity Hall2, Cambridge. Junior research fellow James McKee devised a 1350-digit prime number whose image forms a likeness of the college's coat of arms. The number of digits is significant, as it's the year that Bishop William Bateman3 founded the college.

It turns out that finding such "prime" images is easier than one might think. In the video description, McKee explains:

Most of the digits of $$p$$ were fixed so that i) the top two thirds made the desired pattern and ii) the bottom third ensured that $$p - 1$$ had a nice large (composite) factor $$F$$ with the factorisation of $$F$$ known. Numbers of this shape can easily be checked for primality. A small number of digits (you can see which!) were looped over until $$p$$ was found that was prime.

This inspired Cambridge math student Jack Hodkinson to publish his own prime number, this one presenting an image4 of Corpus Christi College5 and including his initials and date of birth.

To design the Ghent University prime number, we started from the logo that was used to celebrate the 200th anniversary of Ghent University.

This logo has then been converted into an ASCII image containing 9000 digits (as a reference to the postal code of the city of Ghent, Belgium), split over 75 rows containing 120 ones and eights each. We selected Bimini as a font to represent the prime number, because it gave good contract between the "heavy" eights (representing the blue pixels) and the "light" ones (representing the white pixels). Luckily, the bottom right pixel was white, because the prime number we had in mind could impossibly be even.

We then wrote a Python program to convert this initial number — which showed the pattern we had in mind, but wasn't a prime number yet — into a prime number. To do so, the program systematically iterated over all eights in the initial number, replaced the eight by another digit (not 1 or 8), and checked if the resulting number was prime. To quickly check if a 9000-digit number is prime, we used the Miller-Rabin primality test6. This algorithm is always correct in saying that a given number is not prime, but it can only state with (very) high probability that a given number is prime. To finally check that a candidate prime number was indeed prime, we used Dario Alpern's fantastic tool7 to give ourselves absolute certainty.

How were we so confident that this would work? Well, the prime number theorem8 tells us that there are approximately $$\frac{n}{\log{n}}$$ primes less than $$n$$. So there are approximately $\frac{10^{9000}}{\log{10^{9000}}} - \frac{10^{8999}}{\log{10^{8999}}} \approx 4.34 \times 10^{8995}$ 9000-digit primes. So, approximately one in every 21.000 9000-digit numbers is prime. Of course, we haven't calculated these estimates at the back of an envelope, as we also had Python to the rescue here (the module Decimal provides support for fast correctly-rounded decimal floating point arithmetic).

>>> from decimal import Decimal
>>> n = Decimal(10 ** 9000)
>>> m = Decimal(10 ** 8999)
>>> estimate = lambda x : x / x.ln()
>>> primes_with_9000_digits = estimate(n) - estimate(m)
>>> primes_with_9000_digits
Decimal('4.342891196471751863968210190E+8995')
>>> numbers_with_9000_digits = 9 * m
>>> numbers_with_9000_digits / primes_with_9000_digits
Decimal('20723.52171132395093158056936')


The even numbers were left out of consideration in advance, reducing half of the search space. We could also skip the digits 0, 3, 6 and 9 as replacements for one of the eights, since the combination with 7660 ones and 1339 eights would always result in a multiple of three. This only left us with the digits 2, 4, 5 and 7 that needed to be considered as replacements for one of the eights.

Searching our prime number would definitely not be as time consuming as looking for the proverbial needle in a haystack. But if you take into account that it takes a couple of minutes to figure out if a 9000-digit number is prime, it could have easily taken us more than a month to find our prime number. Luckily, we also had the Ghent University supercomputer9 at our disposal (thanks to the collaboration with the Flemish Supercomputer Centre10) to check many numbers at the same time. In the end, the 2942nd number checked turned out to be prime, so that our rudimentary prediction from above even proved to be a slight overestimation.