A - Octave

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

音の高さが 1 オクターヴ上がるごとに、音の周波数は 2 倍になります。

周波数 X ヘルツの音の高さを Y オクターヴ上げると、その周波数は何ヘルツになりますか?

制約

  • 1 \leq X \leq 444
  • 1 \leq Y \leq 3
  • 入力される値はすべて整数

入力

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

X Y

出力

答えを整数として 1 行に出力せよ。単位 (ヘルツ) は省いて出力すること。


入力例 1

110 2

出力例 1

440

周波数 110 ヘルツの音の 2 オクターヴ上の音について、その周波数は 110 \times 2 \times 2 = 440 ヘルツです。


入力例 2

233 3

出力例 2

1864

周波数 233 ヘルツの音の 3 オクターヴ上の音について、その周波数は 233 \times 2 \times 2 \times 2 = 1864 ヘルツです。


入力例 3

432 1

出力例 3

864

周波数 432 ヘルツの音の 1 オクターヴ上の音について、その周波数は 432 \times 2 = 864 ヘルツです。

Score : 100 points

Problem Statement

The frequency of a sound doubles for every increase of 1 octave in pitch.

If the pitch of a sound with frequency X hertz is raised by Y octaves, what will its frequency be in hertz?

Constraints

  • 1 \leq X \leq 444
  • 1 \leq Y \leq 3
  • All input values are integers.

Input

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

X Y

Output

Output the answer as an integer in one line. Omit the unit (hertz).


Sample Input 1

110 2

Sample Output 1

440

For a sound 2 octaves above a sound with frequency 110 hertz, its frequency is 110 \times 2 \times 2 = 440 hertz.


Sample Input 2

233 3

Sample Output 2

1864

For a sound 3 octaves above a sound with frequency 233 hertz, its frequency is 233 \times 2 \times 2 \times 2 = 1864 hertz.


Sample Input 3

432 1

Sample Output 3

864

For a sound 1 octave above a sound with frequency 432 hertz, its frequency is 432 \times 2 = 864 hertz.

B - 10yen Stamp

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

サンタさんに手紙を出したい高橋くんは、 X 円切手が 1 枚だけ貼られた封筒を用意しました。
サンタさんに手紙を届けるためには、貼られている切手の総額が Y 円以上である必要があります。
高橋くんは、この封筒に 10 円切手を何枚か貼り足すことで、貼られている切手の総額を Y 円以上にしたいです。
高橋くんはこの封筒に、最小で何枚の 10 円切手を貼り足す必要がありますか?

制約

  • X,Y は整数
  • 1 \le X,Y \le 1000

入力

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

X Y

出力

答えを整数として出力せよ。


入力例 1

80 94

出力例 1

2
  • 80 円切手に 0 枚の 10 円切手を貼り足せば総額が 80 円となり、これは手紙を届けるのに必要な 94 円未満です。
  • 80 円切手に 1 枚の 10 円切手を貼り足せば総額が 90 円となり、これは手紙を届けるのに必要な 94 円未満です。
  • 80 円切手に 2 枚の 10 円切手を貼り足せば総額が 100 円となり、これは手紙を届けるのに必要な 94 円以上です。

入力例 2

1000 63

出力例 2

0

もともと貼られている切手だけで金額が十分である可能性もあります。


入力例 3

270 750

出力例 3

48

Score : 100 points

Problem Statement

Takahashi wants to send a letter to Santa Claus. He has an envelope with an X-yen (Japanese currency) stamp stuck on it.
To be delivered to Santa Claus, the envelope must have stamps in a total value of at least Y yen.
Takahashi will put some more 10-yen stamps so that the envelope will have stamps worth at least Y yen in total.
At least how many more 10-yen stamps does Takahashi need to put on the envelope?

Constraints

  • X and Y are integers.
  • 1 \le X,Y \le 1000

Input

Input is given from Standard Input in the following format:

X Y

Output

Print the answer as an integer.


Sample Input 1

