Guess the Hidden Interval

You are given an integer n and a limit c on the number of queries. A hidden closed subinterval [a,b] is chosen from the interval [1,n]. Your task is to implement a function std::pair Guess(int n,int c) (and an init() function that is called once at the beginning) that correctly determines the hidden interval by making at most c calls to the provided function Query.

The interactive function Query is defined as follows:

• If x is less than a, it returns \(-1\).
• If x belongs to \([a,b]\), it returns \(0\).
• If x is greater than b, it returns \(1\).

You are allowed at most \(c\) queries per call to Guess. In each test case, the Guess function may be called multiple times (up to 5000 times). To avoid timeouts, implement an init() function which is called only once at the start (its body can be empty).

Note: Although this is an interactive problem, for the purpose of offline testing, the hidden interval will be provided as part of the input (see below). In your submitted solution, you must implement both Guess and init functions. Since Rumia's compiler only supports C++ (in all versions C++/C++11/C++14/C++17), you are limited to using these languages in the interactive environment. However, for this contest problem, you need to provide working solutions in five languages.

inputFormat

The input consists of four space-separated integers:

• n: The upper bound of the interval \([1, n]\).
• c: Maximum number of allowed queries for each call to Guess.
• a and b: The hidden interval such that \(1 \le a \le b \le n\).

For offline simulation of the interactive problem, the hidden interval \([a,b]\) is given as input.

outputFormat

Output the determined hidden interval as two space-separated integers: a and b. Your output should exactly match the hidden interval provided in the input.

sample

10 5 3 7

3 7