A - swallow

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

日本では、ツバメは 4 月から 9 月まで観察できます。

1 以上 12 以下の整数 M が与えられるので、 M 月にツバメを観察できるか答えてください。

制約

  • M1 以上 12 以下の整数

入力

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

M

出力

M 月にツバメを観察できる場合 Yes を、観察できない場合 No を出力せよ。


入力例 1

4

出力例 1

Yes

4 月はツバメを観察できます。


入力例 2

12

出力例 2

No

12 月は 4 月から 9 月に含まれないので、ツバメを観察できません。


入力例 3

9

出力例 3

Yes

Problem Statement

In Japan, swallows can be observed from April through September.

Given an integer M between 1 and 12, determine if swallows can be observed in month M (where January is month 1).

Constraints

  • M is an integer between 1 and 12, inclusive.

Input

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

M

Output

Print Yes if swallows can be observed in month M, and No otherwise.


Sample Input 1

4

Sample Output 1

Yes

Swallows can be observed in April (month 4).


Sample Input 2

12

Sample Output 2

No

Swallows cannot be observed in December (month 12), which is not in the season from April through September.


Sample Input 3

9

Sample Output 3

Yes
B - Slot

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

3 つの正整数 A,B,C が与えられます。

A,B,C が全て等しいなら Yes を、そうでないならば No を出力してください。

制約

  • 1\leq A ,B,C\leq 9
  • A,B,C は整数

入力

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

A B C

出力

A,B,C が全て等しいなら Yes を、そうでないならば No を出力せよ。


入力例 1

3 3 3

出力例 1

Yes

A=B=C=3 であるため、A,B,C はすべて等しいです。 よって、Yes を出力します。


入力例 2

7 7 8

出力例 2

No

A=7, C=8 であるため、AC は等しくありません。 よって、No を出力します。


入力例 3

1 2 3

出力例 3

No

Problem Statement

You are given three positive integers A, B, and C.

Print Yes if A, B, and C are all equal, and No otherwise.

Constraints

  • 1\leq A ,B,C\leq 9
  • A, B, and C are integers.

Input

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

A B C

Output

Print Yes if A, B, and C are all equal, and No otherwise.


Sample Input 1

3 3 3

Sample Output 1

Yes

A=B=C=3, so A, B, and C are all equal. Thus, Yes should be printed.


Sample Input 2

7 7 8

Sample Output 2

No

A=7 and C=8, so A and C are not equal. Thus, No should be printed.


Sample Input 3

1 2 3

Sample Output 3

No
C - Programming Contest

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

あなたは競技プログラミングのコンテストを何回か開こうとしています。
コンテストを 1 回開くためには、難易度1 から 8 の問題を各 1 問、計 8 問用意する必要があります。

あなたは問題を N 問用意しており、i 番目の問題の難易度は A_i です。
同じ問題を複数のコンテストで使うことはできないとき、用意した N 問を使ってコンテストを最大何回開けますか?

制約

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 8
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。


入力例 1

10
1 2 3 4 5 5 6 7 8 8

出力例 1

1

例えば 1,2,3,4,5,7,8,9 番目の問題を使うことでコンテストを 1 回行うことができます。


入力例 2

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

出力例 2

2

入力例 3

1
1

出力例 3

0

Problem Statement

You are going to hold a competitive programming contest several times.
Holding a contest requires preparing a total of eight problems: one problem of each difficulty from 1 through 8.

You have prepared N problems, the i-th of which is of difficulty A_i.
If you cannot use the same problem for multiple contests, at most how many contests can you hold with the N problems prepared?

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i \leq 8
  • All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Print the answer.


Sample Input 1

10
1 2 3 4 5 5 6 7 8 8

Sample Output 1

1

For example, you can hold one contest with the 1-st, 2-nd, 3-rd, 4-th, 5-th, 7-th, 8-th, and 9-th problems.


Sample Input 2

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

Sample Output 2

2

Sample Input 3

1
1

Sample Output 3

0
D - Relative Score

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

あなたは、プログラミングコンテストを主催しました。 コンテストには N 人が参加し、i (1\leq i\leq N) 番目の参加者は A _ i 点を得ました。

あなたは、全員のスコアを 0 以上 10^9 以下の整数にするために、i=1,2,\ldots,N について次の式で i 番目の参加者の相対スコアを計算することにしました。

  • \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right)

ただし、\max _ iA _ iA _ i のうち最大のものを、\operatorname{round}(x)x を四捨五入して整数にしたものを表します。 厳密には、\max _ iA _ iA _ i のうちすべての整数 j (1\leq j\leq N) について A _ j\leq A _ i を満たすようなものを表し、\operatorname{round}(x)n-\dfrac12\leq x\lt n+\dfrac12 を満たす唯一の整数 n を表します。

i=1,2,\ldots,N について、i 番目の参加者の相対スコアを計算してください。

制約

  • 1\leq N\leq10^5
  • 1\leq A _ i\leq10^9 (1\leq i\leq N)
  • 入力はすべて整数

入力

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

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

出力

i 番目 (1\leq i\leq N) の参加者の相対スコアを、i の昇順に空白区切りで 1 行に出力せよ。


入力例 1

3
200 600 300

出力例 1

333333333 1000000000 500000000

それぞれの参加者の相対スコアは、以下のように計算されます。

A _ 1\leq A _ 2,A _ 2\leq A _ 2,A _ 3\leq A _ 2 が成り立つので、 \max _ iA _ i=A _ 2=600 です。

  • 1 番目の参加者の得点は A _ 1=200 点です。10^9\times\dfrac{200}{600}=\dfrac{10^9}3 で、333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12 なので、1 番目の参加者の相対スコアは 333333333 です。
  • 2 番目の参加者の得点は A _ 2=600 点です。10^9\times\dfrac{600}{600}=10^9 で、1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12 なので、2 番目の参加者の相対スコアは 1000000000 です。
  • 3 番目の参加者の得点は A _ 3=300 点です。10^9\times\dfrac{300}{600}=5\times10^8 で、500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12 なので、3 番目の参加者の相対スコアは 500000000 です。

入力例 2

2
1 999999999

出力例 2

1 1000000000

入力例 3

10
55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617

出力例 3

77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000

Problem Statement

You held a programming contest. There were N participants, and the i-th (1\leq i\leq N) of them scored A _ i points.

In order to make their scores integers between 0 and 10^9 (inclusive), you are going to determine the relative score of the i-th participant for each i=1,2,\ldots,N by the following expression:

  • \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right).

Here, \max _ iA _ i denotes the maximum value among A _ i, and \operatorname{round}(x) denotes x rounded off to an integer. Formally, \max _ iA _ i is A _ i that satisfies A _ j\leq A _ i for all j (1\leq j\leq N), and \operatorname{round}(x) is the unique integer n satisfying n-\dfrac12\leq x\lt n+\dfrac12.

Find the relative score of the i-th participant for i=1,2,\ldots,N.

Constraints

  • 1\leq N\leq10^5
  • 1\leq A _ i\leq10^9 (1\leq i\leq 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

Print the relative scores of the i-th participants (1\leq i\leq N) in ascending order of i, separated by spaces in a single line.


Sample Input 1

3
200 600 300

Sample Output 1

333333333 1000000000 500000000

The relative score of each participant is computed as follows.

\max _ iA _ i=A _ 2=600, since A _ 1\leq A _ 2,A _ 2\leq A _ 2, and A _ 3\leq A _ 2.

  • The 1-st participant scored A _ 1=200 points. 10^9\times\dfrac{200}{600}=\dfrac{10^9}3 and 333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12, so the relative score of the 1-st participant is 333333333.
  • The 2-nd participant scored A _ 2=600 points. 10^9\times\dfrac{600}{600}=10^9 and 1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12, so the relative score of the 2-nd participant is 1000000000.
  • The 3-rd participant scored A _ 3=300 points. 10^9\times\dfrac{300}{600}=5\times10^8 and 500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12, so the relative score of the 3-rd participant is 500000000.

Sample Input 2

2
1 999999999

Sample Output 2

1 1000000000

Sample Input 3

10
55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617

Sample Output 3

77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000
E - <=10^n

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

正整数 X が与えられます。

X\leq 10^n をみたす最小の非負整数 n を求めてください。

制約

  • 1\leq X\leq 10^{100000}
  • X は整数

入力

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

X

出力

X\leq 10^n をみたす最小の非負整数 n を出力せよ。


入力例 1

23

出力例 1

2

23>1=10^023>10=10^123\leq 100=10^2 であるため、2 を出力します。


入力例 2

1

出力例 2

0

1\leq 10^0 であるため、0 を出力します。


入力例 3

12345678901234567890

出力例 3

20

Problem Statement

Given a positive integer X, find the minimum non-negative integer n such that X\leq 10^n.

Constraints

  • 1\leq X\leq 10^{100000}
  • X is an integer.

Input

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

X

Output

Print the minimum non-negative integer n such that X\leq 10^n.


Sample Input 1

23

Sample Output 1

2

23>1=10^0, 23>10=10^1, and 23\leq 100=10^2, so 2 should be printed.


Sample Input 2

1

Sample Output 2

0

1\leq 10^0, so 0 should be printed.


Sample Input 3

12345678901234567890

Sample Output 3

20
F - Evaluate Formula

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

数字と *(乗算記号)からなる文字列 S が与えられます。 S を数式として見た上で、その式を評価した値を 998244353 で割った余りを求めてください。 例えば、S= 5*32*2 のとき、式を評価した値は 5 \times 32 \times 2 = 320 です。

なお、S は正しい数式であることが保証されます。すなわち、以下がすべて保証されます。

  • S の中に * が連続して現れることはない
  • S の先頭の文字は数字である
  • S の末尾の文字は数字である

制約

  • S は数字と * からなる文字列
  • S は正しい数式
  • S の長さは 1 以上 10^6 以下

入力

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

S

出力

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


入力例 1

5*32*2

出力例 1

320

問題文中で説明した例の通りです。


入力例 2

998244354

出力例 2

1

S* を含まないこともあります。

式を評価した値を 998244353 で割った余りを求めることに注意してください。


入力例 3

05*000

出力例 3

0

S の中に現れる数が先頭に余分な 0 を含むこともあります。

Problem Statement

Given a string S consisting of digits and * (multiplication sign), interpret S as a mathematical expression, evaluate it, and report the result modulo 998244353. For example, S= 5*32*2 evaluates to 5 \times 32 \times 2 = 320.

Here, it is guaranteed that S is a valid expression. In other words, it is guaranteed that:

  • multiple * do not occur contiguously in S;
  • S starts with a digit;
  • S ends with a digit.

Constraints

  • S is a string consisting of digits and *.
  • S is a valid expression.
  • S has a length between 1 and 10^6, inclusive.

Input

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

S

Output

Print the answer as an integer.


Sample Input 1

5*32*2

Sample Output 1

320

This example is already described in the problem statement.


Sample Input 2

998244354

Sample Output 2

1

S may not contain *.

Be sure to report the evaluated value modulo 998244353.


Sample Input 3

05*000

Sample Output 3

0

Numbers in S may have leading zeros.

G - N triangles

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

3N 本の棒があります。i 番目の棒の長さは A_i です。

この棒を 31 組に分け、N 個の三角形を作る方法は何通りありますか?

ただし、N 個の三角形を作る 2 つの方法は、一方では三角形をなしているある 3 本の組が、他方では三角形をなしていないとき、かつそのときに限り異なるとみなします。
詳細は入力例 1 の説明を参照してください。

制約

  • 1 \leq N \leq 4
  • 1 \leq A_i \leq 100
  • 入力は全て整数である

入力

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

N
A_1 \ldots A_{3N}

出力

答えを出力せよ。


入力例 1

2
3 3 3 4 4 6

出力例 1

7

i,j,k 番目の 3 本の棒を使って作ることができる三角形を (i,j,k) と表すことにします。

以下の 7 通りの方法があります。同じ長さの棒も区別することに注意してください。

  • (1,2,3),(4,5,6)
  • (1,2,4),(3,5,6)
  • (1,2,5),(3,4,6)
  • (1,3,4),(2,5,6)
  • (1,3,5),(2,4,6)
  • (2,3,4),(1,5,6)
  • (2,3,5),(1,4,6)

なお、例えば、1,2,6 番目の棒を組み合わせることでは三角形を作ることができません。


入力例 2

4
100 100 100 100 100 100 100 100 100 100 100 100

出力例 2

15400

Problem Statement

There are 3N sticks. The length of the i-th stick is A_i.

How many ways are there to group them into triplets so that they form N triangles?

Here, two ways to form N triangles are distinguished if and only if there is a triplet forming a triangle in one way that does not form a triangle in the other way.
For more details, see the description of Sample Input 1.

Constraints

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

Input

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

N
A_1 \ldots A_{3N}

Output

Print the answer.


Sample Input 1

2
3 3 3 4 4 6

Sample Output 1

7

We denote by (i,j,k) the triangle formed by the following three sticks: i-th, j-th, and k-th.

There are seven ways as follows. Note that equal-length sticks are distinguished.

  • (1,2,3),(4,5,6)
  • (1,2,4),(3,5,6)
  • (1,2,5),(3,4,6)
  • (1,3,4),(2,5,6)
  • (1,3,5),(2,4,6)
  • (2,3,4),(1,5,6)
  • (2,3,5),(1,4,6)

On the other hand, for instance, the 1-st, 2-nd, and 6-th sticks do not form a triangle.


Sample Input 2

4
100 100 100 100 100 100 100 100 100 100 100 100

Sample Output 2

15400
H - Vacation

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

あなたは明日からの N 日間の休暇の予定を立てようとしています。

それぞれの日には「遊ぶ」「宿題をする」のどちらかを行います。
N 日間のうち M 日以上宿題をする日がある必要があります。
2 日以上連続で宿題をすることはしません。
i 日目に遊ぶと、楽しさA_i 得ます。宿題をするとその日の楽しさは 0 です。

N 日間で得られる楽しさの合計の最大値を求めてください。

制約

  • 1 \leq N \leq 3000
  • 0 \leq M \leq \frac{N+1}{2}
  • 1 \leq A_i \leq 10^9
  • 入力は全て整数である

入力

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

N M
A_1 \ldots A_N

出力

答えを出力せよ。


入力例 1

5 2
3 2 4 1 5

出力例 1

12

1,3,5 日目に遊び、2,4 日目に宿題をすることで、楽しさ 12 を得ます。


入力例 2

5 2
3 5 4 1 2

出力例 2

11

2,3,5 日目に遊び、1,4 日目に宿題をすることで、楽しさ 11 を得ます。
2 日以上連続して宿題をすることはできないことに注意してください。


入力例 3

10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

出力例 3

10000000000

Problem Statement

You are making plans for an upcoming N-day vacation.

On each day, you will either "play" or "study."
Among the N days, you need to study on at least M days.
You will not study on two or more days in a row.
If you play on day i, you get a joy of A_i; if you study, the joy is 0 on that day.

Find the maximum possible total joy of the N days.

Constraints

  • 1 \leq N \leq 3000
  • 0 \leq M \leq \frac{N+1}{2}
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

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

N M
A_1 \ldots A_N

Output

Print the answer.


Sample Input 1

5 2
3 2 4 1 5

Sample Output 1

12

You can play on days 1, 3, and 5, and study on days 2 and 4 to get a joy of 12.


Sample Input 2

5 2
3 5 4 1 2

Sample Output 2

11

You can play on days 2, 3, and 5, and study on days 1 and 4 to get a joy of 11.
Note that you cannot study on two or more days in a row.


Sample Input 3

10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

10000000000
I - Candies

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

N 人のこどもが一列に並んでいます。最初、前から i 番目のこどもは A_i 個のアメを持っています。

あなたは以下の操作を M 回続けて行います。

  • 持っているアメの個数が最も少ないこども(複数いるならそのうち最も前にいるこども) 1 人に、アメを K 個与える

M 回の操作が終了したときに、それぞれのこどもが持っているアメの個数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^{12}
  • 1 \leq K \leq 10^5
  • 0 \leq A_i \leq 10^{12}
  • 入力は全て整数である

入力

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

N M K
A_1 A_2 \ldots A_N

出力

M 回の操作が終了したときに、前から i 番目のこどもが持っているアメの個数を B_i として、B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。


入力例 1

4 3 2
3 4 1 10

出力例 1

5 4 5 10
  • 1 回目の操作では、前から 3 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 3,4,3,10 になります。
  • 2 回目の操作では、前から 1 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 5,4,3,10 になります。
  • 3 回目の操作では、前から 3 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 5,4,5,10 になります。

入力例 2

2 1000000000000 100000
1000000000000 1

出力例 2

50000500000000000 50000500000000001

入力例 3

3 1415 9
26 53 58

出力例 3

4292 4292 4288

Problem Statement

N children are standing in line. Initially, the i-th child from the front has A_i candies.

You are going to repeat the following operation M times.

  • Give K candies to the child with the fewest candies (if there are multiple such children, to the frontmost one among them).

Find how many candies the children will have after the M operations.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^{12}
  • 1 \leq K \leq 10^5
  • 0 \leq A_i \leq 10^{12}
  • All input values are integers.

Input

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

N M K
A_1 A_2 \ldots A_N

Output

Let B_i be the number of candies that the i-th child from the front will have after the M operations. Print B_1,B_2,\ldots, and B_N in this order, with spaces in between.


Sample Input 1

4 3 2
3 4 1 10

Sample Output 1

5 4 5 10
  • The 1-st operation gives candies to the 3-rd child from the front. Now, the children have 3,4,3, and 10 candies.
  • The 2-nd operation gives candies to the 1-st child from the front. Now, the children have 5,4,3, and 10 candies.
  • The 3-rd operation gives candies to the 3-rd child from the front. Now, the children have 5,4,5, and 10 candies.

Sample Input 2

2 1000000000000 100000
1000000000000 1

Sample Output 2

50000500000000000 50000500000000001

Sample Input 3

3 1415 9
26 53 58

Sample Output 3

4292 4292 4288
J - Joya no Kane

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

除夜の鐘の音が等間隔に N 回鳴りました。 より具体的には、鐘の音はある正整数 d と整数 t によって、 時刻 t, d+t, 2d+t, \ldots, (N-1)d+t と表される N 個の時刻それぞれに鳴りました。

高橋君は、そのうち時刻 A_1, A_2, \ldots, A_K に鳴った K 回の鐘の音を聞きました。 高橋君が鐘の音を聞いた時刻に実際に鐘の音が鳴ったことは確かですが、 高橋君が鐘の音を聞いていない時刻にも鐘の音が鳴った可能性があります。

NK、および、A_1, A_2, \ldots, A_K が与えられるので、 正整数 d としてあり得るものすべてを昇順に列挙してください。

なお、本問題の制約下において、正整数 d としてあり得るものの個数は有限であることが証明できます。

制約

  • 2 \leq N \leq 10^9
  • 2 \leq K \leq \min \lbrace N, 2 \times 10^5 \rbrace
  • 0 \leq A_1 \lt A_2 \lt \cdots \lt A_K \leq 10^9
  • 入力はすべて整数
  • 正整数 d としてあり得るものが少なくとも 1 つ存在する。

入力

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

N K
A_1 A_2 \ldots A_K

出力

下記の形式にしたがって、正整数 d としてあり得るものすべてを昇順に列挙せよ。

M
d_1 d_2 \ldots d_M

すなわち、まず 1 行目に、正整数 d としてあり得るものの個数 M を出力し、 2 行目に、正整数 d としてあり得るものすべてを昇順に並べた列 (d_1, d_2, \ldots, d_M) を空白区切りで出力せよ。


入力例 1

8 3
3 7 15

出力例 1

2
2 4

正整数 d としてあり得るものは、242 個です。

  • d = 2 については、例えば時刻 3, 5, 7, 9, 11, 13, 15, 178 個の時刻に鐘の音が鳴ったという可能性が考えられます。
  • d = 4 については、例えば時刻 -5, -1, 3, 7, 11, 15, 19, 238 個の時刻に鐘の音が鳴ったという可能性が考えられます。

入力例 2

500 22
30 42 138 318 354 378 450 462 522 582 630 738 834 894 930 942 1002 1050 1062 1110 1146 1158

出力例 2

4
3 4 6 12

Problem Statement

The New Year's bell rang N times at equal intervals. More specifically, the bell rang at times t, d+t, 2d+t, \ldots, (N-1)d+t for some positive integer d and integer t.

Takahashi heard the bell ring at times A_1, A_2, \ldots, A_K. Although it is certain that the bell actually rang when Takahashi heard the sound, the bell may have also rung at other times.

You are given N, K, and A_1, A_2, \ldots, A_K. List all possible values for the positive integer d in ascending order.

Under the constraints of this problem, it can be proved that the number of possible values for d is finite.

Constraints

  • 2 \leq N \leq 10^9
  • 2 \leq K \leq \min \lbrace N, 2 \times 10^5 \rbrace
  • 0 \leq A_1 \lt A_2 \lt \cdots \lt A_K \leq 10^9
  • All input values are integers.
  • There is at least one possible value for the positive integer d.

Input

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

N K
A_1 A_2 \ldots A_K

Output

List all possible values for the positive integers d in ascending order in the following format:

M
d_1 d_2 \ldots d_M

That is, the first line should contain M, the number of possible values for d, and the second line should contain (d_1, d_2, \ldots, d_M), all possible values for d in ascending order, with spaces in between.


Sample Input 1

8 3
3 7 15

Sample Output 1

2
2 4

There are two possible values for d: 2 and 4.

  • For d = 2, it is possible that the bell rang eight times, for instance, at times 3, 5, 7, 9, 11, 13, 15, 17.
  • For d = 4, it is possible that the bell rang eight times, for instance, at times -5, -1, 3, 7, 11, 15, 19, 23.

Sample Input 2

500 22
30 42 138 318 354 378 450 462 522 582 630 738 834 894 930 942 1002 1050 1062 1110 1146 1158

Sample Output 2

4
3 4 6 12
K - Grid

Time Limit: 8 sec / Memory Limit: 1024 MiB

問題文

N \times N のマス目があります。上から i 番目、左から j 番目のマスを マス (i,j) と呼ぶこととします。

それぞれのマスは、スタートかゴールか通路か穴のマスのいずれかです。マス (i,j) の状態は S_{i,j} によって与えられます。

  • S はそのマスがスタートであることを示します。スタートはただ 1 個のみ存在します。
  • G はそのマスがゴールであることを示します。ゴールは 1 個以上存在します。
  • . はそのマスが通路であることを示します。
  • X はそのマスが穴であることを示します。

k=1,2,\dots,N-1 に対して、以下の問題を解いてください。

始め、あなたはスタートのマスにいます。その後、以下の操作を繰り返します。

  • 上下左右の 4 方向のうち、いずれかの方向を選ぶ。選んだ方向に k 回連続で移動する。

ただし、操作によって穴のマスを通過することや、マス目の外に出ることは許されません。

操作が終わったあとにゴールのマスにいる状態にすることができるか判定し、できるのであれば必要な操作の回数の最小値を求めてください。

なお、移動中にゴールを通過しても、ゴールのマスにいる状態になったとはみなさないことに注意してください。

制約

  • 1 \le N \le 1500
  • S_{i,j}S,G,.,X のいずれかである。
  • S_{i,j}=S である (i,j) はただ 1 個存在する。
  • S_{i,j}=G である (i,j)1 個以上存在する。
  • N は整数である。

入力

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

N
S_1
S_2
\vdots
S_N

出力

N-1 行出力せよ。

1 \le i \le N-1 に対して、i 行目には k=i のときに操作が終わったあとにゴールのマスにいる状態にすることができるのであれば必要な操作の回数の最小値を、そうでないのであれば -1 を出力せよ。


入力例 1

5
SX...
.....
..GX.
..XG.
X.X.G

出力例 1

4
2
-1
-1

k=2 のとき、以下のように操作をすることで 2 回で操作が終わったあとにゴールのマスにいる状態にすることができます。

  • 下を選ぶ。(1,1) から (3,1) に移動する。
  • 右を選ぶ。(3,1) から (3,3) に移動する。

1 回の移動で操作が終わったあとにゴールのマスにいる状態にすることはできないので、答えは 2 です。

k=3 のとき、以下のような操作はできないことに注意してください。

  • 右を選ぶ。(1,1) から (1,4) に移動する。

この操作は、操作中に穴であるマス (1,2) を通過しているため許されません。


入力例 2

2
GX
XS

出力例 2

-1

Problem Statement

There is an N \times N grid. Let (i,j) denote the square at the i-th row from the top and j-th square from the left.

Each square is one of the following: the starting point, a goal, a passage, and a hole. The state of the square (i,j) is given as S_{i,j}.

  • S indicates that the square is the starting point. There is exactly one starting point.
  • G indicates that the square is a goal. There is one or more goals.
  • . indicates that the square is a passage.
  • X indicates that the square is a hole.

Solve the following problem for k=1,2,\dots,N-1.

You are initially at the starting square. Then, you repeat the following operation.

  • Choose one of the four directions: up, down, left, right. Move k squares consecutively in the chosen direction.

You may not pass through a hole square or exit the grid by the operation.

Determine if you can be at a goal square at the end of an operation, and if so, find the minimum number of operations required to do so.

Note that passing through a goal in the middle of an operation does not count as finishing at a goal square.

Constraints

  • 1 \le N \le 1500
  • S_{i,j} is S, G, ., or X.
  • There is exactly one pair (i,j) such that S_{i,j}=S.
  • There is one or more pairs (i,j) such that S_{i,j}=G.
  • N is an integer.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print N-1 lines.

For 1 \le i \le N-1, the i-th line should contain the minimum number of operations required to be at a goal square at the end of an operation for k=i if it is possible to do so, and -1 otherwise.


Sample Input 1

5
SX...
.....
..GX.
..XG.
X.X.G

Sample Output 1

4
2
-1
-1

For k=2, you can perform two operations as follows to be at the goal square at the end of an operation.

  • Choose down. Move from (1,1) to (3,1).
  • Choose right. Move from (3,1) to (3,3).

With just one operation, you cannot be at a goal square at the end of an operation, so the answer is 2.

Note that for k=3, the operation cannot be performed as follows.

  • Choose right. Move from (1,1) to (1,4).

This operation is not allowed because it passes through (1,2), which is a hole.


Sample Input 2

2
GX
XS

Sample Output 2

-1
L - Average queries

Time Limit: 3 sec / Memory Limit: 1024 MiB

問題文

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

また、0\leq L<R\leq N をみたす整数の組 (L,R) に対して、f(L,R)\displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} で定めます。