80 94

Sample Output 1

2
  • After adding zero 10-yen stamps to the 80-yen stamp, the total is 80 yen, which is less than the required amount of 94 yen.
  • After adding one 10-yen stamp to the 80-yen stamp, the total is 90 yen, which is less than the required amount of 94 yen.
  • After adding two 10-yen stamps to the 80-yen stamp, the total is 100 yen, which is not less than the required amount of 94 yen.

Sample Input 2

1000 63

Sample Output 2

0

The envelope may already have a stamp with enough value.


Sample Input 3

270 750

Sample Output 3

48
C - Vacation Together

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1 から N までの番号がついた N 人の人がいます。
N 人の人の今後 D 日間の予定が与えられます。人 i の予定は長さ D の文字列 S_i で表されて、S_i の j 文字目が o ならば j 日目は暇であることを、x ならばそうでないことを意味します。

D 日間のうち全員が暇であるような 連続する 何日かを選ぶことを考えます。
選べる日数は最大で何日ですか?ただし、選べる日が存在しない場合は 0 日と答えてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N, D は整数
  • S_i は o と x からなる長さ D の文字列

入力

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

N D
S_1
S_2
\vdots
S_N

出力

選べる日数の最大値を出力せよ。選べる日が存在しない場合は 0 を出力せよ。


入力例 1

3 5
xooox
oooxx
oooxo

出力例 1

2

2 日目と 3 日目は全員が暇な日なので選ぶことができます。
この 2 日間を選ぶと、連続する日にちを選ぶ方法の中で日数を最大にすることができます。


入力例 2

3 3
oxo
oxo
oxo

出力例 2

1

選ぶ日にちは連続している必要があるのに注意してください。(1 日目と 3 日目は全員が暇な日なので選ぶことができますが、この 2 つを同時に選ぶことはできません)


入力例 3

3 3
oox
oxo
xoo

出力例 3

0

選べる日が存在しない場合は 0 を出力してください。


入力例 4

1 7
ooooooo

出力例 4

7

入力例 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

出力例 5

5

Score : 200 points

Problem Statement

There are N people numbered 1 to N.
You are given their schedule for the following D days. The schedule for person i is represented by a string S_i of length D. If the j-th character of S_i is o, person i is free on the j-th day; if it is x, they are occupied that day.

From these D days, consider choosing some consecutive days when all the people are free.
How many days can be chosen at most? If no day can be chosen, report 0.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq D \leq 100
  • N and D are integers.
  • S_i is a string of length D consisting of o and x.

Input

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

N D
S_1
S_2
\vdots
S_N

Output

Print the maximum number of days that can be chosen, or 0 if no day can be chosen.


Sample Input 1

3 5
xooox
oooxx
oooxo

Sample Output 1

2

All the people are free on the second and third days, so we can choose them.
Choosing these two days will maximize the number of days among all possible choices.


Sample Input 2

3 3
oxo
oxo
oxo

Sample Output 2

1

Note that the chosen days must be consecutive. (All the people are free on the first and third days, so we can choose either of them, but not both.)


Sample Input 3

3 3
oox
oxo
xoo

Sample Output 3

0

Print 0 if no day can be chosen.


Sample Input 4

1 7
ooooooo

Sample Output 4

7

Sample Input 5

5 15
oxooooooooooooo
oxooxooooooooox
oxoooooooooooox
oxxxooooooxooox
oxooooooooxooox

Sample Output 5

5
D - Integer Division Returns

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

-10^{18} 以上 10^{18} 以下の整数 X が与えられるので、\left\lceil \dfrac{X}{10} \right\rceil を出力してください。
ここで、\left\lceil a \right\rceil は a 以上の整数のうち最小のものを意味します。

制約

  • -10^{18} \leq X \leq 10^{18}
  • X は整数

入力

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

X

出力

\left\lceil \dfrac{X}{10} \right\rceil を整数として出力せよ。


入力例 1

27

出力例 1

