401926: GYM100584 C Up and down
Description
Baška had a sequence of N integers from the range [0, M]. For every 2 consecutive elements of the sequence, she wrote down < , = or > depending on the earlier one of them being lesser, equal or greater than the later one. For example, as for a sequence (3, 1, 7, 7, 4) we have 3 > 1 < 7 = 7 > 4, Baška would've written down > < = > .
Olívia doesn't know Baška's original sequence. She only knows N, M and the sequence of characters that Baška wrote down. Now, she'd like to reconstruct Baška's sequence — as far as possible.
Find one such sequence with minimal sum or decide that it doesn't exist. If there are multiple correct sequences with minimal sum, find any one of them.
InputThe input consists of 2 lines. The first contains integers N and M; the second contains the sequence that Baška wrote down - a string of N - 1 characters < , = or > .
OutputPrint one line containing your reconstruction of Baška's original sequence — N space-separated integers. If no such sequence exists, print N times - 1.
ExamplesInput5 1000000000Output
><=>
1 0 1 1 0Input
4 2Output
»>
-1 -1 -1 -1Note
There are 10 sets of tests, in which the following restrictions hold:
| Set(s) no. | Length of sequence | Size of elements | Other |
| 1,6 | 2 ≤ N ≤ 10 | M = 109 | There's exactly one | gt; and no = in the sequence.
| 2,7 | 2 ≤ N ≤ 20 | M = 109 | |
| 3,8 | 2 ≤ N ≤ 1000 | M = 998 | |
| 4,9 | 2 ≤ N ≤ 75000 | 0 ≤ M ≤ 109 | There's no = in the sequence. |
| 5,10 | 2 ≤ N ≤ 250000 | 0 ≤ M ≤ 109 |