1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <cstring>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

char *mem;
char **a;
int *rx, *ry;

const int DX[4] = {0, 1, 0, -1};
const int DY[4] = {1, 0, -1, 0};
const char L[3] = "-|";
int tx, ty, dir, rot;

void pos(int x, int y) {
	tx = x;
	ty = y;
	dir = 0;
	rot = 1;
}

void rt() {
	dir += rot;
	dir = (dir + 4) % 4;
}

void lt() {
	dir -= rot;
	dir = (dir + 4) % 4;
}

void fd() {
	tx += DX[dir];
	ty += DY[dir];
	a[tx][ty] = L[dir & 1];
	tx += DX[dir];
	ty += DY[dir];
}

void mirror() {
	rot = -rot;
}

void hilbert(int n) {
	if (!n) {
		rt();
		rt();
		return;
	}
	rt();
	mirror();
	hilbert(n - 1);
	mirror();
	rt();
	fd();
	hilbert(n - 1);
	lt();
	fd();
	lt();
	hilbert(n - 1);
	fd();
	rt();
	mirror();
	hilbert(n - 1);
	mirror();
	rt();
}

int main() {
	int n;
	scanf("%d", &n);
	int m = (1 << (n + 1)) + 1;
	mem = new char[m * m];
	memset(mem, ' ', m * m);
	a = new char*[m];
	REP(i,m) a[i] = mem + m * i;
	pos(0, 0);
	REP(i,4) {
		REP(j,1<<n) fd();
		rt();
	}		
	pos(1, 1);
	hilbert(n);
	int s = 1 << ((n + 1) << 1);
	rx = new int[s];
	ry = new int[s];
	int bx = 1, by = 0, vx = 1, vy = 1;
	REP(i,s) {
		rx[i] = bx;
		ry[i] = by;
		bx += vx;
		by += vy;
		switch (a[bx][by]) {
			case '-':
				vx = -vx;
				break;
			case '|':
				vy = -vy;
				break;
			default:
				break;
		}
	}
	int z;
	scanf("%d", &z);
	REP(i,z) {
		int t;
		scanf("%d", &t);
		printf("%d %d\n", rx[t], ry[t]);
	}
	delete[] rx;
	delete[] ry;
	delete[] a;
	delete[] mem;
}