3

\frac{27}{10} = 2.7 以上の整数は 3, 4, 5, \dots です。この中で一番小さい整数は 3 なので、\left \lceil \frac{27}{10} \right \rceil = 3 となります。


入力例 2

-13

出力例 2

-1

\frac{-13}{10} = -1.3 以上の整数は、全ての正整数および 0, -1 です。この中で一番小さい整数は -1 なので、\left \lceil \frac{-13}{10} \right \rceil = -1 となります。


入力例 3

40

出力例 3

4

\frac{40}{10} = 4 以上の整数で一番小さい整数は 4 自身です。


入力例 4

-20

出力例 4

-2

入力例 5

123456789123456789

出力例 5

12345678912345679

Score: 200 points

Problem Statement

Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.

Constraints

  • -10^{18} \leq X \leq 10^{18}
  • X is an integer.

Input

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

X

Output

Print \left\lceil \dfrac{X}{10} \right\rceil as an integer.


Sample Input 1

27

Sample Output 1

3

The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.


Sample Input 2

-13

Sample Output 2

-1

The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.


Sample Input 3

40

Sample Output 3

4

The smallest integer not less than \frac{40}{10} = 4 is 4 itself.


Sample Input 4

-20

Sample Output 4

-2

Sample Input 5

123456789123456789

Sample Output 5

12345678912345679
E - Lock All Doors

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N + 1 個の部屋が一列に並んでおり、順に 0, 1, \ldots, N の番号が付けられています。

部屋の間には N 個のドアがあり、1, 2, \ldots, N の番号が付けられています。ドア i は部屋 i - 1 と部屋 i の間にあります。

各ドアについて鍵の状態を表す値 L_i が与えられ、L_i = 0 のときドア i の鍵は開いており、L_i = 1 のときドア i の鍵は閉まっています。

高橋君ははじめ部屋 R におり、ドア i の鍵が開いているときに限り、部屋 i - 1 と部屋 i の間を移動することができます。また、高橋君は部屋 i - 1 または部屋 i にいるときに限り、ドア i の鍵に対して 開閉操作 を行うことができます。ドア i の鍵に対して開閉操作を行ったとき、その鍵が開いているときは閉まり、閉まっているときは開きます。

すべてのドアの鍵が閉まった状態にするために行う鍵の開閉操作の回数として考えられる最小値を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq R \leq N
  • L_i \in \lbrace 0, 1 \rbrace
  • 入力される値はすべて整数

入力

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

N R
L_1 L_2 \ldots L_N

出力

答えを出力せよ。


入力例 1

6 3
1 0 0 1 0 0

出力例 1

6

高橋君は以下のように行動することで 6 回の開閉操作ですべてのドアの鍵が閉まった状態にすることができます。

  • 部屋 2 に移動する。
  • ドア 2 に対して開閉操作を行い、ドア 2 の鍵を閉める。
  • 部屋 3 に移動する。
  • ドア 4 に対して開閉操作を行い、ドア 4 の鍵を開ける。
  • ドア 3 に対して開閉操作を行い、ドア 3 の鍵を閉める。
  • 部屋 4 に移動する。
  • ドア 4 に対して開閉操作を行い、ドア 4 の鍵を閉める。
  • 部屋 5 に移動する。
  • ドア 5 に対して開閉操作を行い、ドア 5 の鍵を閉める。
  • ドア 6 に対して開閉操作を行い、ドア 6 の鍵を閉める。

入力例 2

2 1
0 0

出力例 2

2

入力例 3

8 2
0 1 0 0 1 0 1 1

出力例 3

8

Score : 300 points

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.

Find the minimum number of switching operations needed to make all doors locked.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 0 \leq R \leq N
  • L_i \in \lbrace 0, 1 \rbrace
  • All input values are integers.

Input

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

N R
L_1 L_2 \ldots L_N

Output

Output the answer.


Sample Input 1

6 3
1 0 0 1 0 0

Sample Output 1

