该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：2 Sec 内存限制：32 MB 输入文件：memory.in 输出文件：memory.out

请计算长度为 $10000001$ 的数列 $a$ 的中位数。这道题对大家来说太过简单，因此特意将内存限制设定为 32MB。

补充说明：中位数指将数列按大小排序后，位于中间位置的数值。

输入格式

一个整数 $seed$，作为生成 $a$ 序列的种子。生成的算法为 XOR Shift 伪随机数生成算法，代码如下：

uint32_t x = 0, y = 1, z = 2, w = 3;
uint32_t generate() { 
    uint32_t t = (x^(x<<11));
    x = y;
    y = z;
    z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); 
    return w;
}

int main(void) {
    int64_t seed; cin >> seed; 
    x = seed;
    uint32_t a[10000001];
    for (int i = 0; i < 10000001; i++) {
        a[i] = generate();
    }
    for (int i = 0; i < 10000001; i++) {
        cout << a[i] << endl;
    }
    return 0;
}

其中，uint32_t 是 C++ 内置的数据类型，表示 32 位无符号整数，取值范围为 $0 \sim 2^{32}-1$；int64_t 是 64 位整数。

提示：generate 函数产生的随机数会以 10000001 为一个循环，即第 10000002 到第 20000002 个数会和第 1 个到第 10000001 个数完全相同。

输出格式

一个整数，表示中位数。

样例

样例 1

1

2147058707

样例说明：生成的数列如下：$2058$、$3$、$4113$、$2058$、$4198488$、$4196427$、$12587210$、$8390784$、$4332056$、$4212747$、$413321$、……

样例 2

100000

2148033584

数据范围

$1 \le seed \le 100000$