Easy as ABC

Time limit2sMemory limit1024 MB

Summary

Find the lexicographically smallest 3-letter word spelled by three distinct cells in a 3x3 grid of A, B, and C, where each consecutive pair of cells is adjacent.

Level: Easy2 of 10
Topics: Brute force, Implementation
Solved: No attempts yet

Problem

You are playing a word puzzle. The puzzle starts with a $3$ by $3$ grid, where each cell contains either the letter A, B, or C.

The goal is to find the lexicographically smallest word of length $3$ that you can form in the grid. Choose three different cells. The cell holding the first letter must be adjacent to the cell holding the second letter, and the cell holding the second letter must be adjacent to the cell holding the third letter.

Two cells are adjacent if they share a border or a corner, as shown in the following illustration. Formally, cell $(r, c)$ is adjacent to cells $(r, c + 1)$ , $(r - 1, c + 1)$ , $(r - 1, c)$ , $(r - 1, c - 1)$ , $(r, c - 1)$ , $(r + 1, c - 1)$ , $(r + 1, c)$ , and $(r + 1, c + 1)$ .

Input

The input consists of three lines. Each line contains three letters that represent the grid. Every letter is A, B, or C.

Output

Output the lexicographically smallest word of length $3$ that you can find in the grid.

Examples5

Example 1
Input
```
BCB
CAC
BCB
```
Expected output
```
ABC
```
Example 2
Input
```
BCB
CCC
CCA
```
Expected output
```
ACB
```
Example 3
Input
```
ACA
CBC
ACA
```
Expected output
```
ABA
```
Example 4
Input
```
ACA
CAC
ACA
```
Expected output
```
AAA
```
Example 5
Input
```
CCC
CBC
CCC
```
Expected output
```
BCC
```