2-2014-B

import java.util.*;

public class BRapido {
  // un vector con números fibonacci
  public static int nf, INFINITO = 10000;
  public static int[] F = new int[INFINITO];

  public static void alimentarF(int numero) {
    while (F[nf-1] < numero) {
      F[nf] = F[nf-1] + F[nf-2];
      nf++;
    }
  }

  /* devuelve -1 si no lo encuentra, de lo contrario, devuelve
     el índice en el que se encuentra el número fibonacci */
  public static int buscarF(int numero) {
    /* [a,b] es el rango de índices de F dentro de los que podría
       estar el número */
    int a=0, b=nf, mitad=b/2;

    while (b-a > 1) {
      mitad = a + (b-a)/2;
      if (numero == F[mitad])
    return mitad;

      if (numero < F[mitad])
    b = mitad;
      else
    a = mitad;
    }

    if (F[mitad] == numero)
      return mitad;

    return -1;
  }

  public static boolean esFibonacci(int numero) {
    /* si el vector de fibonaccis aún no ha llegado hasta
       el número, alimentar al vector de fibonaccis hasta
       que llegue al número. */
    alimentarF(numero);

    /*
      Ahora, voy a buscar al número, mediante el método
      binary search, dentro del vector F de fibonaccis.
     */
    int indice = buscarF(numero);

    return indice != -1;

  }

  public static void main(String[] args) {
    F[0] = 0;
    F[1] = 1;
    nf = 2;
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt(); // esta variable fue declarada globalmente.

    // leyendo el vector ... (el vector fue declarado globalmente (línea 8))
    for (int i=0; i<n; i++) {
      int a = cin.nextInt();
      System.out.print(a + " ");

      if (esFibonacci(a))
    System.out.print(a + " ");
    }

    System.out.println();

  }

}