Non-Interactive Guessing Number

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.

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

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.