C. Up and down
time limit per test
1 second
memory limit per test
256 megabytes
input
stdin
output
stdout

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.

Input

The 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  > .

Output

Print one line containing your reconstruction of Baška's original sequence — N space-separated integers. If no such sequence exists, print N times  - 1.

Examples
Input
5 1000000000
><=>
Output
1 0 1 1 0
Input
4 2
»>
Output
-1 -1 -1 -1
Note

There are 10 sets of tests, in which the following restrictions hold:

gt; and no  =  in the sequence.
Set(s) no.Length of sequenceSize of elementsOther
1,62 ≤ N ≤ 10M = 109There's exactly one
2,72 ≤ N ≤ 20M = 109
3,82 ≤ N ≤ 1000M = 998
4,92 ≤ N ≤ 750000 ≤ M ≤ 109There's no  =  in the sequence.
5,102 ≤ N ≤ 2500000 ≤ M ≤ 109