6

Takahashi can make all doors locked with six switching operations by acting as follows:

  • Move to room 2.
  • Perform a switching operation on door 2 to lock door 2.
  • Move to room 3.
  • Perform a switching operation on door 4 to unlock door 4.
  • Perform a switching operation on door 3 to lock door 3.
  • Move to room 4.
  • Perform a switching operation on door 4 to lock door 4.
  • Move to room 5.
  • Perform a switching operation on door 5 to lock door 5.
  • Perform a switching operation on door 6 to lock door 6.

Sample Input 2

2 1
0 0

Sample Output 2

2

Sample Input 3

8 2
0 1 0 0 1 0 1 1

Sample Output 3

8
F - Cross

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

縦 H マス横 W マスのグリッドがあります。グリッドの上から i 行目、左から j 列目のマスを (i, j) と呼びます。
グリッドの各マスには # と . のいずれかの文字が書かれています。(i, j) に書かれている文字を C[i][j] とします。また、整数 i, j が 1 \leq i \leq H と 1 \leq j \leq W の少なくとも一方を満たさない場合、 C[i][j] を . と定義します。

正整数 a, b, n が以下の条件を全て満たす時、(a,b) および (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n) の 4n + 1 マスを (a,b) を中心とするサイズ n のバツ印 と呼びます。

  • C[a][b] は # である。
  • 1 \leq d \leq n を満たす整数 d について、 C[a+d][b+d],C[a+d][b-d],C[a-d][b+d],C[a-d][b-d] はいずれも # である。
  • C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1],C[a-n-1][b-n-1] のうち少なくとも 1 つは . である。

例えば次の図で示された例では、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印がグリッド上にあります。

image

グリッドにはいくつかのバツ印があります。バツ印を構成するマス以外に # は書かれていません。
また、異なるバツ印を構成するマス同士は頂点を共有しません。以下の 2 つのグリッドは異なるバツ印を構成するマス同士が頂点を共有している例で、このようなグリッドの状態は入力として与えられません。 例えば左のグリッドでは (3, 3) と (4, 4) が頂点を共有しているのが条件に反しています。

image2

N = \min(H, W) とします。また、サイズ n のバツ印の個数を S_n とします。S_1, S_2, \dots, S_N を計算してください。

制約

  • 3 \leq H, W \leq 100
  • C[i][j] は # または .
  • 異なるバツ印を構成するマス同士は頂点を共有しない
  • H, W は整数

入力

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

出力

S_1, S_2, \dots, S_N を空白区切りで出力せよ。


入力例 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

出力例 1

1 1 0 0 0

問題文に書かれた説明の通り、(2, 2) を中心とするサイズ 1 のバツ印と (3, 7) を中心とするサイズ 2 のバツ印が書かれています。


入力例 2

3 3
...
...
...

出力例 2

0 0 0

バツ印が 1 個も書かれていない場合もあります。


入力例 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

出力例 3

3 0 0

入力例 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

出力例 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Score : 300 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

  • C[a][b] is #.
  • C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
  • At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

image

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

image2

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

  • 3 \leq H, W \leq 100
  • C[i][j] is # or ..
  • No two different squares that comprise two different crosses share a corner.
  • H and W are integers.

Input

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

H W
C[1][1]C[1][2]\dots C[1][W]
C[2][1]C[2][2]\dots C[2][W]
\vdots
C[H][1]C[H][2]\dots C[H][W]

Output

Print S_1, S_2, \dots, and S_N, separated by spaces.


Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).


Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.


Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0
G - Reindeer and Sleigh

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 台のソリがあり、各ソリには 1,2,\ldots, N の番号がつけられています。

ソリ i を引くために必要なトナカイは R_i 匹です。

また、各トナカイが引けるソリは高々 1 台です。より厳密には、m 台のソリ i_1, i_2, \ldots, i_m を引くために必要なトナカイは \sum_{k=1}^{m} R_{i_k} 匹です。

