import java.io.FileNotFoundException; import java.io.PrintWriter; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) throws FileNotFoundException { new Main().run(); } void run() throws FileNotFoundException { Scanner sc = new Scanner(System.in); seed = sc.nextLong(); initialize(); int n = 10000001; long[] q = new long[n]; for (int i = 0; i < q.length; ++i) { q[i] = generate(); } Arrays.sort(q); System.out.println(q[n / 2]); initialize(); int[] a = new int[1 << 16]; for (int i = 0; i < 10000001; ++i) { ++a[(int) (generate() >> 16)]; } int sum = 0; int p = 0; while (sum < 5000001) { sum += a[p]; ++p; } p = p - 1; long gt = Math.max(0, (1 << 16) * (p - 1)), el = Math.min((long) (1L << 16) * (p + 1), (1L << 32) - 1); while (true) { long m = (gt + el) / 2; initialize(); for (int i = 0; i < 10000001; ++i) { generate(); if (w < m) ++c1; else if (w == m) ++c2; else ++c3; } if (c1 + c2 < 5000001) { gt = m; } else { el = m; } if (c1 + c2 >= 5000001 && c2 + c3 >= 5000001) { System.out.println(m); return; } } } long c1 = 0, c2 = 0, c3 = 0; long x = 0, y = 1, z = 2, w = 3; long seed; void initialize() { x = seed; y = 1; z = 2; w = 3; c1 = 0; c2 = 0; c3 = 0; } long generate() { long t = (x ^ (x << 11)) & ((1L << 32) - 1); x = y & ((1L << 32) - 1); y = z & ((1L << 32) - 1); z = w & ((1L << 32) - 1); w = ((w ^ (w >> 19)) ^ (t ^ (t >> 8))) & ((1L << 32) - 1); return w; } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } }