Find the Marked Node in the Segment Tree

Given a sequence of length (n=2^k), a segment tree is built on this sequence. Exactly one node in the segment tree is marked. You can perform several queries on the segment tree. In each query you are given an interval ([l,r]) and you can call the function (query(l,r)) provided by the interactive library. This function returns:

• \(0\) if none of the nodes corresponding to the current query interval is marked,
• \(1\) if at least one is marked, and
• \(-1\) if the query interval is invalid (in which case you must immediately terminate the current test case).

Your task is to identify the marked node by finding its corresponding interval ([x,y]) while using as few queries as possible. More formally, if the optimal strategy in the worst case uses (Q) queries, then you are allowed to use at most (Q) queries.

Interaction Protocol:

You do not need to implement the main function. Instead, implement the following function:

[ std::pair<int,int> solve(int k); ]

which should return the pair ((x,y)) representing the marked node’s interval ([x,y]).

You may use the interactive function:

[ int query(int l, int r); ]

where (1 \le l \le r \le n) and (n=2^k).

Note: There is no strict limit on query count; however, too many queries may lead to a time limit exceeded error.

inputFormat

The input consists of two lines:

1. The first line contains an integer (k).
2. The second line contains two integers (x) and (y) which represent the marked node's interval ([x,y]) in the segment tree. (This is given only for simulation purposes.)

outputFormat

Output the two integers (x) and (y) (separated by a space) representing the interval of the marked node.

sample

1
1 1

1 1