Non-Interactive Guessing Number

Time limit2sMemory limit512 MB

Summary

Given N, K, and Theodora's answer string, output guess values that follow the rules, or -1 if impossible.

Level: Hard8 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Problem

Romanos: “Can I submit an interactive problem to the contest?”

Theodora: “No.”

Romanos: “Aww, that is not fun.”

So Romanos submitted this non-interactive version instead. Theodora first chooses an integer between $1$ and $N$ inclusive. Romanos may make up to $K$ guesses. For each guess, Theodora answers $<$ if her number is smaller than the guess, $>$ if her number is larger than the guess, and $=$ if the guess is correct. The game ends immediately when Romanos guesses correctly, or after $K$ wrong guesses.

Romanos does not always play optimally, but he never makes a silly guess. Every guess lies between $1$ and $N$ inclusive and is consistent with all previous answers. For example, if $N = 10$ and his first guess is $4$ and the answer is $<$ , his next guess is always between $1$ and $3$ inclusive.

Theodora plays to make Romanos lose and changes her hidden number adaptively whenever it stays consistent with her previous answers. Whenever she can answer $<$ or $>$ , she chooses the answer that leaves the larger set of possible numbers. If both sides leave the same number of possibilities, she answers $<$ . For example, if $N = 10$ and the first guess is $4$ , she answers $>$ because $5$ to $10$ inclusive is larger than $1$ to $3$ inclusive.

You are given $N$ , $K$ , and the sequence of Theodora's answers. Output any guess sequence by Romanos that is consistent with the rules of both players, or $-1$ if no such sequence exists.

Input

The first line contains two integers $N$ and $K$ ( $1 ≤ N ≤ 10^{18}$ , $1 ≤ K ≤ 50000$ ), the range of numbers and the maximum number of guesses.

The second line contains a string $S$ of Theodora's answers. Each character is one of $<$ , $>$ , $=$ , and either:

the last character is $=$ , every other character is $<$ or $>$ , and the length of $S$ is at most $K$ , or
every character is $<$ or $>$ , and the length of $S$ is exactly $K$ .

Output

Let $M$ be the length of $S$ .

If a guess sequence consistent with the rules exists, output $M$ integers $A_1, A_2, ..., A_M$ in one line, where $A_i$ is the $i$ -th guess. If several sequences exist, output any of them.
Otherwise output $-1$ in one line.

Examples5

Example 1
Input
```
10 5
><>=
```
Expected output
```
5 8 6 7
```
Example 2
Input
```
10 5
><<><
```
Expected output
```
1 10 9 2 8
```
Example 3
Input
```
10 5
<>=
```
Expected output
```
-1
```
Example 4
Input
```
10 9
>>>>>>>>>
```
Expected output
```
1 2 3 4 5 6 7 8 9
```
Example 5
Input
```
10 10
>>>>>>>>>>
```
Expected output
```
-1
```