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
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int n, z, ile, gdzie, PozX, PozY, ZmX, ZmY;
int tab[35];

char Tab[8200][8200];

vector < vector < pair <int, int> > > res;
vector < pair <int, int> > POZ, PION;
vector < pair <int, int> >::iterator it;

vector < vector < pair <int, int> > > hilbert (int m)
{
	vector < vector < pair <int, int> > > result;
	vector < pair <int, int> > poziome;
	vector < pair <int, int> > pionowe;
	vector < vector < pair <int, int> > > pomoc;
	vector < pair <int, int> > poz;
	vector < pair <int, int> > pion;
	if (m == 1)
	{
		poziome.push_back(make_pair(2, 3));
		pionowe.push_back(make_pair(1, 2));
		pionowe.push_back(make_pair(3, 2));
		result.push_back(poziome);
		result.push_back(pionowe);
		return result;
	}
	pomoc = hilbert(m - 1);
	poz = pomoc[0];
	pion = pomoc[1];
	for (int i = 0; i < poz.size(); ++i)
	{
		poziome.push_back(make_pair(poz[i].first, poz[i].second + tab[m]));
		poziome.push_back(make_pair(poz[i].first + tab[m], poz[i].second + tab[m]));
		pionowe.push_back(make_pair(poz[i].second, tab[m] - poz[i].first));
		pionowe.push_back(make_pair(tab[m + 1] - poz[i].second, poz[i].first));
	}
	for (int i = 0; i < pion.size(); ++i)
	{
		pionowe.push_back(make_pair(pion[i].first, pion[i].second + tab[m]));
		pionowe.push_back(make_pair(pion[i].first + tab[m], pion[i].second + tab[m]));
		poziome.push_back(make_pair(pion[i].second, tab[m] - pion[i].first));
		poziome.push_back(make_pair(tab[m + 1] - pion[i].second, pion[i].first));
	}
	poziome.push_back(make_pair(tab[m], tab[m] + 1));
	pionowe.push_back(make_pair(1, tab[m]));
	pionowe.push_back(make_pair(tab[m + 1] - 1, tab[m]));
	result.push_back(poziome);
	result.push_back(pionowe);
	return result;
}

int main ()
{
	tab[0] = 1;
	for (int i = 1; i < 31; ++i) tab[i] = 2 * tab[i - 1];
	scanf("%d%d", &n, &z);
	if (n <= 12)
	{
		res = hilbert(n);
		POZ = res[0];
		PION = res[1];
		for (int i = 0; i < POZ.size(); ++i) Tab[POZ[i].first][POZ[i].second] = 1;
		for (int i = 0; i < PION.size(); ++i) Tab[PION[i].first][PION[i].second] = 2;
		for (int i = 1; i < tab[n + 1]; i += 2) Tab[i][0] = Tab[i][tab[n + 1]] = 1;
		for (int i = 1; i < tab[n + 1]; i += 2) Tab[0][i] = Tab[tab[n + 1]][i] = 2;
		ile = 0;
		PozX = 1;
		PozY = 0;
		ZmX = 1;
		ZmY = 1;
		while (z--)
		{
			scanf("%d", &gdzie);
			for (int i = ile; i < gdzie; ++i)
			{
				PozX += ZmX;
				PozY += ZmY;
				if (Tab[PozX][PozY] == 1) ZmY *= -1;
				else if (Tab[PozX][PozY] == 2) ZmX *= -1;
			}
			printf("%d %d\n", PozX, PozY);
			ile = gdzie;
		}
		return 0;
	}
	res = hilbert(n);
	POZ = res[0];
	PION = res[1];
	for (int i = 1; i < tab[n + 1]; i += 2)
	{
		POZ.push_back(make_pair(i, 0));
		POZ.push_back(make_pair(i, tab[n + 1]));
		PION.push_back(make_pair(0, i));
		PION.push_back(make_pair(tab[n + 1], i));
	}
	sort(POZ.begin(), POZ.end());
	sort(PION.begin(), PION.end());
	ile = 0;
	PozX = 1;
	PozY = 0;
	ZmX = 1;
	ZmY = 1;
	while (z--)
	{
		scanf("%d", &gdzie);
		for (int i = ile; i < gdzie; ++i)
		{
			PozX += ZmX;
			PozY += ZmY;
			it = upper_bound(POZ.begin(), POZ.end(), make_pair(PozX, PozY));
			if ((it != POZ.end()) && (it->first == PozX) && (it->second == PozY)) ZmY *= -1;
			else
			{
				it = upper_bound(PION.begin(), PION.end(), make_pair(PozX, PozY));
				if ((it != PION.end()) && (it->first == PozX) && (it->second == PozY)) ZmX *= -1;
			}
		}
		printf("%d %d\n", PozX, PozY);
		ile = gdzie;
	}
	return 0;
}