Increasing List

Time limit2sMemory limit128 MB

Summary

Replace every '?' in a string with a digit or comma to form the lexicographically smallest strictly increasing list of positive integers with no leading zeros, or print -1 if impossible.

Level: Hard8 of 10
Topics: Backtracking, Greedy, String, Dynamic programming
Solved: No attempts yet

Problem

A string represents an increasing list if every comma-separated item is a positive integer, no item starts with 0, and each number is strictly larger than the one before it.

You are given a string consisting only of digits, commas, and question marks. Replace each question mark with either one digit or one comma so that the resulting string is an increasing list. If several results are possible, print the lexicographically smallest one. In this lexicographic order, the comma , comes before the digits 0 through 9.

Input

The first line contains a string made only of digits, commas, and question marks. Its length is at most 50.

Output

Print the lexicographically smallest possible resulting string. If it is impossible, print -1.

Examples7

Example 1
Input
```
?????????,9
```
Expected output
```
1,2,3,4,5,9
```
Example 2
Input
```
??
```
Expected output
```
10
```
Example 3
Input
```
???
```
Expected output
```
1,2
```
Example 4
Input
```
??????????,9
```
Expected output
```
-1
```
Example 5
Input
```
?,10,?????????????????,16,??
```
Expected output
```
-1
```
Example 6
Input
```
?2?5??7?,??
```
Expected output
```
12,50,70,71
```

Example 7

Input

???????????????????????????????,???

Expected output

1,10,11,100,101,102,103,104,105,106