# Ces programmes sont sous licence CeCILL-B V1.

from math import *
from random import *

tab = [0 for i in range(0,16)]
for i in range(0,16):
  tab[i] = floor(random() * 1000)

for i in range(0,16):
  print(tab[i],end="")
  print(" ",end="")
print()

tab1 = [0 for i in range(0,16)]
   
s = 1
while s <= 15:
  b = 0
  x = 0
  y = s
  for i in range(0,16):
    if (x < b + s and y < b + 2 * s and tab[x] < tab[y]) or (y == b + 2 * s):
      tab1[i] = tab[x]
      x = x + 1
    else:
      tab1[i] = tab[y]
      y = y + 1
    if x == b + s and y == b + 2 * s:
      b = b + 2 * s
      x = b
      y = b + s
  for i in range(0,16):
    tab[i] = tab1[i]
  s = s * 2

for i in range(0,16):
  print(tab[i],end="")
  print(" ",end="")
print()