Theater Seating

Time limit1sMemory limit128 MB

Summary

Assign each seat a priority by Euclidean distance to the middle of row 1, breaking ties by row then by seat number, and print rows back to front.

Level: Easy3 of 10
Topics: Sorting, Math, Implementation
Solved: No attempts yet

Problem

A theater has seats arranged in a rectangle: an odd number of seats per row, the width $W$ ( $11 \le W \le 101$ ), and $R$ rows ( $4 \le R \le 50$ ). Within a row the seats are numbered $1$ to $W$ from left to right (as seen from the stage), and the rows are numbered $1$ to $R$ starting from the row closest to the stage. Adjacent seats in the same row are one unit apart, and this spacing equals the distance between a seat and the seat directly in front of or behind it in an adjacent row. So seat $s$ in row $r$ occupies the grid point $(s, r)$ .

Tickets are sold online with automatic seat assignment, so every seat is given a unique priority, where priority $1$ is the best. Priorities are assigned by these rules:

The middle seat of row $1$ (the row closest to the stage), at position $\left(\frac{W+1}{2},\ 1\right)$ , gets the best priority, $1$ .
Every other seat is ranked by its Euclidean distance to that best seat: the closer a seat is, the better (smaller) its priority.
Among seats that are exactly the same distance away, a seat in a row closer to the stage (a smaller row number) gets the better priority.
Among seats that are the same distance away and in the same row, the seat closer to seat number $1$ (the left-most seat) gets the better priority.

Because $(x, y)$ is unique for every seat, these rules assign a distinct priority to each of the $W \cdot R$ seats. Write a program that prints the resulting priority chart for a given width and number of rows.

Input

The only line contains two space-separated integers $W$ and $R$ , where $W$ is odd, $11 \le W \le 101$ , and $4 \le R \le 50$ .

Output

Print $R$ lines. For $i = 1, 2, \ldots, R$ , line $i$ contains the $W$ priorities of the seats in row $R - i + 1$ , listed from seat $1$ to seat $W$ and separated by single spaces. In other words, print the rows from the back of the theater (row $R$ ) down to the front row (row $1$ ).

Examples3

Example 1

Input

11 5

Expected output

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

Example 2

Input

11 4

Expected output

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

Example 3

Input

13 4

Expected output

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