#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; 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() { uint32_t seed; cin >> seed; ll ok = 0; ll ng = UINT_MAX; ll a = 10000001; while (abs(ng - ok) >= 2) { ll mid = (ok + ng) / 2; ll m_cnt = 0; x = seed; y = 1; z = 2; w = 3; for (int i = 0; i < a; ++i) { ll v = generate(); if (v <= mid) { ++m_cnt; } } if (m_cnt <= a / 2 + 1) { ok = mid; } else { ng = mid; } } cout << ok << endl; return 0; }