Q 個のクエリを与えられた順に処理してください。 クエリは次の 2 種類のいずれかです。

  • タイプ 1 : 0\leq x\leq N をみたす整数 x が与えられる。xS に含まれないならば xS に追加し、xS に含まれるならば xS から取り除く。
  • タイプ 2 : l,r\in S かつ 0\leq l<r\leq N をみたす整数の組 (l,r) すべてについての f(l,r) の最大値を X とする。このとき、X は互いに素な正整数 P, Q を用いて \frac{P}{Q} と一意に表される。P, Q を空白区切りで出力する。ただし、このクエリが与えられるとき、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r) が少なくとも 1 つ存在することが保証される。

制約

  • 1\leq N\leq 10^5
  • 3\leq Q\leq 3\times 10^5
  • 1\leq A_i\leq 10^9
  • 0\leq x\leq N
  • 入力はすべて整数
  • タイプ 2 のクエリが少なくとも 1 つ存在する。
  • タイプ 2 のクエリを処理する時点において、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r) が少なくとも 1 つ存在する。

入力

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

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q

query_i において、まずクエリのタイプを表す番号 t_i (1\leq t_i\leq 2) が与えられる。 その後、t_i=1ならば整数 x (0\leq x\leq N) が与えられ、t_i=2 ならば何も与えられない。 すなわち、次のいずれかの形式で与えられる。

