10216. Magic Square

I'm a slow walker, but I never walk backwards.

A magic square is an $N \times N$ matrix filled with positive integers 1, 2, …, $N^2$ by the following steps:

First fill the initial position in the grid with number 1. After that, fill the diagonally up and right square one step at a time. If we encounter a filled square, moves vertically down one square. Then continue as before until the whole matrix is filled. Note that when an “up and right” or “down” move will leave the square, it is wrapped around to the last row, first column, or first row.

We can see the following figure to understand the steps that fills the matrix if we start from position (1, 2) with $N$ = 5. Note that the index of the matrix is from 0 to $N$ - 1, from top to down, from left to right.

sample

Now we give you the size of matrix $N$ and the position (x, y) where an integer k ranging from 1 to $N$ is placed. Write a program to construct the magic square.

Input Format

There are four integers $N, k, x$, and $y$ in a line.

• $1 \leq N \leq 1000$
• $1 \leq k \leq N$
• $0 \leq x, y \lt N$

Output Format

Print the magic square.

• 90 points: $k = 1$.
• 10 points: $k \leq N$.

Sample Input 1

5 1 1 2


Sample Output 1

11 18 25 2 917 24 1 8 1523 5 7 14 164 6 13 20 2210 12 19 21 3


Sample Input 2

4 3 2 1


Sample Output 2

7 9 15 112 14 4 613 3 5 112 8 10 16


Hint

Since $k \leq N$, there will be no up down position changes. Therefore we can move $k$ - 1 steps left-and-down to go back to the starting point. From there we just use the previous code for $k$ = 1.