MALAKIES_KHPOYRIDH

#include <stdio.h>

int main ( void ) {
  FILE *in= fopen ( "qubits.in" , "r" ) ;
  FILE *out = fopen ( "qubits.out", "w" ) ;
  int N , ar[20][3] , p[3] , turn = 0 , i , j , ontop = 0 , tmp ;

  fscanf ( in , "%d" , &N ) ;
  N-- ;
  p[0] = N ; p[1] = -1 ; p[2] = -1 ;
  for ( i = 0 ; i <= N ; i++ )
    ar[i][0] = i ;
  if ( ( N % 2 ) == 1 ) {
    p[1]++ ;
    ar[p[1]][1] = ar[p[0]][0] ;
    ar[p[0]][0] = -1 ;
    p[0]-- ;
    fprintf ( out , "%c %c\n" , 65 , 66 ) ;
  }
  else {
    p[2]++ ;
    ar[p[2]][2] = ar[p[0]][0] ;
    ar[p[0]][0] = -1 ;
    p[0]-- ;
    fprintf ( out , "%c %c\n" , 65 , 67 ) ;
  }
  while ( 1 ) {
    tmp =  -5 ;
    if ( turn ) {
      /* Find the smallest */
      for ( i = 0 ; ar[p[i]][i] != N ; i++ ) ;
      if ( ontop ) {
        /*Calculate how many layers are under the smallest
        ( arithmetical progression ( + 1 ) ) */
        for ( j = 0 ; ( ar[p[i]-j][i] ) == ( ar[p[i]-j-1][i] + 1 ) ; j++ ) ;
        tmp = j ;
        for ( j = 0 ; ; j++ ) {
          if ( p[j] == -1 )
            continue ;
          if ( ( ar[p[j]][j] ) == ( ar[p[i] - tmp][i] - 1 ) )
              break ;
        }
        if ( ( tmp % 2 ) == 1 ) {
          for ( ontop = 0 ; ( ontop == i ) || ( ontop == j ) ; ontop++ ) ;
          p[ontop]++ ;
          ar[p[ontop]][ontop] = ar[p[i]][i] ;
          ar[p[i]][i] = -1 ;
          p[i]-- ;
          fprintf ( out , "%c %c\n" , 65 + i , 65 + ontop ) ;
          ontop = 1 ;
        }
        else {
          p[j]++ ;
          ar[p[j]][j] = ar[p[i]][i] ;
          ar[p[i]][i] = -1 ;
          p[i]-- ;
          fprintf ( out , "%c %c\n" , 65 + i , 65 + j ) ;
        }
        tmp = -2 ;
      }
      else {
        /*Find the second smallest*/
        for ( j = 0 ; ar[p[j]][j] != ( N - 1 ) ; j++ ) ;
        /* Transfer the smallest to the second smallest */
        p[j]++ ;
        ar[p[j]][j] = ar[p[i]][i] ;
        ar[p[i]][i] = -1 ;
        p[i]-- ;
        fprintf ( out , "%c %c\n" , 65 + i , 65 + j ) ;
        ontop = 1 ;
      }
      if ( tmp == -2 )
        ontop = 0 ;
      tmp = -1 ;
    }
    else {
      /* Find if there is an empty slot */
      for ( i = 0 ; ( p[i] != -1 ) && ( i < 3 ) ; i++ ) ;
      /* If an empty slot was found */
      if ( i != 3 ) {
        /* Find the non empty slot ( and not the smallest ) */
        for ( j = 0 ; ( ar[p[j]][j] == N ) || ( p[j] == -1 ) ; j++ ) ;
        /* Transfer the non empty to the empty */
        p[i]++ ;
        ar[p[i]][i] = ar[p[j]][j] ;
        ar[p[j]][j] = -1 ;
        p[j]-- ;
        fprintf ( out , "%c %c\n" , 65 + j , 65 + i ) ;
      }
      else {
        /*Find the non smallest slots*/
        for ( i = 0 ; ar[p[i]][i] == N ; i++ ) ;
        for ( j = 0 ; ( ar[p[j]][j] == N ) || ( j == i ) ; j++ ) ;
        /*Move the biggest to i and the smallest to j ( well ,
        that was the idea , but due to incompatibility it's
        the smallest-number ( which is actually the big layer )
        to the biggest-number ( which is actually the small layer )*/
        if ( ar[p[j]][j] < ar[p[i]][i] ) {
          tmp = i ; i = j ; j = tmp ;
        }
        p[i]++ ;
        ar[p[i]][i] = ar[p[j]][j] ;
        ar[p[j]][j] = -1 ;
        p[j]-- ;
        fprintf ( out , "%c %c\n" , 65 + j , 65 + i ) ;
      }
      turn = 1 ;
    }
    if ( tmp == -1 )
      turn = 0 ;
    if ( ( p[0] == -1 && p[1] == -1 ) || ( p[0] == -1 && p[2] == -1 ) || ( p[1] == -1 && p[2] == -1 ) )
      break ;
  }
  fclose ( in ) ; fclose ( out ) ;
  return ( 0 ) ;
}