A - QQ solver

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100

問題文

3 文字からなる文字列 S が与えられます。S は、1 以上 9 以下の整数 a, b と文字 x を、axb のように順につなげて得られます。

ab の積を求めてください。

制約

  • S の長さは 3
  • S1 文字目および 3 文字目は 1 以上 9 以下の整数を表す
  • S2 文字目は x

入力

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

S

出力

答えを出力せよ。


入力例 1

3x7

出力例 1

21

3 \times 7 = 21 であるので、これを出力します。


入力例 2

9x9

出力例 2

81

入力例 3

1x1

出力例 3

1

Score : 100 points

Problem Statement

You are given a 3-character string S, which is a concatenation of integers a and b between 1 and 9 (inclusive) and the character x in this order: axb.

Find the product of a and b.

Constraints

  • The length of S is 3.
  • The 1-st and 3-rd characters are digits between 1 and 9 (inclusive).
  • The 2-nd character is x.

Input

Input is given from Standard Input in the following format:

S

Output

Print the answer.


Sample Input 1

3x7

Sample Output 1

21

We have 3 \times 7 = 21, which should be printed.


Sample Input 2

9x9

Sample Output 2

81

Sample Input 3

1x1

Sample Output 3

1
B - Caesar Cipher

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200

問題文

高橋君は英小文字からなる文字列 S を持っています。

高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。

  • まず、非負整数 K を選ぶ。
  • その後、S の各文字を K 個後ろの英小文字に変更する。

ただし、

  • a1 個後ろの英小文字は b であり、
  • b1 個後ろの英小文字は c であり、
  • c1 個後ろの英小文字は d であり、
  • \cdots
  • y1 個後ろの英小文字は z であり、
  • z1 個後ろの英小文字は a です。

例えば、b4 個後ろの英小文字は f であり、y3 個後ろの英小文字は b です。

文字列 T が与えられます。 高橋君が上記の操作によって ST に一致させることができるかを判定してください。

制約

  • ST はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
  • S の長さと T の長さは等しい

入力

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

S
T

出力

高橋君が ST に一致させることができる場合は Yes と出力し、 できない場合は No と出力せよ。


入力例 1

abc
ijk

出力例 1

Yes

高橋君が K=8 を選ぶと、

  • a8 個後ろの i
  • b8 個後ろの j
  • c8 個後ろの k

それぞれ変更され、ST が一致します。
高橋君が ST に一致させることができるため Yes と出力します。


入力例 2

z
a

出力例 2

Yes

高橋君が K=1 を選ぶと ST が一致します。
z1 個後ろの英小文字は a であることに注意してください。


入力例 3

ppq
qqp

出力例 3

No

高橋君は非負整数 K をどのように選んでも ST に一致させることができません。 よって、No と出力します。


入力例 4

atcoder
atcoder

出力例 4

Yes

高橋君が K=0 を選ぶと ST が一致します。

Score : 200 points

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

  • First, choose a non-negative integer K.
  • Then, shift each character of S to the right by K (see below).

Here,

  • a shifted to the right by 1 is b;
  • b shifted to the right by 1 is c;
  • c shifted to the right by 1 is d;
  • \cdots
  • y shifted to the right by 1 is z;
  • z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

  • Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
  • The lengths of S and T are equal.

Input

Input is given from Standard Input in the following format:

S
T

Output

If Takahashi can make S equal T, print Yes; if not, print No.


Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

  • a is shifted to the right by 8 and becomes i,
  • b is shifted to the right by 8 and becomes j,
  • c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.


Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.


Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.


Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

C - Graph Isomorphism

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

高橋君と青木君は、それぞれ N 個のボールに M 本のひもを取り付けたおもちゃを持っています。

高橋君のおもちゃにおいて、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール A_i とボール B_i を結んでいます。

青木君のおもちゃにおいても同様に、ボールには 1, \dots, N と番号が付けられており、i \, (1 \leq i \leq M) 本目のひもはボール C_i とボール D_i を結んでいます。

それぞれのおもちゃにおいて、同一のボールを結ぶようなひもは存在せず、2 つのボールを 2 本以上の異なるひもが結んでいることはありません。

すぬけ君は、2 人のおもちゃが同じ形であるかどうか気になっています。
ここで、2 人のおもちゃが同じ形であるとは、以下の条件を満たす数列 P が存在することをいいます。

  • P(1, \dots, N) を並べ替えて得られる。
  • 任意の 1 以上 N 以下の整数 i, j に対し、以下が成り立つ。
    • 高橋君のおもちゃにおいてボール i, j がひもで繋がれていることと、青木君のおもちゃにおいてボール P_i, P_j がひもで繋がれていることは同値である。

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力してください。

