#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;
uint32_t a[1000000];

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) {
    ll seed; cin >> seed;
    x = seed;

    uint32_t h = 1U << 31, d = 1U << 27;
    int p[2] = {};
    int k = 0;
    for (int i = 0; i < 10000001; i++) {
        auto t = generate();
        if (h - d < t && t < h + d) a[k++] = t;
        else p[t > h]++;
    }
    sort(a, a + k);
    cout << a[5000000 - p[0]] << endl;

    return 0;
}