以下の形式のクエリが Q 個与えられるので、答えを求めてください。

  • 整数 X が与えられる。トナカイが X 匹いるときに最大で何台のソリを引けるか求めよ。

制約

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq R_i \leq 10^9
  • 1 \leq X \leq 2 \times 10^{14}
  • 入力される数値はすべて整数

入力

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

N Q
R_1 R_2 \ldots R_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

各クエリは次の形式で与えられる。

X

出力

Q 行出力せよ。

i 行目には i 個目のクエリに対する答えを出力せよ。


入力例 1

4 3
5 3 11 8
16
7
1000

出力例 1

3
1
4

トナカイが 16 匹いるとき、ソリ 1,2,4 を引くことができます。

16 匹のトナカイで 4 台のソリを引くことはできないので、クエリ 1 の答えは 3 となります。


入力例 2

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

出力例 2

1
1
2
2
2
3

入力例 3

2 2
1000000000 1000000000
200000000000000
1

出力例 3

2
0

Score : 400 points

Problem Statement

There are N sleighs numbered 1,2,\ldots, N.

R_i reindeer are required to pull sleigh i.

Additionally, each reindeer can pull at most one sleigh. More precisely, \sum_{k=1}^{m} R_{i_k} reindeer are required to pull m sleighs i_1, i_2, \ldots, i_m.

Find the answer to Q queries of the following form:

  • You are given an integer X. Determine the maximum number of sleighs that can be pulled when there are X reindeer.

Constraints

  • 1 \leq N, Q \leq 2 \times 10^5
  • 1 \leq R_i \leq 10^9
  • 1 \leq X \leq 2 \times 10^{14}
  • All input values are integers.

Input

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

N Q
R_1 R_2 \ldots R_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Each query is given in the following format:

X

Output

Print Q lines.

The i-th line should contain the answer to the i-th query.


Sample Input 1

4 3
5 3 11 8
16
7
1000

Sample Output 1

3
1
4

When there are 16 reindeer, sleighs 1,2,4 can be pulled.

It is impossible to pull four sleighs with 16 reindeer, so the answer to query 1 is 3.


Sample Input 2

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

Sample Output 2

1
1
2
2
2
3

Sample Input 3

2 2
1000000000 1000000000
200000000000000
1

Sample Output 3

2
0
H - Chords

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

円周上に 2N 個の点が等間隔に並んでおり、ある点から始めて時計回りに 1 から 2N までの番号が付けられています。

円周上にはさらに N 個の弦があり、i 個目の弦は点 A_i と点 B_i を結んでいます。 ここで、A_1,\dots,A_N,B_1,\dots,B_N は全て相異なることが保証されます。

弦どうしの交点が存在するかどうか判定してください。

制約

  • 2\leq N \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 2N
  • A_1,\dots,A_N,B_1,\dots,B_N は全て相異なる
  • 入力は全て整数

入力

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

出力

弦どうしの交点が存在するならば Yes を、存在しないならば No を出力せよ。


入力例 1

3
1 3
4 2
5 6

出力例 1

Yes

図のように、弦 1(点 1 と点 3 を結ぶ線分)と弦 2(点 4 と点 2 を結ぶ線分)が交点を持つので、Yes を出力します。


入力例 2

3
6 1
4 3
2 5

出力例 2

No

図のように、弦どうしの交点は存在しないので、No を出力します。


入力例 3

4
2 4
3 7
8 6
5 1

出力例 3

Yes

Score: 500 points

Problem Statement

There are 2N points placed at equal intervals on a circle, numbered 1 to 2N in a clockwise direction starting from a certain point.

There are also N chords on the circle, with the i-th chord connecting points A_i and B_i. It is guaranteed that all the values A_1,\dots,A_N,B_1,\dots,B_N are distinct.

Determine whether there is an intersection between the chords.

Constraints

  • 2\leq N \leq 2\times 10^5
  • 1\leq A_i,B_i \leq 2N
  • A_1,\dots,A_N,B_1,\dots,B_N are all distinct
  • All input values are integers

