A - CAPS LOCK

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

英小文字のみからなる文字列 S が与えられます。

S の各文字を英大文字に変換して得られる文字列 T を出力してください。

制約

  • S は英小文字のみからなる、長さが 1 以上 100 以下の文字列

入力

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

S

出力

T を出力せよ。


入力例 1

abc

出力例 1

ABC

abc の各文字を英大文字に変換すると ABC になります。


入力例 2

a

出力例 2

A

入力例 3

abcdefghjiklnmoqprstvuwxyz

出力例 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.

Uppercase each character of S and print the resulting string T.

Constraints

  • S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Input

The input is given from Standard Input in the following format:

S

Output

Print T.


Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.


Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ
B - Digit Machine

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

1 桁の数字が表示される画面と、ボタンからなる機械があります。

画面に数字 k が表示されているとき、ボタンを 1 回押すと画面の数字が a_k に変わります。

0 が表示されている状態からボタンを 3 回押すと、画面には何が表示されますか?

制約

  • 0\leq a_i \leq 9
  • 入力は全て整数である

入力

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

a_0 a_1 \dots a_9

出力

答えを出力せよ。


入力例 1

9 0 1 2 3 4 5 6 7 8

出力例 1

7

画面に表示される数字は、0 \rightarrow 9 \rightarrow 8 \rightarrow 7 と変化します。


入力例 2

4 8 8 8 0 8 8 8 8 8

出力例 2

4

画面に表示される数字は、0 \rightarrow 4 \rightarrow 0 \rightarrow 4 と変化します。


入力例 3

0 0 0 0 0 0 0 0 0 0

出力例 3

0

Score : 100 points

Problem Statement

There is a device with a screen that shows a single-digit number, and a button.

When the screen is showing a number k, pressing the button once changes the number on the screen to a_k.

The device currently shows 0. After pressing the button 3 times, what will be shown on the screen?

Constraints

  • 0\leq a_i \leq 9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

a_0 a_1 \dots a_9

Output

Print the answer.


Sample Input 1

9 0 1 2 3 4 5 6 7 8

Sample Output 1

7

The number on the screen transitions as 0 \rightarrow 9 \rightarrow 8 \rightarrow 7.


Sample Input 2

4 8 8 8 0 8 8 8 8 8

Sample Output 2

4

The number on the screen transitions as 0 \rightarrow 4 \rightarrow 0 \rightarrow 4.


Sample Input 3

0 0 0 0 0 0 0 0 0 0

Sample Output 3

0
C - Compression

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

A に含まれる数を重複を除いて小さい順に出力してください。

制約

  • 1\le N\le 100
  • 1\le A_i\le 100
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

A に含まれる数を小さい順に C_1,C_2,\ldots , C_M として、以下の形式で出力せよ。

M
C_1 C_2 \ldots C_M

入力例 1

4
3 1 4 1

出力例 1

3
1 3 4

A=(3,1,4,1) に含まれる数は小さい順に 1,3,4 の 3 つです。したがって、上記のように出力してください。


入力例 2

3
7 7 7

出力例 2

1
7

入力例 3

8
19 5 5 19 5 19 4 19

出力例 3

3
4 5 19

Score : 150 points

Problem Statement

An integer sequence A=(A_1,A_2,\ldots,A_N) of length N is given.

Output the numbers contained in A in ascending order, removing duplicates.

Constraints

  • 1\le N\le 100
  • 1\le A_i\le 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Let C_1,C_2,\ldots , C_M be the numbers contained in A in ascending order. Output in the following format:

M
C_1 C_2 \ldots C_M

Sample Input 1

4
3 1 4 1

Sample Output 1

3
1 3 4

The numbers contained in A=(3,1,4,1) are 1,3,4 in ascending order, totalling 3 distinct numbers. Therefore, output as shown above.


Sample Input 2

3
7 7 7

Sample Output 2

1
7

Sample Input 3

8
19 5 5 19 5 19 4 19

Sample Output 3

3
4 5 19
D - Sum of Digits Sequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 x に対して、f(x) を x の十進表記における各桁の和として定義します。例えば、f(123) = 1 + 2 + 3 = 6 です。

無限数列 A = (A_0, A_1, A_2, \ldots) を以下の式により定義します。

  • A_0 = 1
  • i \geq 1 のとき A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

正整数 N が与えられます。A_N の値を求めてください。

制約

  • N は 1 以上 100 以下の整数

入力

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

N

出力

答えを出力せよ。


入力例 1

6

出力例 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

であるため、A_6 = 23 です。


入力例 2

45

出力例 2