制約

  • 1 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
  • (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
  • 入力は全て整数である。

入力

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

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

出力

2 人のおもちゃが同じ形であるなら Yes、そうでないなら No と出力せよ。


入力例 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

出力例 1

Yes

高橋君のおもちゃは下図の左側のような形をしており、青木君のおもちゃは下図の右側のような形をしています。

yes1

次の図から、2 人のおもちゃが同じ形であることがわかります。例えば P = (3, 2, 1, 4) とすると問題文中の条件を満たします。

yes2


入力例 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

出力例 2

No

2 人のおもちゃは同じ形ではありません。

no


入力例 3

8 0

出力例 3

Yes

Score : 300 points

Problem Statement

Takahashi and Aoki each have a toy made by attaching M cords to N balls.

In Takahashi's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball A_i and B_i.

Similarly, in Aoki's toy, the balls are numbered 1, \dots, N, and the i-th cord ties Ball C_i and D_i.

In each toy, no cord ties a ball to itself, and no two balls are tied by two or more different cords.

Snuke is wondering whether the two toys have the same shape.
Here, they are said to have the same shape when there is a sequence P that satisfies the conditions below.

  • P is a permutation of (1, \dots, N).
  • For every pair of integers i, j between 1 and N (inclusive), the following holds.
    • Balls i and j in Takahashi's toy are tied by a cord if and only if Balls P_i and P_j in Aoki's toy are tied by a cord.

If the two toys have the same shape, print Yes; otherwise, print No.

Constraints

  • 1 \leq N \leq 8
  • 0 \leq M \leq \frac{N(N - 1)}{2}
  • 1 \leq A_i \lt B_i \leq N \, (1 \leq i \leq M)
  • (A_i, B_i) \neq (A_j, B_j) \, (i \neq j)
  • 1 \leq C_i \lt D_i \leq N \, (1 \leq i \leq M)
  • (C_i, D_i) \neq (C_j, D_j) \, (i \neq j)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M
C_1 D_1
\vdots
C_M D_M

Output

If the two toys have the same shape, print Yes; otherwise, print No.


Sample Input 1

4 4
1 2
1 3
1 4
3 4
1 3
1 4
2 3
3 4

Sample Output 1

Yes

Takahashi's toy is illustrated on the left in the figure below, and Aoki's is illustrated on the right.

yes1

The following figure shows that the two toys have the same shape. The condition in the statement is satisfied when P = (3, 2, 1, 4), for example.

yes2


Sample Input 2

5 6
1 2
1 3
1 4
3 4
3 5
4 5
1 2
1 3
1 4
1 5
3 5
4 5

Sample Output 2

No

The two toys do not have the same shape.

no


Sample Input 3

8 0

Sample Output 3

Yes
D - Weak Takahashi

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 C_{i, j} で表され、C_{i, j} = . ならばマス (i, j) は空きマスであり、C_{i, j} = # ならばマス (i, j) は壁です。

高橋君がグリッド上を歩こうとしています。彼がマス (i, j) にいるとき、マス (i, j + 1) またはマス (i + 1, j) に移動することができます。ただし、グリッドの外に出るような移動や、壁のマスへの移動を行うことはできません。高橋君は、移動することのできるマスが無くなった時点で立ち止まります。

高橋君がマス (1, 1) から歩き始めるとき、彼が立ち止まるまでに通ることのできるマスは最大で何マスですか?

制約

  • 1 \leq H, W \leq 100
  • H, W は整数
  • C_{i, j} = . または C_{i, j} = # (1 \leq i \leq H, 1 \leq j \leq W)
  • C_{1, 1} = .

入力

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

H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}

出力

答えを出力せよ。


入力例 1

3 4
.#..
..#.
..##

出力例 1

4

例えば (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) と進むことで、4 マス通ることができます。

5 マス以上通ることはできないので、4 と出力します。


入力例 2

1 1
.

出力例 2

1

入力例 3

5 5
.....
.....
.....
.....
.....

出力例 3

9

Score : 400 points

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.

Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.

When starting on (1, 1), at most how many squares can Takahashi visit before he stops?

Constraints

  • 1 \leq H, W \leq 100
  • H and W are integers.
  • C_{i, j} = . or C_{i, j} = #. (1 \leq i \leq H, 1 \leq j \leq W)
  • C_{1, 1} = .

Input

Input is given from Standard Input in the following format:

H W
C_{1, 1} \ldots C_{1, W}
\vdots
C_{H, 1} \ldots C_{H, W}

Output

