A - 321-like Checker

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

以下の条件を満たす正整数 x を 321-like Number と呼びます。

  • x の各桁を上から見ると狭義単調減少になっている。
  • すなわち、x が d 桁の整数だとすると、 1 \le i < d を満たす全ての整数 i について以下の条件を満たす。
    • ( x の上から i 桁目 ) > ( x の上から i+1 桁目 )

なお、 1 桁の正整数は必ず 321-like Number であることに注意してください。

例えば、 321,96410,1 は 321-like Number ですが、 123,2109,86411 は 321-like Number ではありません。

N が入力として与えられるので、 N が 321-like Number なら Yes 、そうでないなら No と出力してください。

制約

  • 入力は全て整数
  • 1 \le N \le 99999

入力

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

N

出力

N が 321-like Number なら Yes 、そうでないなら No と出力せよ。


入力例 1

321

出力例 1

Yes

N=321 に対して、以下が成り立ちます。

  • 上から 1 桁目の 3 は上から 2 桁目の 2 より大きい。
  • 上から 2 桁目の 2 は上から 3 桁目の 1 より大きい。

以上より、 321 は 321-like Number です。


入力例 2

123

出力例 2

No

N=123 について、例えば以下が成り立ちます。

  • 上から 1 桁目の 1 は上から 2 桁目の 2 より大きくない。

このことから、 123 は 321-like Number ではありません。


入力例 3

1

出力例 3

Yes

入力例 4

86411

出力例 4

No

Score : 100 points

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition.

  • The digits of x are strictly decreasing from top to bottom.
  • In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
    • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

You are given N as input. Print Yes if N is a 321-like Number, and No otherwise.

Constraints

  • All input values are integers.
  • 1 \le N \le 99999

Input

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

N

Output

Print Yes if N is a 321-like Number, and No otherwise.


Sample Input 1

321

Sample Output 1

Yes

For N=321, the following holds:

  • The first digit from the top, 3, is greater than the second digit from the top, 2.
  • The second digit from the top, 2, is greater than the third digit from the top, 1.

Thus, 321 is a 321-like Number.


Sample Input 2

123

Sample Output 2

No

For N=123, the following holds:

  • The first digit from the top, 1, is not greater than the second digit from the top, 2.

Thus, 123 is not a 321-like Number.


Sample Input 3

1

Sample Output 3

Yes

Sample Input 4

86411

Sample Output 4

No
B - Jogging

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君と青木君はジョギングをすることにしました。
高橋君は「A 秒間秒速 B メートルで歩き、C 秒間休む」ことを繰り返します。
青木君は「D 秒間秒速 E メートルで歩き、F 秒間休む」ことを繰り返します。
二人が同時にジョギングを始めてから X 秒後、高橋君と青木君のうちどちらが長い距離を進んでいますか?

制約

  • 1 \leq A, B, C, D, E, F, X \leq 100
  • 入力は全て整数

入力

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

A B C D E F X

出力

二人が同時にジョギングを始めてから X 秒後時点で、高橋君の方が青木君よりも長い距離を進んでいるならば Takahashi、青木君の方が高橋君よりも長い距離を進んでいるならば Aoki、二人が同じ距離を進んでいるならば Draw と出力せよ。


入力例 1

4 3 3 6 2 5 10

出力例 1

Takahashi

二人はジョギングを始めてから 10 秒間の間、以下のように行動します。

  • 高橋君は 4 秒間歩き、3 秒間休んだ後、再び 3 秒間歩く。合計 (4 + 3) \times 3 = 21 メートル歩く。
  • 青木君は 6 秒間歩き、4 秒間休む。合計 6 \times 2 = 12 メートル歩く。

高橋君の方が長い距離を進んでいるので、Takahashi と出力します。


入力例 2

3 1 4 1 5 9 2

出力例 2

Aoki

入力例 3

1 1 1 1 1 1 1

出力例 3

Draw