427

Score : 200 points

Problem Statement

For a positive integer x, define f(x) as the sum of the digits in the decimal representation of x. For example, f(123) = 1 + 2 + 3 = 6.

Define an infinite sequence A = (A_0, A_1, A_2, \ldots) by the following formula:

  • A_0 = 1
  • For i \geq 1, A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)

You are given a positive integer N. Find the value of A_N.

Constraints

  • N is an integer between 1 and 100, inclusive.

Input

The input is given from Standard Input in the following format:

N

Output

Print the answer.


Sample Input 1

6

Sample Output 1

23
  • A_0 = 1
  • A_1 = f(A_0) = 1
  • A_2 = f(A_0) + f(A_1) = 2
  • A_3 = f(A_0) + f(A_1) + f(A_2) = 4
  • A_4 = f(A_0) + f(A_1) + f(A_2) + f(A_3) = 8
  • A_5 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) = 16
  • A_6 = f(A_0) + f(A_1) + f(A_2) + f(A_3) + f(A_4) + f(A_5) = 23

Thus, A_6 = 23.


Sample Input 2

45

Sample Output 2

427
E - Circular Playlist

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 曲からなるプレイリストがあり、曲には 1, \dots, N の番号が付けられています。
曲 i の長さは A_i 秒です。

プレイリストを再生すると、曲 1、曲 2、\ldots、曲 N の順に流れます。曲 N が流れ終わると、再び曲 1 から順に流れていきます。ある曲の途中で次の曲が流れることはなく、曲が流れ終わると、その瞬間に次の曲が流れ始めます。

プレイリストを再生してから T 秒後に流れているのはどの曲ですか?また、その曲が流れ始めてから何秒の時点ですか?
ただし、T 秒後ちょうどに曲が切り替わるような入力は与えられません。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • プレイリストを再生して T 秒後ちょうどに曲が切り替わることはない
  • 入力される値は全て整数

入力

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

N T
A_1 \ldots A_N

出力

プレイリストを再生してから T 秒後に流れている曲の番号と、その曲が流れ始めてから何秒たったかを表す整数を空白区切りで出力せよ。


入力例 1

3 600
180 240 120

出力例 1

1 60

プレイリストを再生してからの様子は次のようになります。

  • 0 秒後から 180 秒後まで曲 1 が流れる。
  • 180 秒後から 420 秒後まで曲 2 が流れる。
  • 420 秒後から 540 秒後まで曲 3 が流れる。
  • 540 秒後から 720 秒後まで曲 1 が流れる。
  • 720 秒後から 960 秒後まで曲 2 が流れる。
  • \qquad\vdots

600 秒後の時点で流れているのは曲 1 であり、流れ始めて 60 秒の時点です。


入力例 2

3 281
94 94 94

出力例 2

3 93

入力例 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

6 678912340

Score : 300 points

Problem Statement

We have a playlist with N songs numbered 1, \dots, N.
Song i lasts A_i seconds.

When the playlist is played, song 1, song 2, \ldots, and song N play in this order. When song N ends, the playlist repeats itself, starting from song 1 again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.

At exactly T seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly T seconds after it starts playing.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • The playlist does not change songs at exactly T seconds after it starts playing.
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N T
A_1 \ldots A_N

Output

Print an integer representing the song that is playing at exactly T seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.


Sample Input 1

3 600
180 240 120

Sample Output 1

1 60

When the playlist is played, the following happens. (Assume that it starts playing at time 0.)

  • From time 0 to time 180, song 1 plays.
  • From time 180 to time 420, song 2 plays.
  • From time 420 to time 540, song 3 plays.
  • From time 540 to time 720, song 1 plays.
  • From time 720 to time 960, song 2 plays.
  • \qquad\vdots

At time 600, song 1 is playing, and 60 seconds have passed since the start of that song.


Sample Input 2

3 281
94 94 94

Sample Output 2

3 93

Sample Input 3

10 5678912340
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

6 678912340
F - 1D puyopuyo

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。

あなたは以下の操作を 0 回以上好きな順番で好きな回数行うことができます:

  • A_k=A_{k+1}=A_{k+2}=A_{k+3} を満たす 1 以上 |A|-3 以下の整数 k を選び、A から A_k,A_{k+1},A_{k+2},A_{k+3} を削除する。(より厳密には、 A を (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N) に置き換える。)

ここで、 |A| は整数列 A の長さを表します。

操作を繰り返した後の最終的な |A| としてあり得る最小値を求めてください。

制約

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le N
  • 入力される値は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

