from math import log
from sys import argv


fib = [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733,1134903170,1836311903]


def sqrs(x):
  out = ''
  while x > 0:
    out += chr(ord('0') + x % 2)
    x /= 2
  if len(out) <= 1: return 1
  outnum = 1
  for i in xrange(1, len(out)):
    if out[i] == out[i - 1] == '1':
      outnum *= -1
  return outnum

'''
def trace(x, n):
  bale = 0
  print '%12s' % bin(x)[2:],
  for i in xrange(1, n + 1):
    bale += sqrs(x + i)
    if bale == 0:
      print '%4d' % i,
      break


for kk in xrange(10):
  trace(2 ** kk + int(argv[1]), 1000)
  print 
'''
'''
a = 0
for i in xrange(10000):
  a += sqrs(i)
  print a,
'''

def listsr(x):
  out = [1]
  for i in xrange(x):
    out.append(out[i] + sqrs(i + 1))
  return out


def sqs(lis):
  dic = {}
  for i in xrange(len(lis)):
    tmp = lis[i]
    if dic.keys().count(tmp) == 0:
      dic.update({tmp: [i]})
    else:
      dic.get(tmp).append(i)
  return dic





def log2(x):
  return int(log(x)/log(2))


def first(x):
  if x == 0:
    return 0
  minus = 0
  if x & 1 == 0:
    tmp = 1
    while x & tmp == 0:
      tmp *= 2
    else:
      minus = ((4 ** log2(tmp) - 1) / 3 + 1) / 2
    x += 1
  length = log2(x)
  value = 4 ** length / 2
  can = 2 ** length + 1 # 1000...0001
  for i in xrange(1, length):
    bar = 2 ** i
    if (bar & can) != (bar & x):
      value += 4 ** i / 2
  return value - minus


lis = listsr(50000)
#print lis
a = sqs(lis)
a.pop(1)
for item in a.keys():
  tmp = a.get(item)[0]
  for i in xrange(len(a.get(item))):
    a.get(item)[i] -= tmp
  #print item, '\t', '%8s' % bin(tmp)[2:], '\t', a.get(item)
  print '%10s' % bin(item)[2:], '%6d' % first(item), '%7d' % a.get(item)[-1], '%8d' % ((first(item) + a.get(item)[-1]) / 2), a.get(item)[(item + 1) / 2]