Score : 100 points

Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

  • 1 \leq A, B, C, D, E, F, X \leq 100
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B C D E F X

Output

When X seconds have passed since they simultaneously started to jog, if Takahashi goes ahead of Aoki, print Takahashi; if Aoki goes ahead of Takahashi, print Aoki; if they have advanced the same distance, print Draw.


Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

  • Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
  • Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.


Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw
C - Piano 3

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。 このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。 演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します(逆に、手の移動以外で疲労度が増加することはありません)。 なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

  • 1\leq N \leq 100
  • 1\leq A_i \leq 100
  • N,A_i は整数
  • S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。


入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

11

例えば以下のように演奏することができます。

  • 最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
  • 左手で鍵盤 3 を押す。
  • 右手で鍵盤 6 を押す。
  • 左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
  • 右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
  • 左手で鍵盤 9 を押す。
  • 右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。


入力例 2

3
2 L
2 L
100 L

出力例 2

98

入力例 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

出力例 3

188

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • N and A_i are integers.
  • S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.


Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

  • Initially, place the left hand on key 3 and the right hand on key 6.
  • Press key 3 with the left hand.
  • Press key 6 with the right hand.
  • Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
  • Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
  • Press key 9 with the left hand.
  • Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.


Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188
D - Second Best

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

長さ N の整数列 A=(A_1,\ldots,A_N) が与えられます。ここで A_1,A_2,\ldots,A_N は相異なります。

A の中で二番目に大きい要素は A の何番目の要素でしょうか。

制約

  • 2\leq N\leq 100
  • 1\leq A_i \leq 10^9
  • A_1,A_2,\ldots,A_N は相異なる
  • 入力される数値は全て整数

入力

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

N 
A_1 A_2 \ldots A_{N}

出力

A の中で二番目に大きい要素が A の X 番目であるとき、X を整数として出力せよ。


入力例 1

4
8 2 5 1

出力例 1

3

A の中で二番目に大きい要素は A_3 なので 3 を出力してください。


入力例 2

8
1 2 3 4 5 10 9 11

出力例 2

6

Score : 200 points

Problem Statement

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

Which element in A is the second largest?

Constraints

  • 2 \leq N \leq 100
  • 1 \leq A_i \leq 10^9
  • A_1, A_2, \ldots, A_N are all distinct.
  • 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

Print the integer X such that the X-th element in A is the second largest.


Sample Input 1

4
8 2 5 1

Sample Output 1

3

The second largest element in A is A_3, so print 3.


Sample Input 2

8
1 2 3 4 5 10 9 11

Sample Output 2

6
E - Equilateral Triangle

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

円周が L の円があり、この円周上に点 1,2,\ldots,N が配置されています。i=1,2,\ldots,N-1 に対し、点 i+1 は点 i から時計回りに円周上を d_i 進んだ位置にあります。

整数の組 (a,b,c)\ (1\leq a\lt b\lt c\leq N) であって、以下の 2 つをともに満たすものの個数を求めてください。

  • 3 点 a,b,c はすべて異なる位置にある。
  • 3 点 a,b,c を頂点とする三角形は正三角形である。

制約

  • 3\leq L,N\leq 3\times 10^5
  • 0\leq d_i\lt L
  • 入力は全て整数

入力

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

N L
d_1 d_2 \ldots d_{N-1}

出力

答えを出力せよ。


入力例 1

5 6
4 3 1 2

出力例 1

2

5 つの点の配置は以下のようになります。条件を満たすのは (a,b,c)=(1,2,4),(1,4,5) の 2 つです。


入力例 2

4 4
1 1 1

出力例 2

0

入力例 3

10 12
4 4 5 7 1 7 0 8 5

出力例 3

13

Score : 300 points

Problem Statement

There is a circle with circumference L, and points 1,2,\ldots,N are placed on this circle. For i=1,2,\ldots,N-1, point i+1 is located at a position that is d_i clockwise from point i on the circle.

