Interactive LowerBound

- 这是一个交互式问题。 - 题目将会给你一个按递增顺序排序的单项链表。你需要找到列表中大于或等于x的最小整数。 - 更正式点说，在一个由n个元素构成的数组中构成了一个单项链表。每个数组元素i包含两个整数，value_是元素的整数值，next_i是它所指向的元素（**如果当前元素没有后继（即其为最后一个元素）则为-1**）。通过next_i就可以对数组进行排序。 - 现在给你这个数组中的元素数量n，指向第一个元素的start和整数x。 - 你要进行不超过2000组访问，共有两种访问形式（**输出样例中是你的询问，你每询问一次，你的程序就会读取两个数**) 1. ？i（1<=i<=n）询问value_i和next_i; 1. ！回答第二行所说的答案，即大于或等于x最小整数，***如果没有这样的整数，则输出！-1***，你的程序应在这个输出结束后终止。 - 请编写一个程序来解决这个问题。

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: $ value_{i} $ is the integer value in this element, and $ next_{i} $ 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 $ next_{i}≠-1 $ , then $ value_{nexti}&gt;value_{i} $ . 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 $ value_{i} $ and $ next_{i} $ , - ! 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.

The first line contains three integers $ n $ , $ start $ , $ x $ ( $ 1<=n<=50000 $ , $ 1<=start<=n $ , $ 0<=x<=10^{9} $ ) — the number of elements in the list, the index of the first element and the integer $ x $ .

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 $ value_{i} $ and $ next_{i} $ ( $ 0<=value_{i}<=10^{9} $ , $ -1<=next_{i}<=n $ , $ next_{i}≠0 $ ). It is guaranteed that if $ next_{i}≠-1 $ , then $ value_{nexti}&gt;value_{i} $ , 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 $ next_{i}=-1 $ and $ value_{i}=-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<=10^{9} $ ). In the next $ n $ lines print the description of the elements of the list: in the $ i $ -th line print two integers $ value_{i} $ and $ next_{i} $ ( $ 0<=value_{i}<=10^{9} $ , $ -1<=next_{i}<=n $ , $ next_{i}≠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 $ next_{i} $ , and the last element $ end $ should have -1 in the $ next_{end} $ .

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

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

You can read more about singly linked list by the following link: [https://en.wikipedia.org/wiki/Linked\_list#Singly\_linked\_list](https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list) The illustration for the first sample case. Start and finish elements are marked dark.