Guess the Hidden Number

珂愛 gives you an integer \(k\) chosen from \(\{1,2,\ldots,n\}\). You can ask queries by calling the function Seniorious(x), which returns:

• \(1\) if \(k < x\);
• \(-1\) if \(k > x\);
• \(0\) if \(k = x\).

Your task is to implement a function int Chtholly(int n, int c) that finds \(k\) using no more than \(c\) queries. If you exceed \(c\) queries, you score 0 on that test case.

inputFormat

The input consists of a single line with three integers:

1. \(n\): the upper bound for the secret number \(k\) (i.e. \(1 \le k \le n\));
2. \(c\): the maximum number of allowed queries;
3. \(k\): the hidden number.

outputFormat

Output a single integer -- the secret number \(k\) determined using at most \(c\) queries.

sample

10 4 7

7