Input

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

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

If there is an intersection between the chords, print Yes; otherwise, print No.


Sample Input 1

3
1 3
4 2
5 6

Sample Output 1

Yes

As shown in the figure, chord 1 (the line segment connecting points 1 and 3) and chord 2 (the line segment connecting points 4 and 2) intersect, so print Yes.


Sample Input 2

3
6 1
4 3
2 5

Sample Output 2

No

As shown in the figure, there is no intersection between the chords, so print No.


Sample Input 3

4
2 4
3 7
8 6
5 1

Sample Output 3

Yes
I - Random Gathering

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 個の皿が、皿 1, 皿 2,\ldots, 皿 N の順に左から並んでいます。 はじめ、皿 i\ (1\le i\le N) には A _ i 個の石が入っています。

この皿たちに対して M 回の操作を行います。 i 回目 (1\le i\le M) の操作では、2 つの整数 L _ i,R _ i が与えられ、次の操作を順に行います。

  • 皿 L _ i, 皿 L _ i+1,\ldots, 皿 R _ i の R _ i-L _ i+1 個の皿に入っている石をすべて皿の上から取り除く。
  • L _ i 以上 R _ i 以下の整数を一様ランダムに 1 つ取り、それを x とする。
  • 取り除いた石をすべて皿 x に乗せる。

i=1,2,\ldots,N について、M 回の操作がすべて終了したときに皿 i に置かれている石の個数の期待値を{}\bmod998244353 で求めてください。

期待値を{}\bmod{998244353} で求めるとは

求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not\equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 を満たす整数 R が一意に定まります。期待値を{}\bmod{998244353} で求めるとは、この R を求めることを指します。

制約

  • 1\le N\le2\times10 ^ 5
  • 1\le M\le2\times10 ^ 5
  • 0\le A _ i\lt998244353\ (1\le i\le N)
  • 1\le L _ i\le R _ i\le N\ (1\le i\le M)
  • 入力はすべて整数

入力

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

N M
A _ 1 A _ 2 \ldots A _ N
L _ 1 R _ 1
L _ 2 R _ 2
\vdots
L _ M R _ M

出力

空白を区切りとして N 個の整数を 1 行に出力せよ。 i 番目 (1\leq i\leq N) には M 回の操作がすべて終了したときに皿 i に置かれている石の個数の期待値を{}\bmod998244353 で求め、出力せよ。


入力例 1

7 4
30 10 40 10 50 90 20
4 6
5 7
1 6
3 7

出力例 1

35 35 36 36 36 36 36 

例えば、操作は次のように進みます。

  • 1 回目の操作で 4 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 30 個 ,10 個 ,40 個 ,150 個 ,0 個 ,0 個 ,20 個となる。
  • 2 回目の操作で 6 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 30 個 ,10 個 ,40 個 ,150 個 ,0 個 ,20 個 ,0 個となる。
  • 3 回目の操作で 2 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 0 個 ,250 個 ,0 個 ,0 個 ,0 個 ,0 個 ,0 個となる。
  • 4 回目の操作で 3 が選ばれる。皿 1, 皿 2,\ldots, 皿 7 に置かれている石の個数はそれぞれ 0 個 ,250 個 ,0 個 ,0 個 ,0 個 ,0 個 ,0 個となる。

すべての操作が終了したときに皿 1, 皿 2 に置かれている石の個数の期待値は 35 、皿 3, 皿 4, 皿 5, 皿 6, 皿 7に置かれている石の個数の期待値は 36 なので、35 35 36 36 36 36 36 を出力してください。


入力例 2

2 1
0 1
1 2

出力例 2

499122177 499122177 

期待値を{}\bmod998244353 で求めることに注意してください。

