Problem: This is an interactive problem.

This is a hard version of the problem. The difference from the easy version is that in the hard version 1 ≤ t ≤ min(n, 10^4) and the total number of queries is limited to 6 ⋅ 10^4.

Polycarp is playing a computer game. In this game, an array consisting of zeros and ones is hidden. Polycarp wins if he guesses the position of the k-th zero from the left t times.

Polycarp can make no more than 6 ⋅ 10^4 requests totally of the following type: 

  * ? l r — find out the sum of all elements in positions from l to r (1 ≤ l ≤ r ≤ n) inclusive. 



To make the game more interesting, each guessed zero turns into one and the game continues on the changed array. More formally, if the position of the k-th zero was x, then after Polycarp guesses this position, the x-th element of the array will be replaced from 0 to 1.

Help Polycarp win the game.

Interaction

First, your program must read two integers n and t (1 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ t ≤ min(n, 10^4)).

Then t lines follow, each of which contains one integer k (1 ≤ k ≤ n). It is guaranteed that at the moment of the request the array contains at least k zeros. In order to get the next value of k, you must output the answer for the previous value of k.

After that, you can make no more than 6 ⋅ 10^4 requests in total.

Use the following format to output the answer (it is not a request, it doesn't count in 6 ⋅ 10^4): 

  * ! x — position of the k-th zero. 



Positions in the array are numbered from left to right from 1 to n inclusive.

After printing t answers, your program should exit immediately.

In this task, the interactor is not adaptive. This means that within the same test, the hidden array and the queries do not change.

In case of an incorrect query, -1 will be displayed. When this value is received, your program must immediately exit normally (for example, by calling exit(0)), otherwise, the testing system may issue an arbitrary verdict.

If the number of requests is exceeded, the verdict wrong answer will be displayed.

Your solution may get the verdict Idleness limit exceeded if you don't print anything or forget to flush the output buffer.

To flush the output buffer, you need to do the following immediately after the query output and the end-of-line character:

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



Hacks

Use the following format for hacks:

On the first line print the string s (1 ≤ |s| ≤ 2 ⋅ 10^5), consisting of zeros and ones, and an integer t (1 ≤ t ≤ min(|s|, 10^4)) — hidden array and number of requests, respectively. In the next t lines output the number k (1 ≤ k ≤ |s|).

The hacked solution will not have direct access to the hidden array.

Example

Input


6 2

2

2

1

1

0

1

0

Output


? 4 6

? 1 1

? 1 2

? 5 5

! 5

? 2 2

! 2

Note

In the first test, the array [1, 0, 1, 1, 0, 1] is hidden. After answering the query k=2, the array changed to [1, 0, 1, 1, 1, 1].

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
public class F2 {
    static class Scan {
        private byte[] buf=new byte[1024];
        private int index;
        private InputStream in;
        private int total;
        public Scan()
        {
            in=System.in;
        }
        public int scan()throws IOException
        {
            if(total<0)
            throw new InputMismatchException();
            if(index>=total)
            {
                index=0;
                total=in.read(buf);
                if(total<=0)
                return -1;
            }
            return buf[index++];
        }
        public int scanInt()throws IOException
        {
            int integer=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n))
            {
                if(n>='0'&&n<='9')
                {
                    integer*=10;
                    integer+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            return neg*integer;
        }
        public double scanDouble()throws IOException
        {
            double doub=0;
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            int neg=1;
            if(n=='-')
            {
                neg=-1;
                n=scan();
            }
            while(!isWhiteSpace(n)&&n!='.')
            {
                if(n>='0'&&n<='9')
                {
                    doub*=10;
                    doub+=n-'0';
                    n=scan();
                }
                else throw new InputMismatchException();
            }
            if(n=='.')
            {
                n=scan();
                double temp=1;
                while(!isWhiteSpace(n))
                {
                    if(n>='0'&&n<='9')
                    {
                        temp/=10;
                        doub+=(n-'0')*temp;
                        n=scan();
                    }
                    else throw new InputMismatchException();
                }
            }
            return doub*neg;
        }
        public String scanString()throws IOException
        {
            StringBuilder sb=new StringBuilder();
            int n=scan();
            while(isWhiteSpace(n))
            n=scan();
            while(!isWhiteSpace(n))
            {
                sb.append((char)n);
                n=scan();
            }
            return sb.toString();
        }
        private boolean isWhiteSpace(int n)
        {
            if(n==' '||n=='\n'||n=='\r'||n=='\t'||n==-1)
            return true;
            return false;
        }
    }
    
    public static void sort(int arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(int arr[],int l1,int r1,int l2,int r2) {
        int tmp[]=new int[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    public static void sort(long arr[],int l,int r) {    //sort(arr,0,n-1);
        if(l==r) {
            return;
        }
        int mid=(l+r)/2;
        sort(arr,l,mid);
        sort(arr,mid+1,r);
        merge(arr,l,mid,mid+1,r);
    }
    public static void merge(long arr[],int l1,int r1,int l2,int r2) {
        long tmp[]=new long[r2-l1+1];
        int indx1=l1,indx2=l2;
        //sorting the two halves using a tmp array
        for(int i=0;i<tmp.length;i++) {
            if(indx1>r1) {
                tmp[i]=arr[indx2];
                indx2++;
                continue;
            }
            if(indx2>r2) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            if(arr[indx1]<arr[indx2]) {
                tmp[i]=arr[indx1];
                indx1++;
                continue;
            }
            tmp[i]=arr[indx2];
            indx2++;
        }
        //Copying the elements of tmp into the main array
        for(int i=0,j=l1;i<tmp.length;i++,j++) {
            arr[j]=tmp[i];
        }
    }
    
    
    static class seg_tree {
        int seg_tree[],lazy[];
        public seg_tree(int n,int arr[]) {
            seg_tree=new int[4*n];
            lazy=new int[4*n];
            built(arr,0,0,n-1);
        }

        public void built(int arr[], int vertex, int l,int r) {
            if(l==r) {
                seg_tree[vertex]=arr[r];
                return;
            }
            int mid=(l+r)/2;

            //Left Child
            built(arr,(2*vertex)+1, l, mid);

            //Right Child
            built(arr,(2*vertex)+2, mid+1, r);

            seg_tree[vertex]=seg_tree[(2*vertex)+1]+seg_tree[(2*vertex)+2];
        }

        public void push(int vertex,int l,int r) {
            int mid=(l+r)/2;
            int ll=l;
            int lr=mid;
            int rl=mid+1;
            int rr=r;
            seg_tree[(2*vertex)+1]+=(lr-ll+1)*lazy[vertex];
            lazy[(2*vertex)+1]+=lazy[vertex];
            seg_tree[(2*vertex)+2]+=(rr-rl+1)*lazy[vertex];
            lazy[(2*vertex)+2]+=lazy[vertex];
            lazy[vertex]=0;
        }

        public void update(int vertex,int l,int r,int ql,int qr,int add) {
            if(ql>qr) {
                return;
            }
            if(l==ql && r==qr) {
                seg_tree[vertex]+=(qr-ql+1)*add;
                lazy[vertex]+=add;
                return;
            }
            push(vertex,l,r);

            int mid=(l+r)/2;
            //Left Child
            update((2*vertex)+1,l,mid,ql,Math.min(mid,qr),add);
            //Right Child
            update((2*vertex)+2,mid+1,r,Math.max(mid+1,ql),qr,add);

            seg_tree[vertex]=seg_tree[(2*vertex)+1]+seg_tree[(2*vertex)+2];
        }

        public int sum(int vertex,int l,int r,int ql,int qr) {
            if(ql>qr) {
                return 0;
            }
            if(ql<=l && r<=qr) {
                return seg_tree[vertex];
            }
            push(vertex,l,r);
            int mid=(l+r)/2;
            return sum((2*vertex)+1,l,mid,ql,Math.min(qr,mid))+sum((2*vertex)+2,mid+1,r,Math.max(mid+1,ql),qr);
        }
    }
    
    
    public static void main(String args[]) throws IOException {
        Scan input=new Scan();
        StringBuilder ans=new StringBuilder("");
        int n=input.scanInt();
        int test=input.scanInt();
        int k=input.scanInt();
        int lft=1,rgt=Math.min(n,lft+15);
        int arr[]=new int[(n/16)+((n%16!=0)?1:0)];
        int lll[]=new int[arr.length];
        int rrr[]=new int[arr.length];
        int indx=0,cnt=0;
        while(true) {
            lll[indx]=lft;
            rrr[indx]=rgt;
            System.out.println("? "+lft+" "+rgt);
            System.out.flush();
            cnt+=(rgt-lft+1)-input.scanInt();
            arr[indx]=cnt;
//            System.out.println(arr[indx]);
            if(rgt==n) {
                break;
            }
            lft=rgt+1;
            rgt=lft+15;
            rgt=Math.min(rgt, n);
            indx++;
        }
        
        seg_tree st=new seg_tree(arr.length,arr);
        
        for(int i=0;i<test;i++) {
            if(i!=0) {
                k=input.scanInt();
            }
//            System.out.println("rdf  "+st.sum(0, 0, arr.length-1, 0, arr.length-1));
            indx=search(arr,k,st);
            int sum=st.sum(0, 0, arr.length-1, indx, indx);
            if(indx!=0) {
                sum-=st.sum(0, 0, arr.length-1, indx-1, indx-1);
                k-=st.sum(0, 0, arr.length-1, indx-1, indx-1);
            }
            int l=lll[indx],r=rrr[indx];
            while(l<r) {
                int mid=(l+r)/2;
                System.out.println("? "+l+" "+mid);
                System.out.flush();
                int ll=input.scanInt();
                int rr=sum-ll;
                ll=(mid-l+1)-ll;
                rr=(r-(mid+1)+1)-rr;
                if(k<=ll) {
                    r=mid;
                }
                else {
                    k-=ll;
                    l=mid+1;
                }
            }
            System.out.println("! "+l);
            System.out.flush();
            st.update(0, 0, arr.length-1, indx, arr.length-1, -1);
//            System.out.println("rdf  "+st.sum(0, 0, arr.length-1, 0, arr.length-1));
        }
        
        System.out.println(ans);
    }
    
    public static int search(int arr[],int val,seg_tree st) {
        if(arr.length==1) {
            return 0;
        }
        int l=0,r=arr.length-1,ans=-1;
        while(l<=r) {
            int mid=(l+r)/2;
            int mm=st.sum(0, 0, arr.length-1, mid, mid);
            if(mm<val) {
                l=mid+1;
            }
            else {
                ans=mid;
                r=mid-1;
            }
        }
        return ans;
    }
}