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
#include<iostream>
#include<stdlib.h>
#include<stdint.h>
#include<vector>
#include<string>
#include<bitset>
#include<stdio.h>
#include<iomanip>

using namespace std;

#define DEBUG
#define ASSERT

#ifdef DEBUG
#define ifdebug if(true)
#else
#define ifdebug if(false)
#endif

#ifdef ASSERT
#define ifassert if(true)
#else
#define ifassert if(false)
#endif


/// Funkcja sprawdzająca, czy jest ściana w danym miejscu;
/// x,y pozycja, size - aktualny rozmiar boku dla tego poziomu (4 == poziom 1; n=1)
bool check(int x, int y, int size) {
	if(size==4) {	// dla najmniejszego poziomu po prostu zwracamy wartości
		return (y==3 && x==2) || ((y==2 && (x==1 || x==3)));
	}
	// dla pozostałych poziomów działamy rekurencyjnie
    size>>=1;	// połowa
    if(y>size) {	// jeżeli jest w górnej części
		if(x<size) return check(x, y-size, size);	// to rekurencyjnie sprawdzamy lewą część
		if(x>size) return check(x-size, y-size, size);	// to rekurencyjnie sprawdzamy prawą część
		return y==size+1;	// jeżeli jest na środku górnej cześci, to tam jest łącznik punkt nad granicą
    }
    if(y==size) return x==1 || x==(2*size-1);		// jeżeli jesteśmy na środku (góra/dół), to punkty są na krawędziach (lewej, prawej)
    // jeżeli jest w dolnej cześci, to są obroty
    if(x<=size) return check(size-y, x, size);	// lewa strona dolnej części
    x-=size;	// prawa strona dolnej części; korygujemy x, aby był relatywny do kwadrata tamtej części
    return check(y, size-x, size);
}

class Walker {
public:
	int x,y;
	int dx,dy;
	int size;
public:
	Walker(int _size) : x(1), y(0), dx(1), dy(1), size(_size) {
	}

	void walk(int64_t steps) {
		for(int64_t i=0;i<steps;++i) {
			x+=dx; y+=dy;
			bool p=check(x,y, size);
			//cout<<"Step: "<<i<<" position: "<<x<<", "<<y<<(!p?"":" on wall")<<endl;
			if(x==0 || x==size) dx=-dx;	// zmieniamy kierunek lewo<->prawo
			else if(y==0 || y==size) dy=-dy;	// zmieniamy kierunek góra<->dół
			else if(p) {	// ściana wewnętrzna
				if(y&1) dy=-dy;
				else dx=-dx;
			}
		}
	}
};


int main(int argc, char** argv) {
	int n,z;

	std::ios::sync_with_stdio(false);

	cin>>n>>z;

	Walker w(1<<(n+1));

	int64_t last=0;
	for(int i=0;i<z;++i) {
		int64_t v;

		cin>>v;
		w.walk(v-last);
		cout<<w.x<<" "<<w.y<<endl;
		last=v;
	}

	return 0;
}