This is an interactive problem.

Natasha is going to fly to Mars. Finally, Natasha sat in the rocket. She flies, flies... but gets bored. She wishes to arrive to Mars already! So she decides to find something to occupy herself. She couldn't think of anything better to do than to calculate the distance to the red planet.

Let's define $x$ as the distance to Mars. Unfortunately, Natasha does not know $x$. But it is known that $1 \le x \le m$, where Natasha knows the number $m$. Besides, $x$ and $m$ are positive integers.

Natasha can ask the rocket questions. Every question is an integer $y$ ($1 \le y \le m$). The correct answer to the question is $-1$, if $x&lt;y$, $0$, if $x=y$, and $1$, if $x&gt;y$. But the rocket is broken — it does not always answer correctly. Precisely: let the correct answer to the current question be equal to $t$, then, if the rocket answers this question correctly, then it will answer $t$, otherwise it will answer $-t$.

In addition, the rocket has a sequence $p$ of length $n$. Each element of the sequence is either $0$ or $1$. The rocket processes this sequence in the cyclic order, that is $1$-st element, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $1$-st, $2$-nd, $3$-rd, $\ldots$, $(n-1)$-th, $n$-th, $\ldots$. If the current element is $1$, the rocket answers correctly, if $0$ — lies. Natasha doesn't know the sequence $p$, but she knows its length — $n$.

You can ask the rocket no more than $60$ questions.

Help Natasha find the distance to Mars. Assume, that the distance to Mars does not change while Natasha is asking questions.