Print the answer.


Sample Input 1

3 4
.#..
..#.
..##

Sample Output 1

4

For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.

He cannot visit 5 or more squares, so we should print 4.


Sample Input 2

1 1
.

Sample Output 2

1

Sample Input 3

5 5
.....
.....
.....
.....
.....

Sample Output 3

9
E - Rook Path

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

H 行、横 W 行の H \times W マスからなるグリッドがあります。上から i 行目、左から j 列目のマスを (i, j) と表します。

はじめ、マス (x_1, y_1) にルークが置かれており、高橋君は以下の操作を K 回行います。

  • 現在ルークが置かれているマスと行または列が同じマスにルークを移動させる。ただし、現在ルークが置かれているマスとは異なるマスに移動させる必要がある。

K 回の操作の後、ルークがマス (x_2, y_2) に置かれているようにする方法は何通りありますか?答えは非常に大きくなることがあるので、998244353 で割った余りを求めてください。

制約

  • 2 \leq H, W \leq 10^9
  • 1 \leq K \leq 10^6
  • 1 \leq x_1, x_2 \leq H
  • 1 \leq y_1, y_2 \leq W

入力

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

H W K
x_1 y_1 x_2 y_2

出力

K 回の操作の後、ルークがマス (x_2, y_2) に置かれているようにする方法の総数を 998244353 で割った余りを出力せよ。


入力例 1

2 2 2
1 2 2 1

出力例 1

2

以下の 2 通りです。

  • 1 回目の操作でルークをマス (1, 2) からマス (1, 1) へ動かし、2 回目の操作でルークをマス (1, 1) からマス (2, 1) に動かす。
  • 1 回目の操作でルークをマス (1, 2) からマス (2, 2) へ動かし、2 回目の操作でルークをマス (2, 2) からマス (2, 1) に動かす。

入力例 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

出力例 2

24922282

998244353 で割った余りを求めなければならないことに注意して下さい。


入力例 3

3 3 3
1 3 3 3

出力例 3

9

Score : 500 points

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.

  • Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.

Constraints

  • 2 \leq H, W \leq 10^9
  • 1 \leq K \leq 10^6
  • 1 \leq x_1, x_2 \leq H
  • 1 \leq y_1, y_2 \leq W

Input

Input is given from Standard Input in the following format:

H W K
x_1 y_1 x_2 y_2

Output

Print the number of ways to do the K operations so that the rook will be on (x_2, y_2) in the end, modulo 998244353.


Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

  • First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
  • First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo 998244353.


Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9
F - Simple Operations on Sequence

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

長さ N2 つの整数列 A = (A_1, A_2, \ldots, A_N) および B = (B_1, B_2 \ldots, B_N) が与えられます。

整数列 A に対して、「下記の 2 つの操作のうちどちらかを行う」ということを好きな回数( 0 回でもよい)繰り返すことができます。

  • 1 \leq i \leq N を満たす整数 i を選び、A_i の値を 1 増やすか 1 減らす。この操作には X 円の費用がかかる。
  • 1 \leq i \leq N-1 を満たす整数 i を選び、A_i の値と A_{i+1} の値を入れ替える。この操作には Y 円の費用がかかる。

上記の繰り返しによって整数列 A を整数列 B に一致させるためにかかる合計費用としてあり得る最小値を出力してください。

制約

  • 2 \leq N \leq 18
  • 1 \leq X \leq 10^8
  • 1 \leq Y \leq 10^{16}
  • 1 \leq A_i, B_i \leq 10^8
  • 入力はすべて整数

入力

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

N X Y
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

AB に一致させるためにかかる合計費用としてあり得る最小値を求めよ。


入力例 1

4 3 5
4 2 5 2
6 4 2 1

出力例 1

16

はじめ、A = (4, 2, 5, 2) です。
下記の通りに操作を行うと、AB に一致させることができます。

  • X = 3 円払い、A_3 の値を 1 増やす。その結果 A = (4, 2, 6, 2) となる。
  • Y = 5 円払い、A_2 の値と A_3 の値を入れ替える。その結果 A = (4, 6, 2, 2) となる。
  • Y = 5 円払い、A_1 の値と A_2 の値を入れ替える。その結果 A = (6, 4, 2, 2) となる。
  • X = 3 円払い、A_4 の値を 1 減らす。その結果 A = (6, 4, 2, 1) = B となる。

上記の操作にかかる費用の合計は 3+5+5+3 = 16 円であり、これが最小となります。


入力例 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

出力例 2

0

AB は初めから一致しているため、一度も操作を行う必要がありません。


入力例 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

出力例 3

