Placing the Cards

Interview

Time limit2sMemory limit512 MB

Summary

Given the top view of overlapping rectangular cards, find the placement order that produces it, choosing the lexicographically smallest valid order.

Level: Medium7 of 10
Topics: Graph, Topological sort, Greedy, Implementation
Solved: No attempts yet

Problem

Yeongseon places rectangular cards on a grid, one card at a time. No two cards have the same color, and the cards can differ in size.

Every card is placed with its sides parallel to the sides of the grid, so one card covers a rectangular block of grid cells exactly. Cards can overlap, and a card placed later hides the cards beneath it. No card ends up completely hidden, so every card has at least one cell that is visible from above.

You are given the view from above after all the cards have been placed. Write a program that finds the order in which the cards were placed.

Input

The first line contains the grid size $N$ and $M$ . ( $1 \le N, M \le 50$ )

Each of the next $N$ lines contains $M$ characters describing one row of the view from above. Each character is the color of the card visible in that cell, and it is a lowercase letter 'a'-'z', an uppercase letter 'A'-'Z', or a digit '0'-'9'. A '.' is a cell that no card covers. At least one cell shows a card.

Output

On the first line, print the colors of the cards in the order they were placed, with no separator. If several orders are possible, print the lexicographically smallest one. Characters compare in the order digits '0'-'9', then uppercase letters 'A'-'Z', then lowercase letters 'a'-'z'. If no order produces the given view, print -1.

Examples3

Example 1
Input
```
3 6
..AA..
.CAAC.
.CAAC.
```
Expected output
```
CA
```
Example 2
Input
```
2 6
..47..
..74..
```
Expected output
```
-1
```

Example 3

Input

5 6
bbb666
.655X5
a65AA5
a65AA5
a65555

Expected output

65AXab