Hidden Roman Numerals

Time limit1sMemory limit1024 MB

Summary

Find which of the twelve Roman numerals from 1 to 12 appear as substrings of a given string over {I,V,X}.

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

Problem

Bronius is learning the Roman numerals from 1 to 12. These numbers can be written using only three symbols — I, V, and X — as follows:

1	2	3	4	5	6	7	8	9	10	11	12
I	II	III	IV	V	VI	VII	VIII	IX	X	XI	XII

For practice, Bronius wrote on the board a random string $s_1 s_2 \dots s_N$ of length $N$ made up of the symbols I, V, and X. He then looks for the Roman numerals from 1 to 12 that are hidden in the string. A number is hidden in the string if its Roman representation appears as a contiguous substring. For example, the string XIIIX hides the numbers 1, 2, 3, 9, 10, 11, 12.

Find all numbers from 1 to 12 that are hidden in the string Bronius wrote.

Input

The first line contains a positive integer $N$ , the length of the string.

The second line contains the $N$ symbols $s_i$ with no spaces. Each symbol is one of I, V, or X.

Output

Print, on a single line, all numbers hidden in the string in increasing order, separated by spaces.

Constraints

$1 \le N \le 100$
$s_i \in \{\text{I}, \text{V}, \text{X}\}$

Examples5

Example 1
Input
```
5
XIIIX
```
Expected output
```
1 2 3 9 10 11 12
```
Example 2
Input
```
1
I
```
Expected output
```
1
```
Example 3
Input
```
1
V
```
Expected output
```
5
```
Example 4
Input
```
1
X
```
Expected output
```
10
```
Example 5
Input
```
4
VIII
```
Expected output
```
1 2 3 5 6 7 8
```