1 x
2

出力

与えられた Q 個のクエリのうち、タイプ 2 のクエリの個数を k として、k 行出力せよ。
i (1\leq i\leq k) 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。


入力例 1

3 8
2 3 5
1 0
1 3
2
1 2
2
1 1
1 3
2

出力例 1

10 3
5 1
3 1

f(L,R) の値は次のようになります。

  • f(0,1)=\frac{2}{1}=\frac{2}{1}
  • f(0,2)=\frac{2+3}{2}=\frac{5}{2}
  • f(0,3)=\frac{2+3+5}{3}=\frac{10}{3}
  • f(1,2)=\frac{3}{1}=\frac{3}{1}
  • f(1,3)=\frac{3+5}{2}=\frac{8}{2}
  • f(2,3)=\frac{5}{1}=\frac{5}{1}

クエリは次のように処理されます。

  • 1 番目のクエリはタイプ 1 であり、x=0 が与えられています。0\notin S であるため、S0 を追加します。
  • 2 番目のクエリでは、S3 を追加します。
  • 3 番目のクエリはタイプ 2 であり、この時点で S= \{ 0,3 \} であるため、l,r\in S かつ 0\leq l<r\leq N をみたす (l,r)(0,3) のみです。 f(0,3)=\frac{10}{3} であるため、10, 3 を空白区切りに出力します。
  • 4 番目のクエリでは、S2 を追加します。
  • 5 番目のクエリの時点で S=\{0,2,3\} であり条件をみたす (l,r)(0,2), (0,3), (2,3)3 つです。このうち f(l,r) が最大となるのは f(2,3)=\frac{5}{1} のときです。よって、5, 1 をこの順に出力します。
  • 6 番目のクエリでは、S1 を追加します。
  • 7 番目のクエリの直前の時点で 3\in S であるため、3S から取り除きます。
  • 8 番目のクエリの時点で S=\{ 0,1,2\} であり、条件をみたす (l,r) のうちで f(l,r) が最大となるのは f(1,2)=\frac{3}{1} のときです。よって、3, 1 をこの順に出力します。