操作を繰り返した後の最終的な |A| としてあり得る最小値を出力せよ。


入力例 1

10
1 1 1 4 4 4 4 1 2 3

出力例 1

2

以下のように 2 回操作することで |A|=2 にすることができます。

  • k=4 を選ぶ。A_4=A_5=A_6=A_7=4 が成り立つためこの選択は正当である。 A=(1,1,1,1,2,3) となる。
  • k=1 を選ぶ。A_1=A_2=A_3=A_4=1 が成り立つためこの選択は正当である。 A=(2,3) となる。

|A| を 2 未満にすることはできないため、 2 を出力してください。


入力例 2

3
2 1 3

出力例 2

3

はじめから操作を行うことができません。


入力例 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

出力例 3

5

Score : 300 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N.

You can perform the following operation zero or more times in any order:

  • Choose an integer k between 1 and |A|-3, inclusive, such that A_k=A_{k+1}=A_{k+2}=A_{k+3}, and remove A_k,A_{k+1},A_{k+2},A_{k+3} from A. (More formally, replace A with (A_1,A_2,\ldots,A_{k-1},A_{k+4},A_{k+5},\ldots,A_N).)

Here, |A| represents the length of the integer sequence A.

Find the minimum possible value of the final |A| after repeating the operation.

Constraints

  • 1\le N\le 2\times 10^5
  • 1\le A_i\le N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Output the minimum possible value of the final |A| after repeating the operation.


Sample Input 1

10
1 1 1 4 4 4 4 1 2 3

Sample Output 1

2

You can make |A|=2 with two operations as follows:

  • Choose k=4. This choice is valid since A_4=A_5=A_6=A_7=4 holds. A=(1,1,1,1,2,3) is obtained.
  • Choose k=1. This choice is valid since A_1=A_2=A_3=A_4=1 holds. A=(2,3) is obtained.

It is impossible to make |A| less than 2, so output 2.


Sample Input 2

3
2 1 3

Sample Output 2

3

You cannot perform any operation from the beginning.


Sample Input 3

13
1 1 4 4 4 1 1 1 1 4 1 4 1

Sample Output 3

5
G - Square Permutation

Time Limit: 4 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

数字のみからなる、長さ N の文字列 S が与えられます。

S を並べ替えてできる文字列を十進法の整数として解釈したもののうち、平方数であるようなものがいくつあるか求めてください。

より厳密には、次のようになります。

S の先頭から i 番目 (1\leq i\leq N) の数字に対応する数を s _ i とします。

(1, \ldots, N) の順列 P=(p _ 1,p _ 2,\ldots,p _ N) によって \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} と書ける整数のうち、平方数であるようなものがいくつあるか求めてください。

制約

  • 1\leq N\leq 13
  • S は数字のみからなる長さ N の文字列
  • N は整数

入力

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

N
S

出力

答えを 1 行で出力せよ。


入力例 1

4
4320

出力例 1

2

P=(4,2,3,1) とすると、s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2 となります。
P=(3,2,4,1) とすると、s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2 となります。

これら以外の並べ替え方では平方数にならないため、2 を出力してください。


入力例 2

3
010

出力例 2

2

P=(1,3,2) もしくは P=(3,1,2) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2 となります。
P=(2,1,3) もしくは P=(2,3,1) とすると、\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2 となります。

これら以外の並べ替え方では平方数にならないため、2 を出力してください。 異なる並べ替え方でも、並べ替えた結果の数が同じなら 1 つと数えることに注意してください。


入力例 3

13
8694027811503

出力例 3

840

Score : 425 points

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

  • 1\leq N\leq 13
  • S is a string of length N consisting of digits.
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer in a single line.


Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.


Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.


Sample Input 3

13
8694027811503

Sample Output 3

840
H - Grid Filling

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

縦 H 行、横 W 列のグリッドがあります。 上から i 行目、左から j 列目のマスを (i,j) で表します。 (i,j)\ (1\leq i\leq H,1\leq j\leq W) には 1 以上 N 以下の整数 A _ {i,j} が書かれています。

整数 h,w が与えられます。0\leq k\leq H-h,0\leq l\leq W-w を満たすすべての (k,l) の組について、次の問題を解いてください。

  • k\lt i\leq k+h,l\lt j\leq l+w を満たす (i,j) を塗りつぶしたとき、塗りつぶされていないマスに書かれている数が何種類あるか求めよ。

ただし、問題を解く際に実際にマスを塗りつぶすことはない(各問題が独立である)ことに注意してください。