13104119429316474

入力や出力が 32 bit 整数型に収まらないことがあることに注意してください。

Score : 500 points

Problem Statement

Given are two sequences of N integers each: A = (A_1, A_2, \ldots, A_N) and B = (B_1, B_2 \ldots, B_N).

On the sequence A, you can do the two operations below any number of times (possibly zero) in any order.

  • Choose an integer i satisfying 1 \leq i \leq N, and increase or decrease A_i by 1, for the cost of X yen (Japanese currency).
  • Choose an integer i satisfying 1 \leq i \leq N-1, and swap the values of A_i and A_{i+1}, for the cost of Y yen.

Print the minimum total cost needed to make the sequence A equal the sequence B by repeating the above.

Constraints

  • 2 \leq N \leq 18
  • 1 \leq X \leq 10^8
  • 1 \leq Y \leq 10^{16}
  • 1 \leq A_i, B_i \leq 10^8
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Print the minimum total cost needed to make A equal B.


Sample Input 1

4 3 5
4 2 5 2
6 4 2 1

Sample Output 1

16

Initialy, we have A = (4, 2, 5, 2).
The following sequence of operations makes A equal B.

  • Pay X = 3 yen to increase the value of A_3 by 1, making A = (4, 2, 6, 2).
  • Pay Y = 5 yen to swap the values of A_2 and A_3, making A = (4, 6, 2, 2).
  • Pay Y = 5 yen to swap the values of A_1 and A_2, making A = (6, 4, 2, 2).
  • Pay X = 3 yen to decrease the value of A_4 by 1, making A = (6, 4, 2, 1).

The total cost of these operations is 3+5+5+3 = 16 yen, which is the minimum possible.


Sample Input 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

Sample Output 2

0

A and B are equal from the beginning, so no operation is needed.


Sample Input 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

Sample Output 3

13104119429316474

Note that values in input or output may not fit into 32-bit integer types.

G - Modulo Shortest Path

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600

問題文

N 頂点の有向グラフがあります。N 個の頂点はそれぞれ頂点 1、頂点 2\ldots、頂点 N と呼ばれます。

1 \leq i, j \leq N かつ i \neq j を満たす整数の組 (i, j) それぞれに対して、 頂点 i を始点、頂点 j を終点とする重み (A_i + B_j) \bmod M の有向辺があります。 (ただし、x \bmod yxy で割ったあまりを表します。)

上記のほかに辺はありません。

頂点 1 から頂点 N への最短距離、すなわち、頂点 1 から頂点 N へのパス上の辺の重みの総和として考えられる最小値を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • 0 \leq A_i, B_j < M
  • 入力はすべて整数

入力

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

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

頂点 1 から頂点 N へのパス上の辺の重みの総和として考えられる最小値を出力せよ。


入力例 1

4 12
10 11 6 0
8 7 4 1

出力例 1

3

