Problem: 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 ≤ x ≤ 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 ≤ y ≤ m). The correct answer to the question is -1, if x<y, 0, if x=y, and 1, if x>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, …, (n-1)-th, n-th, 1-st, 2-nd, 3-rd, …, (n-1)-th, n-th, …. 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).

Input

The first line contains two integers m and n (1 ≤ m ≤ 10^9, 1 ≤ n ≤ 30) — the maximum distance to Mars and the number of elements in the sequence p.

Interaction

You can ask the rocket no more than 60 questions.

To ask a question, print a number y (1≤ y≤ m) and an end-of-line character, then do the operation flush and read the answer to the question.

If the program reads 0, then the distance is correct and you must immediately terminate the program (for example, by calling exit(0)). If you ignore this, you can get any verdict, since your program will continue to read from the closed input stream.

If at some point your program reads -2 as an answer, it must immediately end (for example, by calling exit(0)). You will receive the "Wrong answer" verdict, and this will mean that the request is incorrect or the number of requests exceeds 60. If you ignore this, you can get any verdict, since your program will continue to read from the closed input stream.

If your program's request is not a valid integer between -2^{31} and 2^{31}-1 (inclusive) without leading zeros, then you can get any verdict.

You can get "Idleness limit exceeded" if you don't print anything or if you forget to flush the output.

To flush the output buffer you can use (after printing a query and end-of-line):

  * fflush(stdout) in C++;
  * System.out.flush() in Java;
  * stdout.flush() in Python;
  * flush(output) in Pascal;
  * See the documentation for other languages.



Hacking

Use the following format for hacking:

In the first line, print 3 integers m,n,x (1≤ x≤ m≤ 10^9, 1≤ n≤ 30) — the maximum distance to Mars, the number of elements in the sequence p and the current distance to Mars.

In the second line, enter n numbers, each of which is equal to 0 or 1 — sequence p.

The hacked solution will not have access to the number x and sequence p.

Example

Input

5 2
1
-1
-1
1
0


Output

1
2
4
5
3

Note

In the example, hacking would look like this:

5 2 3

1 0

This means that the current distance to Mars is equal to 3, Natasha knows that it does not exceed 5, and the rocket answers in order: correctly, incorrectly, correctly, incorrectly ...

Really:

on the first query (1) the correct answer is 1, the rocket answered correctly: 1;

on the second query (2) the correct answer is 1, the rocket answered incorrectly: -1;

on the third query (4) the correct answer is -1, the rocket answered correctly: -1;

on the fourth query (5) the correct answer is -1, the rocket answered incorrectly: 1;

on the fifth query (3) the correct and incorrect answer is 0.

Solution (in JAVA):

Solution:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * #
 * @author pttrung
 */
public class D_Round_499_Div2 {

    public static long MOD = 1000000007;  

    public static void main(String[] args) throws FileNotFoundException {
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File(
        // "output.txt")));
        PrintWriter out = new PrintWriter(System.out);
        Scanner in = new Scanner(); 
        int m = in.nextInt();
        int n = in.nextInt();
        boolean ok = false;
        boolean[]check = new boolean[n];
        for(int i = 0; i < n; i++){
            System.out.println(m);
            int v = in.nextInt();
            if(v == 0){
                ok = true;
                break;
            }
            if(v == -1){
                check[i] = true;
            }            
        }
        if(!ok){
            long st = 1;
            long ed = m;
            int index  =0;
            while(st <= ed){
                long mid = (st + ed)/2;
                System.out.println(mid);
                int v = in.nextInt();
                if(!check[index]){
                    v = -v;
                }
                if(v < 0){
                    ed = mid - 1;
                }else if(v > 0){
                    st = mid + 1;
                }else{
                    break;
                }
                index = (index + 1) % n;
            }
        }
        out.close();
    }

    public static int[] KMP(String val) {
        int i = 0;
        int j = -1;
        int[] result = new int[val.length() + 1];
        result[0] = -1;
        while (i < val.length()) {
            while (j >= 0 && val.charAt(j) != val.charAt(i)) {
                j = result[j];
            }
            j++;
            i++;
            result[i] = j;
        }
        return result;

    }

    public static boolean nextPer(int[] data) {
        int i = data.length - 1;
        while (i > 0 && data[i] < data[i - 1]) {
            i--;
        }
        if (i == 0) {
            return false;
        }
        int j = data.length - 1;
        while (data[j] < data[i - 1]) {
            j--;
        }
        int temp = data[i - 1];
        data[i - 1] = data[j];
        data[j] = temp;
        Arrays.sort(data, i, data.length);
        return true;
    }

    public static int digit(long n) {
        int result = 0;
        while (n > 0) {
            n /= 10;
            result++;
        }
        return result;
    }

    public static double dist(long a, long b, long x, long y) {
        double val = (b - a) * (b - a) + (x - y) * (x - y);
        val = Math.sqrt(val);
        double other = x * x + a * a;
        other = Math.sqrt(other);
        return val + other;



    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int start, int end) {
            this.x = start;
            this.y = end;
        }

        @Override
        public int hashCode() {
            int hash = 5;
            hash = 47 * hash + this.x;
            hash = 47 * hash + this.y;
            return hash;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final Point other = (Point) obj;
            if (this.x != other.x) {
                return false;
            }
            if (this.y != other.y) {
                return false;
            }
            return true;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(x, o.x);
        }
    }

    public static class FT {

        long[] data;

        FT(int n) {
            data = new long[n];
        }

        public void update(int index, long value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public long get(int index) {
            long result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

    public static long pow(long a, long b, long MOD) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2, MOD);
        if (b % 2 == 0) {
            return val * val % MOD;
        } else {
            return val * (val * a % MOD) % MOD;


        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}