入力例 2

2 3
1 1
1 0
1 2
2

出力例 2

1 1

タイプ 2 のそれぞれのクエリにおける P, Q は互いに素でなくてはならないことに注意してください。すなわち、このテストケースにおいて 2 2 と出力してはいけません。

Problem Statement

You are given a sequence of length N consisting of positive integers, A=(A_1,A_2,\ldots,A_N), and an empty set S.

Let us define f(L,R) as \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} for a pair of integers (L,R) such that 0\leq L<R\leq N.

Process Q queries in the given order. Each query is of one of the following two types.

  • Type 1 : You are given an integer x satisfying 0\leq x\leq N. If x is not in S, add x to S; otherwise, remove x from S.
  • Type 2 : Let X be the maximum value of f(l,r) over all pairs of integers (l,r) such that l,r\in S and 0\leq l<r\leq N. Then, X is uniquely represented as \frac{P}{Q} using positive integers P and Q that are coprime. Print P and Q separated by spaces. It is guaranteed that at the time this query is given, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Constraints

  • 1\leq N\leq 10^5
  • 3\leq Q\leq 3\times 10^5
  • 1\leq A_i\leq 10^9
  • 0\leq x\leq N
  • All input values are integers.
  • There is at least one query of type 2.
  • At the time of processing a query of type 2, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Input

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