Your solution will not be accepted, if it does not receive an answer $0$ from the rocket (even if the distance to Mars is uniquely determined by the already received rocket's answers).
The first line contains two integers $m$ and $n$ ($1 \le m \le 10^9$, $1 \le n \le 30$) — the maximum distance to Mars and the number of elements in the sequence $p$.
5 2 3
1 0
3 queries, x=3
1 1 1
1
1 queries, x=1
3 2 3
1 0
4 queries, x=3
6 3 5
1 1 1
5 queries, x=5
10 4 3
0 0 1 0
6 queries, x=3
30 5 16
0 1 1 1 0
6 queries, x=16
60 6 21
1 0 0 1 0 1
11 queries, x=21
100 7 73
0 0 0 1 0 1 1
14 queries, x=73
1000000000 29 958572235
1 1 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0
58 queries, x=958572235
738009704 30 116044407
0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1
59 queries, x=116044407
300 8 165
1 1 1 0 0 1 1 0
16 queries, x=165
600 9 150
0 0 1 0 1 0 1 0 1
19 queries, x=150
1000 10 140
0 0 0 0 1 0 0 0 0 0
20 queries, x=140
3000 11 1896
1 0 1 1 0 0 0 0 1 1 1
21 queries, x=1896
6000 12 4679
1 0 1 1 1 1 1 0 0 0 0 1
23 queries, x=4679
10000 13 4977
1 0 1 1 0 0 0 1 0 0 1 1 0
26 queries, x=4977
30000 14 60
1 1 1 0 0 1 0 1 0 0 1 0 0 0
28 queries, x=60
60000 15 58813
0 1 1 0 1 1 0 0 0 1 1 1 1 0 1
27 queries, x=58813
100000 16 79154
1 1 1 0 0 0 0 0 1 1 0 1 0 1 0 1
32 queries, x=79154
300000 17 11107
1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0
34 queries, x=11107
600000 18 146716
0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 1
37 queries, x=146716
1000000 19 418016
1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 0 0
38 queries, x=418016
3000000 20 642518
1 0 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 1 0 1
41 queries, x=642518
6000000 21 3516807
0 0 0 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0
43 queries, x=3516807
10000000 22 8115129
1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 1
42 queries, x=8115129
30000000 23 10362635
0 1 0 0 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 0 0
48 queries, x=10362635
60000000 24 52208533
1 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 1 0 1 1 1 0
46 queries, x=52208533
100000000 25 51744320
0 1 1 1 1 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 1 0 1 0 1
50 queries, x=51744320
300000000 26 264009490
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1
54 queries, x=264009490
600000000 27 415720732
1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 1 1 1 0 1 0 1 0
56 queries, x=415720732
1000000000 28 946835863
0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 1 0 1 1 0 0
58 queries, x=946835863
1000000000 29 124919287
0 0 1 0 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0
59 queries, x=124919287
1000000000 30 202669473
1 1 0 1 1 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 0 0
58 queries, x=202669473
1000000000 13 532121080
1 1 1 0 1 1 0 0 0 0 1 0 1
42 queries, x=532121080
1000000000 27 105669924
0 1 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 0 1 1 1 1
57 queries, x=105669924
1000000000 11 533994576
0 0 1 0 1 1 1 1 0 1 0
38 queries, x=533994576
1000000000 9 107543421
1 0 0 1 1 1 1 1 1
39 queries, x=107543421
1000000000 23 976059561
1 0 0 0 0 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1
53 queries, x=976059561
1000000000 7 549608406
1 1 1 0 1 1 1
36 queries, x=549608406
1000000000 21 123157250
0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 1
49 queries, x=123157250
1000000000 19 696706094
0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0
47 queries, x=696706094
1000000000 3 125030747
0 0 0
33 queries, x=125030747
1000000000 17 993546887
1 0 1 0 1 1 1 1 1 1 0 1 0 1 1 1 1
46 queries, x=993546887
1000000000 15 567095731
1 1 1 0 0 1 1 1 0 1 0 0 1 0 0
45 queries, x=567095731
1000000000 29 140644576
1 1 1 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 1 0 0
58 queries, x=140644576
1000000000 13 714193420
0 1 0 0 0 1 0 0 0 0 1 1 1
43 queries, x=714193420
1000000000 27 142518072
0 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0
52 queries, x=142518072
1000000000 25 11034213
0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 0 1 1 0 0 1 0 1 0 0
54 queries, x=11034213
1000000000 9 584583057
1 1 1 0 0 1 0 0 0
35 queries, x=584583057
1000000000 23 863164606
1 1 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1
53 queries, x=863164606
1000000000 21 731680746
1 1 0 0 1 1 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1
51 queries, x=731680746
1000000000 5 305229590
0 0 1 1 0
35 queries, x=305229590
1000000000 3 28521539
0 0 1
31 queries, x=28521539
1000000000 3 602070383
0 1 1
32 queries, x=602070383
1000000000 2 880651931
1 1
30 queries, x=880651931
1000000000 16 749168072
1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0
46 queries, x=749168072
1000000000 30 322716916
1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0
58 queries, x=322716916
1000000000 14 191233057
0 0 1 0 0 1 1 1 1 0 0 0 1 1
43 queries, x=191233057
1000000000 30 1
1 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0
1 queries, x=1
1000000000 30 1
1 0 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1
1 queries, x=1
1000000000 30 1
1 0 1 0 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1
1 queries, x=1
1000000000 30 1
1 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1
1 queries, x=1
1000000000 30 1
1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0
1 queries, x=1
1000000000 30 1000000000
1 1 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 1 0
60 queries, x=1000000000
1000000000 30 1000000000
1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 0 1 0 1 1 1 0
60 queries, x=1000000000
1000000000 30 1000000000
0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 1
60 queries, x=1000000000
1000000000 30 1000000000
0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1
60 queries, x=1000000000
1000000000 30 1000000000
0 0 0 1 1 1 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1
60 queries, x=1000000000
1 30 1
1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1
1 queries, x=1
1 30 1
1 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 0 0
1 queries, x=1
1 30 1
1 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 0 0 1 1 0 1 0 0 0
1 queries, x=1
1 30 1
1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0
1 queries, x=1
1 30 1
1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 1 1 0 1 1
1 queries, x=1
2 1 2
1
2 queries, x=2
1000000000 1 1000000000
1
31 queries, x=1000000000
10000 1 10000
1
15 queries, x=10000
1000000000 1 999999999
1
30 queries, x=999999999
100000 2 15
1 0
19 queries, x=15
200000 1 110000
1
17 queries, x=110000
123456789 1 42
1
27 queries, x=42
1000000000 1 9
1
30 queries, x=9
200000 2 100002
1 0
19 queries, x=100002
1000000000 3 234567890
0 1 0
31 queries, x=234567890
1000000000 5 321732193
1 1 0 1 0
35 queries, x=321732193
1000000000 1 804289384
1
27 queries, x=804289384
1000000000 2 999999998
1 0
32 queries, x=999999998
1000000000 5 384618761
0 1 1 0 1
33 queries, x=384618761
100000000 1 100
0
28 queries, x=100
1000000000 1 804289384
0
27 queries, x=804289384
100000000 1 100000000
1
28 queries, x=100000000
40 1 4
0
6 queries, x=4
1000000000 2 999999998
0 1
32 queries, x=999999998
1000000000 1 1000000000
0
31 queries, x=1000000000
1000000000 2 255555555
1 0
31 queries, x=255555555
1000000000 2 1000000000
0 1
32 queries, x=1000000000
1000000000 1 999999999
0
30 queries, x=999999999
1000000000 2 888888888
0 1
31 queries, x=888888888
1000000000 1 77000000
1
31 queries, x=77000000
1000000000 1 123456789
1
27 queries, x=123456789
10000 1 228
0
14 queries, x=228
1000000000 1 12345
1
31 queries, x=12345
1000000000 1 77000000
0
31 queries, x=77000000
1000000000 1 23333
0
31 queries, x=23333
1000000000 4 100
0 1 0 1
34 queries, x=100
100000000 1 200
1
27 queries, x=200
1000000000 3 5
0 1 0
33 queries, x=5
1000000000 12 2
1 1 1 1 1 1 0 0 1 1 1 1
41 queries, x=2
1000000000 1 5
0
31 queries, x=5
100000 2 99999
0 0
18 queries, x=99999
100000 2 2
0 1
18 queries, x=2
1000000 1 91923
0
21 queries, x=91923
1000000 2 1235
0 1
22 queries, x=1235
1000000000 1 5
1
31 queries, x=5
100000000 2 1234567
0 1
28 queries, x=1234567
1000000000 1 1
1
1 queries, x=1
1000000000 4 999999999
1 0 0 1
33 queries, x=999999999
1000000000 4 1000000000
1 0 1 0
34 queries, x=1000000000
1000000000 4 1
1 0 1 0
1 queries, x=1
1000000000 5 500
1 1 0 0 1
34 queries, x=500
1000 1 13
1
11 queries, x=13
999999999 2 123456789
1 0
31 queries, x=123456789
1000000000 5 1000000000
1 1 1 1 1
35 queries, x=1000000000
1000000000 3 123456789
1 0 1
29 queries, x=123456789
1000000000 1 123
1
29 queries, x=123
10 1 9
1
4 queries, x=9
1000000000 1 1
0
1 queries, x=1
100000000 2 12345678
0 1
28 queries, x=12345678
1000000000 30 1000000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
60 queries, x=1000000000
805306369 30 805306369
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
60 queries, x=805306369
1000000000 2 123
0 1
30 queries, x=123
1000000000 1 9
0
30 queries, x=9
100000 2 90000
1 0
18 queries, x=90000
1000000000 2 123456789
1 0
28 queries, x=123456789
1000000000 2 804289384
1 0
28 queries, x=804289384
1000000000 30 999999970
1 0 0 1 1 1 1 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 0 1
60 queries, x=999999970
from sys import stdout
n,m=map(int,input().split())

p=[]
for i in range(n):
    print(m)
    stdout.flush()
    s=input()
    if s=='0':
        exit()
    elif s=='-1':
        p.append(1)
    else:
        p.append(0)
l=0
r=m
while True:
    print((r+l)//2)
    stdout.flush()
    s=input()
    if s=='0':
        break
    elif s=='1':
        r=(l+r)//2
    else:
        l=(l+r)//2