以下では、頂点 i を始点、頂点 j を終点とする有向辺を i \rightarrow j で表します。
1 \rightarrow 3 \rightarrow 2 \rightarrow 4 というパスを考えると、

  • 1 \rightarrow 3 の重みは、(A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2 であり、
  • 3 \rightarrow 2 の重みは、(A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1 であり、
  • 2 \rightarrow 4 の重みは、(A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0 です。

よって、このパスの辺の重みの総和は 2 + 1 + 0 = 3 です。
これが頂点 1 から頂点 N へのパス上の辺の重みの総和として考えられる最小値となります。


入力例 2

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

出力例 2

462

Score : 600 points

Problem Statement

We have a directed graph with N vertices, called Vertex 1, Vertex 2, \ldots, Vertex N.

For each pair of integers such that 1 \leq i, j \leq N and i \neq j, there is a directed edge from Vertex i to Vertex j of weight (A_i + B_j) \bmod M. (Here, x \bmod y denotes the remainder when x is divided by y.)

There is no edge other than the above.

Print the shortest distance from Vertex 1 to Vertex N, that is, the minimum possible total weight of the edges in a path from Vertex 1 to Vertex N.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • 0 \leq A_i, B_j < M
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

Output

Print the minimum possible total weight of the edges in a path from Vertex 1 to Vertex N.


Sample Input 1

4 12
10 11 6 0
8 7 4 1

Sample Output 1

3

Below, i \rightarrow j denotes the directed edge from Vertex i to Vertex j.
Let us consider the path 1 \rightarrow 3 \rightarrow 2 \rightarrow 4.

  • Edge 1\rightarrow 3 weighs (A_1 + B_3) \bmod M = (10 + 4) \bmod 12 = 2,
  • Edge 3 \rightarrow 2 weighs (A_3 + B_2) \bmod M = (6 + 7) \bmod 12 = 1,
  • Edge 2\rightarrow 4 weighs (A_2 + B_4) \bmod M = (11 + 1) \bmod 12 = 0.

Thus, the total weight of the edges in this path is 2 + 1 + 0 = 3.
This is the minimum possible sum for a path from Vertex 1 to Vertex N.


Sample Input 2

10 1000
785 934 671 520 794 168 586 667 411 332
363 763 40 425 524 311 139 875 548 198

Sample Output 2

462
H - King's Tour

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

縦横 H \times W のチェス盤と 1 個のキングの駒があります。
チェス盤のマスのうち、上から i 行目 (1 \leq i \leq H) で左から j 行目 (1 \leq j \leq W) のマスを (i, j) と表します。
キングは置かれているマスから周囲 1 マスに動かすことができます。より厳密には、チェス盤のマス目の組 (i, j), (k, l)\max(|i-k|,|j-l|) = 1 を満たすとき、かつその時に限り (i,j) に置かれているキングを (k, l) に動かすことができます。

次の条件を満たすようにキングを縦横 H \times W のチェス盤上で動かすことを「ツアー」と定めます。

  • はじめ、(1, 1) にキングを置く。そのあと、キングが全てのマスにちょうど 1 回ずつ置かれるようにキングを動かす。

たとえば、H = 2, W = 3 のとき、(1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) の順にキングを動かしたものは条件を満たします。

チェス盤上の (1,1) 以外のマス (a, b) が与えられます。ツアーのうち最後にキングが置かれているマスが (a,b) となるものを 1 つ構成して出力してください。この問題の制約下において解は必ず存在することが証明できます。

制約

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • 1 \leq a \leq H
  • 1 \leq b \leq W
  • (a, b) \neq (1, 1)
  • 入力はすべて整数である。

入力

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

H W a b

出力

HW 行出力せよ。i 行目には i 番目にキングが置かれたマス (h_i, w_i) を以下の形式で出力せよ。

h_i w_i

ここで、1 行目は (1, 1)HW 行目は (a, b) を出力する必要がある点に注意せよ。


入力例 1

3 2 3 2

出力例 1

1 1
1 2
2 1
2 2
3 1
3 2

キングは (1, 1) \to (1, 2) \to (2, 1) \to (2, 2)\to (3, 1) \to (3, 2) と移動して、これは確かに (3,2) を終点とするツアーとなっています。
条件を満たすツアーは他にもいくつかあり、たとえば以下の 3 つの移動が挙げられます。

  • (1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2)
  • (1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to (3, 1) \to (3, 2)
  • (1, 1) \to (2, 2) \to (1, 2) \to (2, 1) \to (3, 1) \to (3, 2)

Score : 600 points

Problem Statement

We have an H \times W chessboard with H rows and W columns, and a king.
Let (i, j) denote the square at the i-th row from the top (1 \leq i \leq H) and j-th column from the left (1 \leq j \leq W).
The king can move one square in any direction. Formally, the king on (i,j) can move to (k,l) if and only if \max(|i-k|,|j-l|) = 1.

A tour is the process of moving the king on the H \times W chessboard as follows.

  • Start by putting the king on (1, 1). Then, move the king to put it on each square exactly once.

For example, when H = 2, W = 3, going (1,1) \to (1,2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) is a valid tour.

You are given a square (a, b) other than (1, 1). Construct a tour ending on (a,b) and print it. It can be proved that a solution always exists under the Constraints of this problem.

Constraints

  • 2 \leq H \leq 100
  • 2 \leq W \leq 100
  • 1 \leq a \leq H
  • 1 \leq b \leq W
  • (a, b) \neq (1, 1)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

H W a b

Output

Print HW lines. The i-th line should contain the i-th square (h_i, w_i) the king is put on, in the following format:

h_i w_i

Here, note that the 1-st line should contain (1, 1), and the HW-th line should contain (a, b).


Sample Input 1

3 2 3 2

Sample Output 1

1 1
1 2
2 1
2 2
3 1
3 2

The king goes (1, 1) \to (1, 2) \to (2, 1) \to (2, 2)\to (3, 1) \to (3, 2), which is indeed a tour ending on (3, 2).
There are some other valid tours, three of which are listed below.

  • (1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2)
  • (1, 1) \to (2, 1) \to (1, 2) \to (2, 2) \to (3, 1) \to (3, 2)
  • (1, 1) \to (2, 2) \to (1, 2) \to (2, 1) \to (3, 1) \to (3, 2)