КУБЧЕТА

Time limit0.1sMemory limit1024 MB

Summary

Given n cubes, each with six digits, arrange them in a row so the top faces form numbers; find the smallest positive integer (no leading zeros) that cannot be formed.

Level: Medium7 of 10
Topics: Greedy, Sorting, Implementation, Math
Solved: No attempts yet

Problem

There are n cubes. On each face of every cube, a single digit between 0 and 9 is written. Some cubes may have repeated digits.

The cubes can be placed side by side in a row, and the digits on their top faces then form an n-digit number.

Write a program kub that finds the smallest natural number that cannot be formed this way. The number being sought must not have leading zeros.

Input

The first line contains the number n (1 ≤ n ≤ 100 000).

The next n lines each contain six digits written one after another with no spaces between them: the digits of each cube, in arbitrary order.

Output

Print the smallest number being sought.

Examples3

Example 1
Input
```
2
012345
098765
```
Expected output
```
11
```
Example 2
Input
```
3
123456
789012
345678
```
Expected output
```
90
```
Example 3
Input
```
5
111111
222222
333333
444444
555555
```
Expected output
```
6
```