题目描述

小婷和小泽听说过蛇形矩阵，也听说过螺旋矩阵。蛇形螺旋矩阵与普通螺旋矩阵很相似，但它的每一圈可以采用不同的旋转方向。

给定蛇形螺旋矩阵的边长，以及从外到内每一圈的旋转方向，请依次填入 $1,2,\ldots,n^2$ 并输出矩阵。第 $i$ 圈从位置 $(i,i)$ 开始填数。

输入格式

第一行包含一个正整数 $n$，表示矩阵的边长。

第二行包含 $\lceil n/2\rceil$ 个整数。第 $i$ 个整数表示从外向内第 $i$ 圈的旋转方向：1 表示顺时针，-1 表示逆时针。

输出格式

输出 $n$ 行，每行 $n$ 个用空格隔开的正整数。第 $i$ 行第 $j$ 个整数表示矩阵 $(i,j)$ 位置应填的数。

样例输入

7
1 -1 -1 1

样例输出

1 2 3 4 5 6 7
24 25 40 39 38 37 8
23 26 41 48 47 36 9
22 27 42 49 46 35 10
21 28 43 44 45 34 11
20 29 30 31 32 33 12
19 18 17 16 15 14 13

数据范围

对于 $50\%$ 的数据，$1\le n\le 100$。

对于 $100\%$ 的数据，$1\le n\le 1000$。

1
1

1

2
-1

1 4
2 3