Tên lửa

Đây là một bài toán tương tác (interactive).

Một con tàu vũ trụ đang bay tới sao Hỏa. Gọi $x$ là khoảng cách còn lại tới sao Hỏa. Bạn không biết $x$, chỉ biết rằng $1\le x\le m$ với $m$ cho trước, và $x$ là số nguyên dương.

Bạn có thể hỏi máy tính của tàu. Mỗi câu hỏi là một số nguyên $y$ với $1\le y\le m$. Câu trả lời đúng cho câu hỏi này là:

• $-1$ nếu $x<y$;
• $0$ nếu $x=y$;
• $1$ nếu $x>y$.

Tiếc là máy tính đã hỏng nên không phải lúc nào cũng trả lời đúng. Cụ thể, nếu câu trả lời đúng là $t$ thì máy tính sẽ trả lời $t$ khi nó nói thật, và trả lời $-t$ khi nó nói dối.

Máy tính có một dãy $p$ gồm $n$ phần tử, mỗi phần tử bằng $0$ hoặc $1$. Nó duyệt dãy này theo vòng tròn: câu hỏi thứ nhất dùng $p_1$, câu hỏi thứ hai dùng $p_2$, …, câu hỏi thứ $n$ dùng $p_n$, câu hỏi thứ $n+1$ lại dùng $p_1$, và cứ thế tiếp tục. Nếu phần tử đang dùng bằng $1$ thì máy tính nói thật, nếu bằng $0$ thì nó nói dối. Bạn không biết dãy $p$, chỉ biết độ dài $n$ của nó.

Bạn được phép đặt tối đa $60$ câu hỏi. Khoảng cách $x$ không thay đổi trong suốt quá trình hỏi.

Lời giải của bạn chỉ được chấp nhận nếu thực sự nhận được câu trả lời $0$ từ máy tính, kể cả khi $x$ đã được xác định duy nhất từ các câu trả lời trước đó.

Nếu đọc được $0$, bạn phải kết thúc chương trình ngay lập tức. Nếu đọc được $-2$, nghĩa là câu hỏi không hợp lệ hoặc bạn đã vượt quá $60$ câu hỏi; khi đó cũng phải kết thúc chương trình ngay.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $m$ và $n$ — khoảng cách lớn nhất có thể tới sao Hỏa và độ dài của dãy $p$.

Sau mỗi câu hỏi, đọc một dòng chứa câu trả lời của máy tính: một trong các giá trị $-1$, $0$, $1$ hoặc $-2$.

Dữ liệu ra

Mỗi câu hỏi in trên một dòng: một số nguyên $y$ với $1\le y\le m$.

Sau mỗi lần in, bạn phải flush output (ví dụ cout << endl hoặc cout.flush() trong C++, flush=True trong Python).

Ràng buộc

• $1\le m\le {10}^9$
• $1\le n\le 30$
• $1\le x\le m$
• Tối đa $60$ câu hỏi

Ví dụ