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
#include <bits/stdc++.h>
using namespace std;

class wektor: public pair<int,int> {
public:
	wektor(int x, int y): pair<int,int>(x,y) {}
	int& x() {
		return first;
	}
	int& y() {
		return second;
	}
	wektor ox() {
		return wektor(-x(), y());
	}
	wektor oy() {
		return wektor(x(), -y());
	}
	wektor swap() {
		return wektor(y(), x());
	}
	wektor obrot90() {
		return wektor(-y(), x());
	}
	wektor obrotm90() {
		return wektor(y(), -x());
	}
};

class gdzie_krawedz {
public:
	long long bok;
	gdzie_krawedz *mniejsza;
	gdzie_krawedz() {
	}
	gdzie_krawedz(int n) {
		bok = 1 << (n + 1);
		if (n > 1) {
			mniejsza = new gdzie_krawedz(n - 1);
		}
	}
	wektor czy_krawedz(long long x, long long y, wektor v) {
		if (x == 0 || x == bok) {
			return v.ox();
		}
		if (y == 0 || y == bok) {
			return v.oy();
		}
		if (x == 1 && y == bok / 2) {
			return v.ox();
		}
		if (x == bok - 1 &&  y == bok / 2) {
			return v.ox();
		}
		if (x == bok / 2 && y == bok / 2 + 1) {
			return v.oy();
		}
		if (x == bok / 2 || y == bok / 2) {
			return v;
		}
		bool bx = x > bok / 2;
		bool by = y > bok / 2;
		x %= bok / 2;
		y %= bok / 2;
		if (by) return mniejsza -> czy_krawedz(x, y, v);
		if (bx) return mniejsza -> czy_krawedz(y, bok/2 - x, v.obrotm90()).obrot90();
		return mniejsza -> czy_krawedz(y, x, v.obrot90()).obrotm90();
	}
};

gdzie_krawedz moja_krzywa;

void symuluj(long long t,long long &x, long long &y, wektor &v) {
	t %= (moja_krzywa.bok * moja_krzywa.bok);
	for (int i = 0; i < t; i ++) {
		x += v.x();
		y += v.y();
		v = moja_krzywa.czy_krawedz(x, y, v);
	}
}
const int N = 100 * 1000 + 5;
pair<long long, long long> odp[N];

int main() {
	int n;
	scanf("%d", &n);
	moja_krzywa = gdzie_krawedz(n);
	int q;
	scanf("%d", &q);
	vector<pair<long long,int> > que;
	for (int i = 0; i < q; i ++) {
		long long t;
		scanf("%lld", &t);
		que.push_back(make_pair(t, i));
	}
	sort(que.begin(), que.end());
	long long x = 1;
	long long y = 0;
	wektor v(1, 1);
	long long t = 0;
	for (int i = 0; i < q; i ++) {
		symuluj(que[i].first - t, x, y, v);
		t = que[i].first;
		odp[que[i].second] = make_pair(x, y); 
	}
	for (int i = 0; i < q; i ++) {
		printf("%lld %lld\n", odp[i].first, odp[i].second);
	}
}