10216. Magic Square

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

Task Description

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.

samplesample

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.

Subtask

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

Sample Input 1

5 1 1 2

Sample Output 1

11 18 25 2 9
17 24 1 8 15
23 5 7 14 16
4 6 13 20 22
10 12 19 21 3

Sample Input 2

4 3 2 1

Sample Output 2

7 9 15 1
12 14 4 6
13 3 5 11
2 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.

Discussion