Problem: This is an interactive problem.

You are given a sorted in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to x.

More formally, there is a singly liked list built on an array of n elements. Element with index i contains two integers: valuei is the integer value in this element, and nexti that is the index of the next element of the singly linked list (or -1, if the current element is the last). The list is sorted, i.e. if nexti ≠ - 1, then valuenexti > valuei.

You are given the number of elements in the list n, the index of the first element start, and the integer x.

You can make up to 2000 queries of the following two types:

  * ? i (1 ≤ i ≤ n) — ask the values valuei and nexti, 
  * ! ans — give the answer for the problem: the minimum integer, greater than or equal to x, or ! -1, if there are no such integers. Your program should terminate after this query. 



Write a program that solves this problem.

Input

The first line contains three integers n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109) — the number of elements in the list, the index of the first element and the integer x.

Output

To print the answer for the problem, print ! ans, where ans is the minimum integer in the list greater than or equal to x, or -1, if there is no such integer.

Interaction

To make a query of the first type, print ? i (1 ≤ i ≤ n), where i is the index of element you want to know information about.

After each query of type ? read two integers valuei and nexti (0 ≤ valuei ≤ 109,  - 1 ≤ nexti ≤ n, nexti ≠ 0).

It is guaranteed that if nexti ≠ - 1, then valuenexti > valuei, and that the array values give a valid singly linked list with start being the first element.

Note that you can't ask more than 1999 queries of the type ?.

If nexti = - 1 and valuei = - 1, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling exit(0)). You will receive "Wrong Answer", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Your solution will get "Idleness Limit Exceeded", if you don't print anything or forget to flush the output, including the final answer.

To flush you can use (just after printing a query and line end):

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



Hacks format

For hacks, use the following format:

In the first line print three integers n, start, x (1 ≤ n ≤ 50000, 1 ≤ start ≤ n, 0 ≤ x ≤ 109).

In the next n lines print the description of the elements of the list: in the i-th line print two integers valuei and nexti (0 ≤ valuei ≤ 109,  - 1 ≤ nexti ≤ n, nexti ≠ 0).

The printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from start by following links nexti, and the last element end should have -1 in the nextend.

Example

Input

5 3 80
97 -1
58 5
16 2
81 1
79 4


Output

? 1
? 2
? 3
? 4
? 5
! 81

Note

You can read more about singly linked list by the following link: <https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list>

The illustration for the first sample case. Start and finish elements are marked dark. <image>

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.BigInteger;

/**
 *
 * @author usquare
 */

public class ProblemB
{

