题目描述

大家一定都听说过蛇形矩阵，也一定都听说过螺旋矩阵，但一定没有听过蛇形螺旋矩阵。所谓蛇形螺旋矩阵，是非常类似于螺旋矩阵的一种矩阵。它们仅有的不同之处在于：螺旋矩阵总是按顺时针方向旋转并填入相应数字，而蛇形螺旋矩阵每一圈的旋转方向是不固定的。

现在给出一个蛇形螺旋矩阵的大小，同时给出每一圈旋转的方向，请你制作出这个矩阵。（特别说明：第 i 圈的旋转是从（i，i）处开始的。）

输入

第一行一个正整数 n，表示蛇形螺旋矩阵的边长。

第二行（n+1）/2 个整数，第 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 ≤ n ≤ 100。

对于 100%的数据，1 ≤ n ≤ 1000。