Find the number of integer triples (a,b,c)\ (1\leq a\lt b\lt c\leq N) that satisfy both of the following conditions:

  • The three points a, b, and c are all at different positions.
  • The triangle with vertices at the three points a, b, and c is an equilateral triangle.

Constraints

  • 3\leq L,N\leq 3\times 10^5
  • 0\leq d_i\lt L
  • All input values are integers.

Input

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

N L
d_1 d_2 \ldots d_{N-1}

Output

Output the answer.


Sample Input 1

5 6
4 3 1 2

Sample Output 1

2

The arrangement of the five points is as follows. Two pairs satisfy the conditions: (a,b,c)=(1,2,4),(1,4,5).


Sample Input 2

4 4
1 1 1

Sample Output 2

0

Sample Input 3

10 12
4 4 5 7 1 7 0 8 5

Sample Output 3

13
F - Sugoroku Destination

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

マス 1, マス 2,\ldots, マス N の N 個のマスが 1 列に並んでいます。 マス i には整数 A _ i (i\le A_ i\le N) が書かれています。

s=1,2,\ldots,N のそれぞれについて、以下の問題を解いてください。

  • はじめ、マス s に駒を置く。「駒が置かれているマスに書かれている整数を x として、駒をマス x に移動させる」という操作を 10 ^ {100} 回行った後、駒が置かれているマスの番号を出力する。

制約

  • 1\le N\le5\times10 ^ 5
  • i\le A _ i\le N\ (1\le i\le N)
  • 入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N

出力

s=1,2,\ldots,N に対する答えを、この順に空白を区切りとして一行に出力せよ。


入力例 1

7
2 4 7 5 5 6 7

出力例 1

5 5 7 5 5 6 7

s=1 のとき、駒は以下の図のように移動します。

駒がマス 5 に置かれているとき、操作が行われても駒は移動しないため、s=1 のときの答えは 5 となります。


入力例 2

5
1 2 3 4 5

出力例 2

1 2 3 4 5

駒が一度も移動しないこともあります。


入力例 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

出力例 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

Score : 300 points

Problem Statement

There are N cells, cell 1, cell 2,\ldots, cell N, arranged in a line. Cell i has an integer A_i\ (i \le A_i \le N) written on it.

For each of s=1,2,\ldots,N, solve the following problem.

  • Initially, place a piece on cell s. After performing the operation "let x be the integer written on the cell where the piece is placed, and then move the piece to cell x" 10^{100} times, output the number of the cell where the piece is placed.