制約

  • 1 \leq H,W,N \leq 300
  • 1 \leq h \leq H
  • 1 \leq w \leq W
  • (h,w)\neq(H,W)
  • 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
  • 入力される値はすべて整数

入力

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

H W N h w
A _ {1,1} A _ {1,2} \dots A _ {1,W}
A _ {2,1} A _ {2,2} \dots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \dots A _ {H,W}

出力

(k,l) に対する答えを \operatorname{ans}_{k,l} として、以下の形式で出力せよ。

\operatorname{ans} _ {0,0} \operatorname{ans} _ {0,1} \dots \operatorname{ans} _ {0,W-w}
\operatorname{ans} _ {1,0} \operatorname{ans} _ {1,1} \dots \operatorname{ans} _ {1,W-w}
\vdots
\operatorname{ans} _ {H-h,0} \operatorname{ans} _ {H-h,1} \dots \operatorname{ans} _ {H-h,W-w}

入力例 1

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

出力例 1

4 4 3
5 3 4

与えられた盤面は下の図のようになります。

例えば、(k,l)=(0,0) のときは塗りつぶされていないマスに書かれている数は 1,3,4,5 の 4 種類なので、4 が答えになります。


入力例 2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

出力例 2

8 8 7
8 9 7
8 9 8

入力例 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

出力例 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17

Score : 500 points

Problem Statement

You have a grid with H rows from top to bottom and W columns from left to right. We denote by (i, j) the square at the i-th row from the top and j-th column from the left. (i,j)\ (1\leq i\leq H,1\leq j\leq W) has an integer A _ {i,j} between 1 and N written on it.

You are given integers h and w. For all pairs (k,l) such that 0\leq k\leq H-h and 0\leq l\leq W-w, solve the following problem:

  • If you black out the squares (i,j) such that k\lt i\leq k+h and l\lt j\leq l+w, how many distinct integers are written on the squares that are not blacked out?

Note, however, that you do not actually black out the squares (that is, the problems are independent).

Constraints

  • 1 \leq H,W,N \leq 300
  • 1 \leq h \leq H
  • 1 \leq w \leq W
  • (h,w)\neq(H,W)
  • 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W)
  • All values in the input are integers.

Input

The input is given from Standard Input in the following format:

H W N h w
A _ {1,1} A _ {1,2} \dots A _ {1,W}
A _ {2,1} A _ {2,2} \dots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \dots A _ {H,W}

Output

Print the answers in the following format, where \operatorname{ans}_{k,l} denotes the answer to (k, l):

\operatorname{ans} _ {0,0} \operatorname{ans} _ {0,1} \dots \operatorname{ans} _ {0,W-w}
\operatorname{ans} _ {1,0} \operatorname{ans} _ {1,1} \dots \operatorname{ans} _ {1,W-w}
\vdots
\operatorname{ans} _ {H-h,0} \operatorname{ans} _ {H-h,1} \dots \operatorname{ans} _ {H-h,W-w}

Sample Input 1

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

Sample Output 1

4 4 3
5 3 4

The given grid is as follows:

For example, when (k,l)=(0,0), four distinct integers 1,3,4, and 5 are written on the squares that are not blacked out, so 4 is the answer.


Sample Input 2

5 6 9 3 4
7 1 5 3 9 5
4 5 4 5 1 2
6 1 6 2 9 7
4 7 1 5 8 8
3 4 3 3 5 3

Sample Output 2

8 8 7
8 9 7
8 9 8

Sample Input 3

9 12 30 4 7
2 2 2 2 2 2 2 2 2 2 2 2
2 2 20 20 2 2 5 9 10 9 9 23
2 29 29 29 29 29 28 28 26 26 26 15
2 29 29 29 29 29 25 25 26 26 26 15
2 29 29 29 29 29 25 25 8 25 15 15
2 18 18 18 18 1 27 27 25 25 16 16
2 19 22 1 1 1 7 3 7 7 7 7
2 19 22 22 6 6 21 21 21 7 7 7
2 19 22 22 22 22 21 21 21 24 24 24

Sample Output 3

21 20 19 20 18 17
20 19 18 19 17 15
21 19 20 19 18 16
21 19 19 18 19 18
20 18 18 18 19 18
18 16 17 18 19 17
I - Eat and Ride

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点 M 辺の連結無向グラフがあります。 頂点には頂点 1, 頂点 2,\ldots, 頂点 N と番号付けられており、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

i=1,2,\ldots,N について次の問題を解いてください。

はじめ、高橋くんの体重は 0 です。