すべての操作が終了したとき、どちらの皿についても \dfrac12 の確率で石が 1 つ置かれており、\dfrac12 の確率で石が 1 つも置かれていません。 よって、置かれている石の個数の期待値は \dfrac12 です。 499122177\times2\equiv1\pmod{998244353} なので、499122177 499122177 を出力してください。


入力例 3

15 10
61477244 450343304 812961384 836482955 280670539 405068748 318805088 304825858 518212597 316347783 589272551 505875419 944071276 364842194 5376942
2 11
5 9
8 15
6 7
6 8
1 2
1 10
4 9
12 15
6 11

出力例 3

449356308 449356308 449356308 449356308 449356308 648148154 648148154 648148154 648148154 648148154 648148154 643863031 643863031 643863031 643863031 

Score : 500 points

Problem Statement

There are N plates arranged from left to right as plate 1, plate 2,\ldots, plate N. Initially, plate i\ (1\le i\le N) contains A _ i stones.

You will perform M operations on these plates. In the i-th operation (1\le i\le M), two integers L _ i and R _ i are given, and the following operations are performed in order:

  • Remove all stones from the R _ i-L _ i+1 plates: plate L _ i, plate L _ i+1,\ldots, plate R _ i.
  • Uniformly randomly choose an integer between L _ i and R _ i, inclusive, and let it be x.
  • Place all the removed stones on plate x.

For i=1,2,\ldots,N, find the expected number, modulo 998244353, of stones placed on plate i when all M operations are completed.

Finding expected value modulo 998244353

It can be proved that the expected value you seek is always a rational number. Also, under the constraints of this problem, when that value is expressed as an irreducible fraction \frac{P}{Q}, it can be proved that Q \not\equiv 0 \pmod{998244353}. Therefore, there is a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353. Finding the expected value modulo 998244353 means finding this R.

Constraints

  • 1\le N\le2\times10 ^ 5
  • 1\le M\le2\times10 ^ 5
  • 0\le A _ i\lt998244353\ (1\le i\le N)
  • 1\le L _ i\le R _ i\le N\ (1\le i\le M)
  • All input values are integers.

Input

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

N M
A _ 1 A _ 2 \ldots A _ N
L _ 1 R _ 1
L _ 2 R _ 2
\vdots
L _ M R _ M

Output

Output N integers separated by spaces on a single line. For the i-th (1\leq i\leq N), find the expected number, modulo 998244353, of stones placed on plate i when all M operations are completed, and output it.


Sample Input 1

7 4
30 10 40 10 50 90 20
4 6
5 7
1 6
3 7

Sample Output 1

35 35 36 36 36 36 36 

For example, the operations proceed as follows:

  • In the first operation, 4 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 0, 20, respectively.
  • In the second operation, 6 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 30, 10, 40, 150, 0, 20, 0, respectively.
  • In the third operation, 2 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.
  • In the fourth operation, 3 is chosen. The number of stones on plates 1, 2,\ldots, 7 becomes 0, 250, 0, 0, 0, 0, 0, respectively.

When all operations are completed, the expected number of stones on plates 1, 2 is 35, and the expected number of stones on plates 3, 4, 5, 6, 7 is 36, so output 35 35 36 36 36 36 36.


Sample Input 2

2 1
0 1
1 2

Sample Output 2

499122177 499122177 

Note that you need to find the expected value modulo 998244353.

When all operations are completed, for both plates, there is a \dfrac12 probability that one stone is placed, and a \dfrac12 probability that no stone is placed. Therefore, the expected number of stones placed is \dfrac12. We have 499122177\times2\equiv1\pmod{998244353}, so output 499122177 499122177.


Sample Input 3

15 10
61477244 450343304 812961384 836482955 280670539 405068748 318805088 304825858 518212597 316347783 589272551 505875419 944071276 364842194 5376942
2 11
5 9
8 15
6 7
6 8
1 2
1 10
4 9
12 15
6 11

Sample Output 3

449356308 449356308 449356308 449356308 449356308 648148154 648148154 648148154 648148154 648148154 648148154 643863031 643863031 643863031 643863031