题目描述

传说中，早在公元前 $114514$ 年，有个神秘的国家，叫做补幺国。他们当时就已在用一种叫做“补幺梨”的货币，其因形状长得像梨子而得名。

补幺人通过“补幺梨”货币来进行交易。具体地，“补幺梨”有 $n$ 种面值，分别为 $a_1,a_2,\cdots,a_n$。

补幺人认为，在他们的视野里，$m$ 是“补幺梨”基本面值的上限。因此，他们为了尽可能让这些基本的面值能覆盖所有面额，这 $m$ 种面值是在 $[2,m]$ 内等概率随机的。

补幺国王掌管大权，每种”补幺梨“他都有 $\infty$ 枚。但是，即便他拥有再多的硬币，他还是很惊叹竟然有这些”补幺梨“凑不出的面额！

古人的智商自然是有限的，因此他们只能意识到问题，但不能解决问题。

作为十万年后的我们，古人借助时光机向我们发出求助。你需要帮他们计算出最大的不能被表示的面额。

输入格式

第一行，输入三个数 $n,m,seed$，表示“补幺梨”的面值种数，基本货币的金额上限，以及随机种子。

对于 $a_1,a_2,\cdots,a_n$，“补幺人”通过下述 c++ 程序的 mt19937 随机数得到（需 c++11）：

int main() {
  scanf("%d%d%d", &n, &m, &seed);
  mt19937 rng(seed);
  auto get = [&]() {
    uniform_int_distribution<int> qwq(2, m);
    return qwq(rng);
  };
  for (int i = 1; i <= n; i++) {
    a[i] = get();
  }
}

输出格式

你需要帮补幺人计算出最大不能被表示的面额。

不难发现，在给定的数据范围下，必定存在不能被表示的面额。

样例

5 5 3

1

注意，样例仅作为参考。该数据范围不会出现在最终测试数据中。

生成的序列为 $4,2,4,5,3$。最大不能被表示的金额显然是 $1$。

2 100 10

2309

生成的序列为 $78,31$。最大不能被表示的金额是 $2309$。

3 100 10

89

生成的序列为 $78,31,4$。最大不能被表示的金额是 $89$。

50 50000000 97

50215765

数据范围

对于 $10\%$ 的数据，$n,m\le 100$；

对于 $30\%$ 的数据，$n\le 100,m\le 10^4$；

对于 $60\%$ 的数据，$2\le m\le 10^7$；

对于 $80\%$ 的数据，$2\le m\le 5\times 10^7$；

对于 $100\%$ 的数据，$50\le n\le 10^7,2\le m\le 10^8$；