#include <stdio.h>
short o[1<<16], n[1<<16];
char rt[] = {0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
const int m = (1<<16)-1;
unsigned short rev(short a){return
 rt[a&15]<<12 | rt[a>>4&15]<<8 | rt[a>>8&15] <<4 | rt[a>>12&15];}
void po(int r){
  for(int j = r; j<65536; ++j) printf("%04x %04x\n", j, m&(int)o[j]);}
void mv(){for(int j = 0; j<65536; ++j) o[j]=n[j];}

void Z(int z, int st)
{short * w = n, *r0 = o, *r1 = o+0x4000, *r2 = o+0x8000, *r3=o+0xc000;
 while(z--){
   for(int e=0; e<st; ++e) *(w++) = *(r0++);
   for(int e=0; e<st; ++e) *(w++) = *(r2++);
   for(int e=0; e<st; ++e) *(w++) = *(r1++);
   for(int e=0; e<st; ++e) *(w++) = *(r3++);
  } mv();}
int main(){{int k = 1<<16; while(k--) o[k] = rev(k);}
// Array o now holds the bit reversal of j at a[j].
// Next we sort them without looking at the bits.
{int s=1<<14, t = 1; while(s) {Z(s, t); t <<= 2; s >>= 2;}}
if(0) po(0xfecd);
{int q = 65536; while(q--) if((o[q]&m) != (q&m)) printf("%x %x\n", q, o[q]);}
}