N Q
A_1 A_2 \ldots A_N
query_1
query_2
\vdots
query_Q

Each query_i starts with a number t_i (1\leq t_i\leq 2) representing the type of the given query. It is followed by an integer x (0\leq x\leq N) if t_i=1, and nothing if t_i=2. That is, query_i is in one of the following formats:

1 x
2

Output

Print k lines, where k is the number of queries of type 2 among the given Q queries.
The i-th line (1\leq i\leq k) should contain the answer to the i-th query of type 2.


Sample Input 1

3 8
2 3 5
1 0
1 3
2
1 2
2
1 1
1 3
2

Sample Output 1

10 3
5 1
3 1

The values of f(L,R) are as follows.

  • f(0,1)=\frac{2}{1}=\frac{2}{1}
  • f(0,2)=\frac{2+3}{2}=\frac{5}{2}
  • f(0,3)=\frac{2+3+5}{3}=\frac{10}{3}
  • f(1,2)=\frac{3}{1}=\frac{3}{1}
  • f(1,3)=\frac{3+5}{2}=\frac{8}{2}
  • f(2,3)=\frac{5}{1}=\frac{5}{1}

The queries are processed as follows.

  • The first query is of type 1 and gives x=0. Since 0\notin S, add 0 to S.
  • The second query adds 3 to S.
  • The third query is of type 2, and we have S= \{ 0,3 \} at this point, so (0,3) is the only (l,r) such that l,r\in S and 0\leq l<r\leq N. We have f(0,3)=\frac{10}{3}, so print 10 and 3 separated by spaces.
  • The fourth query adds 2 to S.
  • At the time of the fifth query, we have S=\{0,2,3\}, and the pairs (l,r) that satisfy the condition are (0,2), (0,3), and (2,3). The maximum f(l,r) over these pairs is f(2,3)=\frac{5}{1}. Thus, print 5 and 1 in this order.
  • The sixth query adds 1 to S.
  • We have 3\in S just before the seventh query, so remove 3 from S.
  • At the time of the eighth query, we have S=\{ 0,1,2\}, and the maximum f(l,r) over the pairs satisfying the conditions is f(1,2)=\frac{3}{1}. Thus, print 3 and 1 in this order.

Sample Input 2

2 3
1 1
1 0
1 2
2

Sample Output 2

1 1

Note that P and Q in each query of type 2 must be coprime. That is, you must not print 2 2 in this test case.

M - Intersection of Line Segments

Time Limit: 2 sec / Memory Limit: 1024 MiB

問題文

xy -平面上に 2 つの線分があります。 i 番目の線分の端点は座標 (a_i,b_i) と座標 (c_i,d_i) です。
これら 2 つの線分が交点を持つかどうかを判定してください。

制約

  • -1000 \leq a_i,b_i,c_i,d_i \leq 1000
  • (a_i,b_i)\neq (c_i,d_i)
  • 入力はすべて整数

入力

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

a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2

出力

2 つの線分が交点を持つならば Yes と、持たないならば No と出力せよ。


入力例 1

0 0 10 10
0 10 10 0

出力例 1

Yes

下図のように、2 つの線分は座標 (5,5) で交わります。

image


入力例 2

0 0 10 0
0 10 0 0

出力例 2

Yes

image


入力例 3

0 0 10 0
0 10 0 1

出力例 3

No

image


入力例 4