Constraints

  • 1 \le N \le 5\times10^5
  • i \le A_i \le N\ (1 \le 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 answers for s=1,2,\ldots,N in this order on a single line, separated by spaces.


Sample Input 1

7
2 4 7 5 5 6 7

Sample Output 1

5 5 7 5 5 6 7

For s=1, the piece moves as shown in the following figure.

When the piece is placed on cell 5, the operation does not move the piece, so the answer for s=1 is 5.


Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

It is possible that the piece never moves.


Sample Input 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

Sample Output 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15
G - Relative Position

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

座標平面上に 1 から N の番号がついた N 人の人がいます。
人 1 は原点にいます。

次の形式の情報が M 個与えられます。

  • 人 A_i から見て、人 B_i は、x 軸正方向に X_i、y 軸正方向に Y_i 離れた位置にいる

それぞれの人がいる座標を求めてください。一意に定まらないときはそのことを報告してください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1\leq A_i, B_i \leq N
  • A_i \neq B_i
  • -10^9 \leq X_i,Y_i \leq 10^9
  • 入力は全て整数である
  • 与えられる情報は矛盾しない

入力

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

N M
A_1 B_1 X_1 Y_1
\vdots
A_M B_M X_M Y_M

出力

N 行出力せよ。
人 i のいる座標が一意に定まらないとき、i 行目には undecidable と出力せよ。
人 i のいる座標が (s_i,t_i) と一意に定まるとき、i 行目には s_i,t_i をこの順に空白区切りで出力せよ。


入力例 1

3 2
1 2 2 1
1 3 -1 -2

出力例 1

0 0
2 1
-1 -2

3 人の位置関係は下図のようになっています。

図


入力例 2

3 2
2 1 -2 -1
2 3 -3 -3

出力例 2

0 0
2 1
-1 -2

3 人の位置関係は下図のようになっています。

図


入力例 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

出力例 3

0 0
0 0
0 0
undecidable
undecidable

同じ情報が複数回与えられたり、同じ座標に複数の人がいることもあります。

Score : 400 points

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

  • From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 0 \leq M \leq 2\times 10^5
  • 1\leq A_i, B_i \leq N
  • A_i \neq B_i
  • -10^9 \leq X_i,Y_i \leq 10^9
  • All input values are integers.
  • The given information is consistent.

Input

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

N M
A_1 B_1 X_1 Y_1
\vdots
A_M B_M X_M Y_M

Output

Print N lines.
If the coordinates of person i cannot be uniquely determined, the i-th line should contain undecidable.
If they can be uniquely determined as (s_i,t_i), the i-th line should contain s_i and t_i in this order, separated by a space.


Sample Input 1

3 2
1 2 2 1
1 3 -1 -2

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Figure


Sample Input 2

3 2
2 1 -2 -1
2 3 -3 -3

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Figure


Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

H - Subtree K-th Max

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 頂点の根付き木があります。頂点には 1 から N の番号がついており、根は頂点 1 です。
i 番目の辺は頂点 A_i と B_i を結んでいます。
頂点 i には整数 X_i が書かれています。

Q 個のクエリが与えられます。i 番目のクエリでは整数の組 (V_i,K_i) が与えられるので、次の問題に答えてください。

  • 問題:頂点 V_i の部分木に含まれる頂点に書かれた整数のうち、大きい方から K_i 番目の値を求めよ

制約

  • 2 \leq N \leq 10^5
  • 0\leq X_i\leq 10^9
  • 1\leq A_i,B_i\leq N
  • 1\leq Q \leq 10^5
  • 1\leq V_i\leq N
  • 1\leq K_i\leq 20
  • 与えられるグラフは木である
  • 頂点 V_i の部分木は頂点を K_i 個以上持つ
  • 入力に含まれる値は全て整数である

入力

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

N Q
X_1 \ldots X_N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 K_1
\vdots
V_Q K_Q

出力

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


入力例 1

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

出力例 1

4
5

この入力において与えられる木は下図のようなものです。

図

1 番目のクエリでは、頂点 1 の部分木に含まれる頂点 1,2,3,4,5 に書かれた数のうち大きい方から 2 番目である 4 を出力します。
2 番目のクエリでは、頂点 2 の部分木に含まれる頂点 2,3,5 に書かれた数のうち大きい方から 1 番目である 5 を出力します。


入力例 2

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

出力例 2

9
10

入力例 3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

出力例 3

1
10
100
1000

Score : 500 points

Problem Statement

We have a rooted tree with N vertices. The vertices are numbered 1 through N, and the root is Vertex 1.
The i-th edge connects Vertices A_i and B_i.
Vertex i has an integer X_i written on it.

You are given Q queries. For the i-th query, given a pair of integers (V_i,K_i), answer the following question.

  • Question: among the integers written on the vertices in the subtree rooted at Vertex V_i, find the K_i-th largest value.

Constraints

  • 2 \leq N \leq 10^5
  • 0\leq X_i\leq 10^9
  • 1\leq A_i,B_i\leq N
  • 1\leq Q \leq 10^5
  • 1\leq V_i\leq N
  • 1\leq K_i\leq 20
  • The given graph is a tree.
  • The subtree rooted at Vertex V_i has K_i or more vertices.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
X_1 \ldots X_N
A_1 B_1
\vdots
A_{N-1} B_{N-1}
V_1 K_1
\vdots
V_Q K_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.


Sample Input 1

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

Sample Output 1

4
5

The tree given in this input is shown below.

figure

For the 1-st query, the vertices in the subtree rooted at Vertex 1 are Vertices 1, 2, 3, 4, and 5, so print the 2-nd largest value of the numbers written on these vertices, 4.
For the 2-nd query, the vertices in the subtree rooted at Vertex 2 are Vertices 2, 3, and 5, so print the 1-st largest value of the numbers written on these vertices, 5.


Sample Input 2

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

Sample Output 2

9
10

Sample Input 3

4 4
1 10 100 1000
1 2
2 3
3 4
1 4
2 3
3 2
4 1

Sample Output 3

1
10
100
1000
I - Random Update Query

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

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

A に対して、i = 1, 2, \ldots, M の順に下記の操作を行います。

  • まず、L_i 以上 R_i 以下の整数を等確率でランダムに 1 個を選び、それを p とおく。
  • そして、A_p の値を整数 X_i に変更する。

上記の手順を行った後の最終的な A における、A_i の期待値 \text{mod } 998244353 を、 各 i = 1, 2, \ldots, N について出力してください。

期待値 \text{mod } 998244353 の定義

この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。

このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

  • 入力される値は全て整数
  • 1 \leq N, M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq L_i \leq R_i \leq N
  • 0 \leq X_i \leq 10^9

入力

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

N M
A_1 A_2 \ldots A_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_M R_M X_M

出力

各 i = 1, 2, \ldots, N に対する最終的な A_i の期待値 E_i を、 下記の形式の通りに空白区切りで出力せよ。

E_1 E_2 \ldots E_N

入力例 1

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

出力例 1

499122179 1 665496238 665496236 5

A = (3, 1, 4, 1, 5) である初期状態からはじめ、下記の通りに 2 個の操作が行われます。

  • まず、1 個目の操作で、A_1 と A_2 のどちらか一方が等確率でランダムに選ばれ、その値が 2 に変更されます。
  • その後、2 個目の操作で、A_2, A_3, A_4 のうちいずれか 1 個が等確率でランダムに選ばれ、その値が 0 に変更されます。

その結果、最終的な A の各要素の期待値は (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5) です。


入力例 2

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

出力例 2

5 6

入力例 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

出力例 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158

Score : 550 points

Problem Statement

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

We will perform the following operation on A for i = 1, 2, \ldots, M in this order.

  • First, choose an integer between L_i and R_i, inclusive, uniformly at random and denote it as p.
  • Then, change the value of A_p to the integer X_i.

For the final sequence A after the above procedure, print the expected value, modulo 998244353, of A_i for each i = 1, 2, \ldots, N.

How to print expected values modulo 998244353

It can be proved that the expected values sought in this problem are always rational. Furthermore, the constraints of this problem guarantee that if each of those expected values is expressed as an irreducible fraction \frac{y}{x}, then x is not divisible by 998244353.

Now, there is a unique integer z between 0 and 998244352, inclusive, such that xz \equiv y \pmod{998244353}. Report this z.

Constraints

  • All input values are integers.
  • 1 \leq N, M \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq L_i \leq R_i \leq N
  • 0 \leq X_i \leq 10^9

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 X_1
L_2 R_2 X_2
\vdots
L_M R_M X_M

Output

Print the expected values E_i of the final A_i for i = 1, 2, \ldots, N in the format below, separated by spaces.

E_1 E_2 \ldots E_N

Sample Input 1

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

Sample Output 1

499122179 1 665496238 665496236 5

We start from the initial state A = (3, 1, 4, 1, 5) and perform the following two operations.

  • The first operation chooses A_1 or A_2 uniformly at random, and changes its value to 2.
  • Then, the second operation chooses one of A_2, A_3, A_4 uniformly at random, and changes its value to 0.

As a result, the expected values of the elements in the final A are (E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5).


Sample Input 2

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

Sample Output 2

5 6

Sample Input 3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

Sample Output 3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158