高橋くんは、車に乗って頂点 1 に訪れ、頂点 i に向かって移動を行います。 高橋くんが頂点 v\ (1\le v\le N) に訪れるとき、高橋くんの体重は W _ v だけ増加します。

高橋くんが乗っている車は辺に沿って移動することができます。 高橋くんが辺を通過するとき、そのときの高橋くんの体重を X として、車は燃料を X 消費します。

高橋くんが頂点 i にたどり着くために消費する燃料の量の最小値を求めてください。

制約

  • 1\le N\le5000
  • 1\le M\le5000
  • 1\le W _ i\le10 ^ 9\ (1\le i\le N)
  • 1\le u _ i\le v _ i\le N\ (1\le i\le M)
  • 与えられるグラフは連結
  • 入力はすべて整数

入力

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

N M
W _ 1 W _ 2 \ldots W _ N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

出力

N 行にわたって出力せよ。 i 行目 (1\le i\le N) には、高橋くんが頂点 i にたどり着くのに必要な燃料の量を出力せよ。


入力例 1

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

出力例 1

0
3
3
7
10

与えられたグラフは以下のようになります。

例えば、高橋くんは頂点 1 に訪れてから次のように行動することで頂点 5 にたどり着くことができます。

  • 高橋くんが頂点 1 に訪れる。高橋くんの体重が 3 増加し、3 になる。
  • 高橋くんが燃料を 3 消費して頂点 3 に移動する。高橋くんの体重が 4 増加し、7 になる。
  • 高橋くんが燃料を 7 消費して頂点 5 に移動する。高橋くんの体重が 5 増加し、12 になる。

このように行動することで燃料を 10 だけ消費して頂点 5 にたどり着くことができます。 消費する燃料を 9 以下にすることはできないため、5 行目には 10 を出力してください。


入力例 2

5 4
1000000000 1000000000 1000000000 1000000000 1000000000
1 2
2 3
3 4
4 5

出力例 2

0
1000000000
3000000000
6000000000
10000000000

答えが 2 ^ {32} を越える場合があることに注意してください。


入力例 3

10 20
74931 58277 33783 91022 53003 11085 65924 63548 78622 77307
1 8
3 6
5 10
4 6
1 3
1 7
2 6
7 10
8 9
3 4
4 4
4 6
6 6
5 10
1 7
4 5
1 2
3 7
2 3
5 8

出力例 3

0
74931
74931
183645
213410
183645
74931
74931
213410
215786

Score : 500 points

Problem Statement

There is a connected undirected graph with N vertices and M edges. The vertices are numbered vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

For i=1,2,\ldots,N, solve the following problem:

Initially, Takahashi's weight is 0.

He travels by car to visit vertex 1 and moves toward vertex i. When he visits vertex v\ (1\le v\le N), his weight increases by W _ v.

The car he is riding can move along the edges. When he passes through an edge, letting X be his weight at that time, the car consumes X fuel.

Find the minimum amount of fuel consumed for him to reach vertex i.

Constraints

  • 1\le N\le5000
  • 1\le M\le5000
  • 1\le W _ i\le10 ^ 9\ (1\le i\le N)
  • 1\le u _ i\le v _ i\le N\ (1\le i\le M)
  • The given graph is connected.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
W _ 1 W _ 2 \ldots W _ N
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Output over N lines. On the i-th line (1\le i\le N), output the amount of fuel needed for Takahashi to reach vertex i.


Sample Input 1

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

Sample Output 1

0
3
3
7
10

The given graph is as follows:

For example, Takahashi can reach vertex 5 by visiting vertex 1 and then acting as follows:

  • He visits vertex 1. His weight increases by 3, becoming 3.
  • He consumes 3 fuel to move to vertex 3. His weight increases by 4, becoming 7.
  • He consumes 7 fuel to move to vertex 5. His weight increases by 5, becoming 12.

By acting this way, he can reach vertex 5 by consuming 10 fuel. It is impossible to reduce the fuel consumption to 9 or less, so output 10 on the 5th line.


Sample Input 2

5 4
1000000000 1000000000 1000000000 1000000000 1000000000
1 2
2 3
3 4
4 5

Sample Output 2

0
1000000000
3000000000
6000000000
10000000000

Note that the answer may exceed 2 ^ {32}.


Sample Input 3

10 20
74931 58277 33783 91022 53003 11085 65924 63548 78622 77307
1 8
3 6
5 10
4 6
1 3
1 7
2 6
7 10
8 9
3 4
4 4
4 6
6 6
5 10
1 7
4 5
1 2
3 7
2 3
5 8

Sample Output 3

0
74931
74931
183645
213410
183645
74931
74931
213410
215786