using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; class TEST{ static void Main(){ Sol mySol =new Sol(); mySol.Solve(); } } class Sol{ public void Solve(){ var dic = new Dictionary(); var rnd = new XorShiftModoki(N); for(int i=0;i<10000001;i++){ var t = rnd.Generate(); if(!dic.ContainsKey(t)) dic.Add(t,0); dic[t]++; } var l = dic.Keys.ToArray(); //Console.WriteLine(l.Length); Array.Sort(l); int tot = 0; for(int i=0;i= 10000001/2 + 1){ Console.WriteLine(l[i]); return; } } } uint N; public Sol(){ N = (uint) ri(); } public Sol(uint n){ N = n; } static String rs(){return Console.ReadLine();} static int ri(){return int.Parse(Console.ReadLine());} static long rl(){return long.Parse(Console.ReadLine());} static double rd(){return double.Parse(Console.ReadLine());} static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);} static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));} static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));} static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));} } class XorShiftModoki{ public uint x = 0, y = 1, z = 2, w = 3; public uint Generate() { uint t = (x^(x<<11)); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); return w; } public XorShiftModoki(uint seed){ x = seed; } }