F-Cidoai的自恋_牛客小白月赛107

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Cidoai 喜欢小 C。
它某天和小 C 在玩一个游戏。小 C 需要猜一个在 $[1,n]$ 之间的数，它会先给小 C 一个长度为 $k$ 的询问列表 $a_1,a_2,\cdots,a_k$ ，Cidoai 会根据答案 $x$ 对列表上的每个数给出大于答案、小于答案或是等于答案的回答。
小 C 认为一次无效询问是：如果存在一个 $i<j$ 满足 $a_i<x$ 且 $a_j \le a_i$ 或满足 $a_i>x$ 且 $a_j \ge a_i$ ，则询问 $a_j$ 是一次无效询问。

Cidoai 想要捉弄一下小 C，因此它会根据询问列表确定答案 $x$ ，满足它不在小 C 的询问列表中且无效的询问次数最多，如果有多个满足条件的数，输出最小的那个。

Cidoai 保证，对于题目所给的所有数据，不存在无解的情况。

由于输入量过大， $a$ 数列不会被直接输入，而是由参数生成，伪代码如下：

def rnd():
    p=(1<<32)
    ret=seed
    seed=(seed xor ((seed<<13) mod p)) mod p
    seed=(seed xor ((seed>>17) mod p)) mod p
    seed=(seed xor ((seed<<5) mod p)) mod p
    return ret
for i=1 to k: 
    a[i]=(rnd() mod n) + 1

其中 $seed$ 由输入给定。

rnd 函数的 C++ 代码如下：

unsigned seed;
unsigned rnd(){
	unsigned ret=seed;
	seed^=seed<<13;
	seed^=seed>>17;
	seed^=seed<<5;
	return ret;
}

输入描述:

一行三个整数 。其中  用来生成  数列。
。

输出描述:

一行一个整数表示答案。

示例1

输入

复制

6 3 5

输出

复制

说明

根据参数生成的 。

若答案 ，则询问都有效。

若答案 ，则询问都有效。

若答案 ，则询问  无效。

若答案 ，则在小 C 的询问列表中。

因此  是使得无效询问次数最多的最小答案。

示例2

输入

复制

6 2 5

输出

复制

说明

生成的 。
答案  时，询问都有效。
因此  是最小的满足条件的答案。

示例3

输入

复制

14 6 4

输出

复制

示例4

输入

复制

32 6 25

输出

复制

示例5

输入

复制

52052 1206 13149999

输出

复制

备注:

在 C++ 中，unsigned int 的运算会自动对  取模。