0 3 8 7
0 3 8 7

出力例 4

Yes

Problem Statement

There are two line segments in the xy-plane. The endpoints of the i-th line segment are at coordinates (a_i,b_i) and (c_i,d_i).
Determine if these two line segments intersect.

Constraints

  • -1000 \leq a_i,b_i,c_i,d_i \leq 1000
  • (a_i,b_i)\neq (c_i,d_i)
  • All input values are integers.

Input

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

a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2

Output

Print Yes if the two line segments intersect, and No otherwise.


Sample Input 1

0 0 10 10
0 10 10 0

Sample Output 1

Yes

As shown below, the two line segments intersect at coordinates (5,5).

image


Sample Input 2

0 0 10 0
0 10 0 0

Sample Output 2

Yes

image


Sample Input 3

0 0 10 0
0 10 0 1

Sample Output 3

No

image


Sample Input 4

0 3 8 7
0 3 8 7

Sample Output 4

Yes
N - Sorting and Function

Time Limit: 4 sec / Memory Limit: 1024 MiB

問題文

正整数の多重集合(同一の要素を複数個含むことが許された集合) S に対して、関数 f(S) を以下のように定義します。

  • まず、 S の要素を昇順に並べた数列を A=(A_0,A_1,...,A_{|S|-1}) とします。
  • そして、 f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i と定めます。この定数 K は入力で与えられます。
  • ただし、 S が空の場合、 f(S)=0 とします。

最初空の多重集合 T があります。この集合に対して以下の操作を合わせて Q 回行います。

+ x

Tx1 つ追加する。

- x

T から x1 つ削除する。但し、このとき Tx1 つ以上存在することが保証される。

各操作を行った後、その時点での f(T) の値を 998244353 で割った余りを求めてください。

制約

  • Q,K は整数
  • 1 \le Q \le 3 \times 10^5
  • 1 \le K < 998244353
  • 全ての操作について、 x は整数
  • 操作 + について、 1 \le x < 998244353
  • 操作 - について、その時点で Tx1 つ以上存在する。

入力

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

Q K
ope_1
ope_2
\vdots
ope_Q

但し、 ope_ii 回目に行う操作を表す。

出力

全体で Q 行出力せよ。
そのうち i 行目には、 i 回目の操作を終えた時点での f(T) の値を 998244353 で割った余りを出力せよ。


入力例 1

10 2
+ 7
- 7
+ 2
+ 3
- 2
+ 3
+ 5
- 3
+ 998244352
+ 5

出力例 1

7
0
2
8
3
9
29
13
9
25
  • 1 個目の操作では、 T71 つ追加します。
    • このとき、 T=\{7\} であり、 f(T)=7 です。
  • 2 個目の操作では、 T から 71 つ削除します。
    • このとき、 T=\{\} であり、 f(T)=0 です。
  • 3 個目の操作では、 T21 つ追加します。
    • このとき、 T=\{2\} であり、 f(T)=2 です。
  • 4 個目の操作では、 T31 つ追加します。
    • このとき、 T=\{2,3\} であり、 f(T)=8 です。
  • 5 個目の操作では、 T から 21 つ削除します。
    • このとき、 T=\{3\} であり、 f(T)=3 です。
  • 6 個目の操作では、 T31 つ追加します。
    • このとき、 T=\{3,3\} であり、 f(T)=9 です。
  • 7 個目の操作では、 T51 つ追加します。
    • このとき、 T=\{3,3,5\} であり、 f(T)=29 です。
  • 8 個目の操作では、 T から 31 つ削除します。
    • このとき、 T=\{3,5\} であり、 f(T)=13 です。
  • 9 個目の操作では、 T9982443521 つ追加します。
    • このとき、 T=\{3,5,998244352\} であり、 f(T)=3992977421 なので、これを 998244353 で割った余りである 9 を出力してください。
  • 10 個目の操作では、 T51 つ追加します。
    • このとき、 T=\{3,5,5,998244352\} であり、 f(T)=7985954849 なので、これを 998244353 で割った余りである 25 を出力してください。

Problem Statement

For a multiset (set with duplicate elements allowed) S of positive integers, let us define the function f(S) as follows.

  • First, let A=(A_0,A_1,...,A_{|S|-1}) be the sorted list of the elements of S in ascending order.
  • Then, let f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i. This constant K is given from the input.
  • Here, let f(S)=0 if S is empty.

There is an initially empty multiset T. Let us perform the following operations on this set Q times in total.

+ X

Add one instance of x to T.

- x

Remove one instance of x from T. It is guaranteed that at least one instance of x exists in T at this time.

After each operation, find the value of f(T) modulo 998244353 at that time.

Constraints

  • Q and K are integers.
  • 1 \le Q \le 3 \times 10^5
  • 1 \le K < 998244353
  • For every operation, x is an integer.
  • For each operation +, 1 \le x < 998244353.
  • For each operation -, there is one or more instances of x in T at that time.

Input

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

Q K
ope_1
ope_2
\vdots
ope_Q

Here, ope_i represents the i-th operation to be performed.

Output

Print Q lines in total.
The i-th line should contain the value of f(T) modulo 998244353 at the end of the i-th operation.


Sample Input 1

10 2
+ 7
- 7
+ 2
+ 3
- 2
+ 3
+ 5
- 3
+ 998244352
+ 5

Sample Output 1

