x=gets.to_i
y=1
z=2
w=3
0.upto(1e7){t=x^x<<11&2**32-1
x,y,z=y,z,w
w^=w>>19^t^t>>8
w<21e8?$.+=1:w<22e8&&$*<<w}
p$*.sort[5e6-$.+1]