    static long mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    static void solve()
    {

        in = new InputReader(System.in);
        out = new PrintWriter(System.out);  
        
        int n = in.nextInt() - 1;
        int s = in.nextInt();
        int x = in.nextInt();
        int[] arr = new int[n];
        
        for(int i = 0; i < n; i++)
            arr[i] = i;
        
        shuffle(arr, new Random());
        
        ArrayList<Pair> list = new ArrayList<>();
        
        for(int i = 1; i < min(1000, n); i++){
            out.println("? "+ (arr[i] + 1));
            out.flush();
            int val = in.nextInt();
            int next = in.nextInt();
            out.flush();
            list.add(new Pair(val, next));
        }
        
        int ptr = s;
        Collections.sort(list);
        
        for(int i = 0; i < list.size(); i++){
            if(list.get(i).x < x){
                ptr = list.get(i).y;
            }
        }
        
        while(ptr != -1){
            out.println("? "+ ptr);
            out.flush();
            int val = in.nextInt();
            int next = in.nextInt();
            if(val >= x){
                out.println("! "+ val);
                out.flush();
                out.close();
                return;
            }
            ptr = next;
        }
        
        out.println("! "+ -1);
        out.flush();
        out.close();
        
        out.close();

    }
    
    
    public static void main(String[] args)
    {

        new Thread(null,new Runnable()
        {
            @Override
            public void run()
            {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        },"1",1<<26).start();
    }

    static class Pair implements Comparable<Pair>
    {

        int i;
        int x, y;
        
	Pair (int x,int y,int i)
        {
		this.x = x;
		this.y = y;
                this.i = i;
	}
        
	Pair (int x,int y)
        {
		this.x = x;
		this.y = y;
	}
        
        
	public int compareTo(Pair o)
        {
                    return Long.compare(this.x,o.x);
	}

        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }

        @Override
        public String toString()
        {
            return x + " "+ y + " "+i;
        }
        
        public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }
    
    } 

    static int[] shuffle(int[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            int d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }

    static class Merge
    {

        public static void sort(int inputArr[])
        {
            int length = inputArr.length;
            doMergeSort(inputArr,0, length - 1);
        }

        private static void doMergeSort(int[] arr,int lowerIndex, int higherIndex)
        {        
            if (lowerIndex < higherIndex)
            {
                int middle = lowerIndex + (higherIndex - lowerIndex) / 2;
                doMergeSort(arr,lowerIndex, middle);
                doMergeSort(arr,middle + 1, higherIndex);
                mergeParts(arr,lowerIndex, middle, higherIndex);
            }
        }

        private static void mergeParts(int[]array,int lowerIndex, int middle, int higherIndex)
        {
            int[] temp=new int[higherIndex-lowerIndex+1];
            for (int i = lowerIndex; i <= higherIndex; i++)
            {
                temp[i-lowerIndex] = array[i];
            }
            int i = lowerIndex;
            int j = middle + 1;
            int k = lowerIndex;
            while (i <= middle && j <= higherIndex)
            {
                if (temp[i-lowerIndex] < temp[j-lowerIndex])
                {
                    array[k] = temp[i-lowerIndex];
                    i++;
                } else
                {
                    array[k] = temp[j-lowerIndex];
                    j++;
                }
                k++;
            }
            while (i <= middle)
            {
                array[k] = temp[i-lowerIndex];
                k++;
                i++;
            }
            while(j<=higherIndex)
            {
                array[k]=temp[j-lowerIndex];
                k++;
                j++;
            }
        }

    }

    static long add(long a,long b)
    {
        long x = a + b;
        if(x >= mod) x -= mod;
        return x;
    }

    static long sub(long a,long b)
    {
        long x= a - b ;
        if(x < 0) x += mod;
        return x;
    }

    static long mul(long a,long b)
    {
        a %= mod;
        b %= mod;
        long x = a*b;
        return x%mod;
    }


    static boolean isPal(String s)
    {
        for(int i=0, j=s.length()-1;i<=j;i++,j--)
        {
                if(s.charAt(i)!=s.charAt(j)) return false;
        }
        return true;
    }
    static String rev(String s)
    {
                StringBuilder sb=new StringBuilder(s);
                sb.reverse();
                return sb.toString();
    }

    static long gcd(long x,long y)
    {
        if(y==0)
                return x;
        else
                return gcd(y,x%y);
    }

    static int gcd(int x,int y)
    {
        if(y==0)
                return x;
        else 
                return gcd(y,x%y);
    }

    static long gcdExtended(long a,long b,long[] x)
    {

        if(a==0)
        {
            x[0]=0;
            x[1]=1;
            return b;
        }
        long[] y=new long[2];
        long gcd=gcdExtended(b%a, a, y);

        x[0]=y[1]-(b/a)*y[0];
        x[1]=y[0];

        return gcd;
    }


    static long mulmod(long  a,long b,long m)
    {
        if (m <= 1000000009) return a * b % m;

        long res = 0;
        while (a > 0)
        {
            if ((a&1)!=0)
            {
                res += b;
                if (res >= m) res -= m;
            }
            a >>= 1;
            b <<= 1;
            if (b >= m) b -= m;
        }
        return res;
    }

    static int abs(int a,int b)
    {
        return (int)Math.abs(a-b);
    }

    public static long abs(long a,long b)
    {
        return (long)Math.abs(a-b);
    }

    static int max(int a,int b)
    {
        if(a>b)
                return a;
        else
                return b;
    }

    static int min(int a,int b)
    {
        if(a>b)
                return b;
        else 
                return a;
    }

    static long max(long a,long b)
    {
        if(a>b)
                return a;
        else
                return b;
    }

    static long min(long a,long b)
    {
        if(a>b)
                return b;
        else 
                return a;
    }

    static long pow(long n,long p,long m)
    {
         long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;
            if(result>=m)
            result%=m;
            p >>=1;
            n*=n;
            if(n>=m)
            n%=m;
        }
        return result;
    }

    static long pow(long n,long p)
    {
        long  result = 1;
          if(p==0)
            return 1;

        while(p!=0)
        {
            if(p%2==1)
                result *= n;	    
            p >>=1;
            n*=n;	    
        }
        return result;
    }

    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }

    static class InputReader
    {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }

        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }

        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }

        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }

        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }

        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }

        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }

        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }

    }
}