7
0
2
8
3
9
29
13
9
25
  • The first operation adds one instance of 7 to T.
    • Now, T=\{7\} and f(T)=7.
  • The second operation removes one instance of 7 from T.
    • Now, T=\{\} and f(T)=0.
  • The third operation adds one instance of 2 to T.
    • Now, T=\{2\} and f(T)=2.
  • The fourth operation adds one instance of 3 to T.
    • Now, T=\{2,3\} and f(T)=8.
  • The fifth operation removes one instance of 2 from T.
    • Now, T=\{3\} and f(T)=3.
  • The sixth operation adds one instance of 3 to T.
    • Now, T=\{3,3\} and f(T)=9.
  • The seventh operation adds one instance of 5 to T.
    • Now, T=\{3,3,5\} and f(T)=29.
  • The eighth operation removes one instance of 3 from T.
    • Now, T=\{3,5\} and f(T)=13.
  • The ninth operation adds one instance of 998244352 to T.
    • Now, T=\{3,5,998244352\} and f(T)=3992977421, so print this modulo 998244353, that is, 9.
  • The tenth operation adds one instance of 5 to T.
    • Now, T=\{3,5,5,998244352\} and f(T)=7985954849, so print this modulo 998244353, that is, 25.
O - Add Sequences

Time Limit: 3 sec / Memory Limit: 1024 MiB

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N) と長さ K の数列 P=(P_1,P_2,\ldots,P_K) が与えられます。

今から、数列 A に対して以下の Q 回の操作を行います。

  • q\ (1\leq q \leq Q) 回目の操作は整数 l_q,r_q\ (1\leq l_q \leq r_q\leq N) および長さ K の数列 b_q = (b_{q,1},b_{q,2},\ldots,b_{q,K}) によって表される。 q 回目の操作では以下の線形漸化式で定まる無限数列 B=(B_1,B_2,\ldots) を考え、 i=1,2,\ldots,r_q-l_q+1 それぞれに対して、A_{l_q+i-1}B_i を加算する。
    • B_j=b_{q,j}\ (1\leq j \leq K)
    • B_j=P_1B_{j-1}+P_2B_{j-2}+\ldots +P_KB_{j-K}\ (j > K)

全ての操作を行った後の A の各要素の値を 998244353 で割った余りを求めてください。

制約

  • 1\leq N,Q \leq 2\times 10^5
  • 1\leq K \leq 10
  • 1\leq l_q \leq r_q\leq N
  • 0\leq A_i,P_i,b_{q,i} < 998244353
  • 入力は全て整数

入力

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

N K Q
A_1 A_2 \ldots A_N
P_1 P_2 \ldots P_K
l_1 r_1
b_{1,1} b_{1,2} \ldots b_{1,K}
\vdots
l_Q r_Q
b_{Q,1} b_{Q,2} \ldots b_{Q,K}

出力

全ての操作を行った後の A の各要素の値を 998244353 で割った余りを空白区切りで出力せよ。


入力例 1

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

出力例 1

3 6 9 12 6

最初、A=(0,0,0,0,0) です。

  • 1 回目の操作では B=(3,1,5,11,27,\ldots) です。操作後、A=(3,1,5,11,0) になります。
  • 2 回目の操作では B=(4,1,6,13,32,\ldots) です。操作後、A=(3,1,9,12,6) になります。
  • 3 回目の操作では B=(5,9,23,55,133,\ldots) です。操作後、A=(3,6,9,12,6) になります。

よって、全ての操作を行った後の A(3,6,9,12,6) です。


入力例 2

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

出力例 2

8

入力例 3

10 3 5
306334866 801978559 895954374 576826717 755317213 872021310 894146017 171871727 347837426 489203653
259995927 523608184 755770553
4 7
822177140 73169010 811074390
7 8
739309938 819084714 711663615
1 9
105947194 88003242 226522376
6 8
544083472 975159386 830222368
1 9
478160947 233931690 460328037

出力例 3

890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653

Problem Statement

You are given a sequence of length N, A=(A_1,A_2,\ldots,A_N), and another of length K, P=(P_1,P_2,\ldots,P_K).

We now perform the following Q operations on the sequence A.

  • The q-th operation (1\leq q \leq Q) is represented by integers l_q,r_q\ (1\leq l_q \leq r_q\leq N) and a sequence of length K, b_q = (b_{q,1},b_{q,2},\ldots,b_{q,K}). For the q-th operation, consider the infinite sequence B=(B_1,B_2,\ldots) determined by the following linear recurrence relation, and add B_i to A_{l_q+i-1} for each i=1,2,\ldots,r_q-l_q+1.
    • B_j=b_{q,j}\ (1\leq j \leq K)
    • B_j=P_1B_{j-1}+P_2B_{j-2}+\ldots +P_KB_{j-K}\ (j > K)

Find the value, modulo 998244353, of each element of A after all the operations.

Constraints

  • 1\leq N,Q \leq 2\times 10^5
  • 1\leq K \leq 10
  • 1\leq l_q \leq r_q\leq N
  • 0\leq A_i,P_i,b_{q,i} < 998244353
  • All input values are integers.

Input

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

N K Q
A_1 A_2 \ldots A_N
P_1 P_2 \ldots P_K
L_1 R_1
B_{1,1} B_{1,2} \ldots B_{1,K}
\vdots
l_Q r_Q
b_{Q,1} b_{Q,2} \ldots b_{Q,K}

Output

Print the values, modulo 998244353, of the elements of A after all the operations.


Sample Input 1

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

Sample Output 1

3 6 9 12 6

Initially, A=(0,0,0,0,0,0).

  • In the first operation, B=(3,1,5,11,27,\ldots). After this operation, A=(3,1,5,11,0,0).
  • In the second operation, B=(4,1,6,13,32,\ldots). After this operation, A=(3,1,9,12,6).
  • In the third operation, B=(5,9,23,55,133,\ldots). After this operation, A=(3,6,9,12,6).

Thus, after all the operations, A is (3,6,9,12,6).


Sample Input 2

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

Sample Output 2

8

Sample Input 3

10 3 5
306334866 801978559 895954374 576826717 755317213 872021310 894146017 171871727 347837426 489203653
259995927 523608184 755770553
4 7
822177140 73169010 811074390
7 8
739309938 819084714 711663615
1 9
105947194 88003242 226522376
6 8
544083472 975159386 830222368
1 9
478160947 233931690 460328037

Sample Output 3

890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653