#include <vector>
#include <iostream>
void s(int**m,int*v,int n,int h){int r=h,c=h,i=0,j,l=n-2*h-1;if(l>-1){do{*v++=m[r][c];l?(j=i/l)<1?c++:j<2?r++:j<3?c--:r--:l;}while(++i<4*l);s(m,v,n,h+1);}}
using V=std::vector<int>;
std::vector<V> x{{1, 2, 3, 4}, {12, 13, 14, 5}, {11, 16, 15, 6}, {10, 9, 8, 7}};
std::vector<V> y{{1, 2, 3}, {8, 9, 4}, {7, 6, 5}};
std::vector<V> z;
int** make_array(const std::vector<V>& v)
{
int **m = new int*[v.size()];
for(int i = 0; i < v.size(); ++i)
m[i] = new int[v.size()];
for(int i = 0; i < v.size(); ++i)
for(int j = 0; j < v.size(); ++j)
m[i][j] = v[i][j];
return m;
}
int main()
{
V v(x.size()*x.size()), w(y.size()*y.size()), t(z.size()*z.size());
s(make_array(x), v.data(), x.size(), 0);
for (auto i : v) std::cout << i << " ";
std::cout << "\n";
s(make_array(y), w.data(), y.size(), 0);
for (auto i : w) std::cout << i << " ";
std::cout << "\n";
s(make_array(z), t.data(), z.size(), 0);
for (auto i : t) std::cout << i << " ";
std::cout << "\n";
}
I2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgoKCnZvaWQgcyhpbnQqKm0saW50KnYsaW50IG4saW50IGgpe2ludCByPWgsYz1oLGk9MCxqLGw9bi0yKmgtMTtpZihsPi0xKXtkb3sqdisrPW1bcl1bY107bD8oaj1pL2wpPDE/YysrOmo8Mj9yKys6ajwzP2MtLTpyLS06bDt9d2hpbGUoKytpPDQqbCk7cyhtLHYsbixoKzEpO319Cgp1c2luZyBWPXN0ZDo6dmVjdG9yPGludD47CnN0ZDo6dmVjdG9yPFY+IHh7ezEsIDIsIDMsIDR9LCB7MTIsIDEzLCAxNCwgNX0sIHsxMSwgMTYsIDE1LCA2fSwgezEwLCA5LCA4LCA3fX07CnN0ZDo6dmVjdG9yPFY+IHl7ezEsIDIsIDN9LCB7OCwgOSwgNH0sIHs3LCA2LCA1fX07CnN0ZDo6dmVjdG9yPFY+IHo7CgppbnQqKiBtYWtlX2FycmF5KGNvbnN0IHN0ZDo6dmVjdG9yPFY+JiB2KQp7CiAgICBpbnQgKiptID0gbmV3IGludCpbdi5zaXplKCldOwogICAgZm9yKGludCBpID0gMDsgaSA8IHYuc2l6ZSgpOyArK2kpCiAgICAgICAgbVtpXSA9IG5ldyBpbnRbdi5zaXplKCldOwogICAgZm9yKGludCBpID0gMDsgaSA8IHYuc2l6ZSgpOyArK2kpCiAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IHYuc2l6ZSgpOyArK2opCiAgICAgICAgICAgIG1baV1bal0gPSB2W2ldW2pdOwogICAgcmV0dXJuIG07Cn0KCmludCBtYWluKCkKewogICAgViB2KHguc2l6ZSgpKnguc2l6ZSgpKSwgdyh5LnNpemUoKSp5LnNpemUoKSksIHQoei5zaXplKCkqei5zaXplKCkpOwogICAgcyhtYWtlX2FycmF5KHgpLCB2LmRhdGEoKSwgeC5zaXplKCksIDApOwogICAgZm9yIChhdXRvIGkgOiB2KSBzdGQ6OmNvdXQgPDwgaSA8PCAiICI7CiAgICBzdGQ6OmNvdXQgPDwgIlxuIjsKICAgIHMobWFrZV9hcnJheSh5KSwgdy5kYXRhKCksIHkuc2l6ZSgpLCAwKTsKICAgIGZvciAoYXV0byBpIDogdykgc3RkOjpjb3V0IDw8IGkgPDwgIiAiOwogICAgc3RkOjpjb3V0IDw8ICJcbiI7CiAgICBzKG1ha2VfYXJyYXkoeiksIHQuZGF0YSgpLCB6LnNpemUoKSwgMCk7CiAgICBmb3IgKGF1dG8gaSA6IHQpIHN0ZDo6Y291dCA8PCBpIDw8ICIgIjsKICAgIHN0ZDo6Y291dCA8PCAiXG4iOwp9Cgo=