1,000,000

N

M

N \times M

0

0

i

j

(i, j)

G[i][j]

2

(a, b), (c, d)

a \gt c

b, d

G[a][b] \geq G[c][d]

2

N

M

(a, b)

(c, d)

|a - c| + |b - d|

入力は以下の形式で標準入力から与えられる。

 N   M
 x_0   a   p

• $1$ 行目には、教室の行の数、列の数をあらわす整数 $N$ , $M$ ( $1 ≦ N, M ≦ 1,000$ )が空白区切りで与えられる。
• $2$ 行目には、各席に座っている生徒の成績のデータを生成する乱数の種 $x_0$ ( $0 ≦ x_0 ≦ 10^9$ ), $a$ ( $0 ≦ a ≦ 10^9$ ), $p$ ( $N \times M ≦ p ≦ 10^9$ , $p$ は常に素数)が空白区切りで与えられる。 席の数が非常に多いため、席替え前の各席に座っている生徒の成績は上記の3つの変数を種に生成してもらう。 $i \geq 1$ について $x_i = (x_{i-1} + a) mod p$ の漸化式で与えられる数列 $x$ を考える。 $(i, j)$ に席替え前に座っている生徒の成績は $x_{i \times m + j}$ とする。

2 3
1 2 59

0

1  3  5
7  9 11

2 3
6 55 59

2

 6  2 57
53 49 45

(0, 2)

(1, 2)

1

2

4 5
15 25 79

26

15 40 65 11 36
61  7 32 57  3
28 53 78 24 49
74 20 45 70 16

15  7 16 11  3
28 20 32 24 36
53 40 45 57 49
74 61 65 70 78