비대화형 숫자 맞히기

Romanos: “대화형 문제를 공모전에 낼 수 있을까요?”

Theodora: “안 돼요.”

Romanos: “아쉬운데요.”

그래서 Romanos는 비대화형 버전을 냈다. Theodora는 먼저 $1$ 이상 $N$ 이하의 정수 하나를 정한다. Romanos는 최대 $K$번까지 추측할 수 있다. 각 추측에 대해 Theodora는 자신의 수가 추측보다 작으면 $<$, 크면 $>$, 같으면 $=$이라고 답한다. Romanos가 정답을 맞히면 게임이 즉시 끝나고, $K$번 모두 틀리면 거기서 끝난다.

Romanos는 항상 최선을 다하지는 않지만 어리석은 추측은 하지 않는다. 모든 추측은 $1$ 이상 $N$ 이하이며 이전의 모든 답변과 모순되지 않는다. 예를 들어 $N = 10$이고 첫 추측이 $4$인데 답이 $<$라면 다음 추측은 항상 $1$ 이상 $3$ 이하이다.

반대로 Theodora는 Romanos를 이기려고 하며, 이전 답변과 모순되지 않는 한 숨긴 수를 바꾸면서 답한다. $<$ 또는 $>$로 답할 수 있을 때마다 남은 가능한 수의 집합이 더 크게 남는 쪽을 답한다. 양쪽 크기가 같으면 항상 $<$라고 답한다. 예를 들어 $N = 10$이고 첫 추측이 $4$라면 $1$부터 $3$보다 $5$부터 $10$이 더 크므로 항상 $>$라고 답한다.

$N$, $K$와 Theodora의 답변 sequence가 주어진다. 두 사람의 규칙과 모두 모순되지 않는 Romanos의 추측 sequence를 하나 출력하거나, 그런 sequence가 없으면 $-1$을 출력하라.

첫째 줄에 두 정수 $N$과 $K$ ($1 ≤ N ≤ 10^{18}$, $1 ≤ K ≤ 50000$)가 주어진다. 수의 범위와 최대 추측 횟수이다.

둘째 줄에 Theodora의 답변 문자열 $S$가 주어진다. 각 문자는 $<$, $>$, $=$ 중 하나이며 다음 중 하나를 만족한다.

• 마지막 문자가 $=$이고 나머지 문자는 모두 $<$ 또는 $>$이며, $S$의 길이는 $K$ 이하이다.
• 모든 문자가 $<$ 또는 $>$이며, $S$의 길이는 정확히 $K$이다.

$M$을 $S$의 길이라고 하자.

• 규칙과 모순되지 않는 추측 sequence가 존재하면 $M$개의 정수 $A_1, A_2, ..., A_M$을 한 줄에 출력한다. $A_i$는 $i$번째 추측이다. 여러 개가 있으면 아무거나 출력한다.
• 존재하지 않으면 한 줄에 $-1$을 출력한다.