A - World Cup

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

あるスポーツ大会は西暦年を 4 で割った余りが 2 である年の 6 月に開催されます。
現在が西暦 Y 年の 1 月である時、このスポーツ大会が次に開催されるのは西暦何年になるかを求めてください。

制約

  • 2000 \leq Y \leq 3000
  • Y は整数

入力

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

Y

出力

答えを出力せよ。


入力例 1

2022

出力例 1

2022

2022 は 4 で割った余りが 2 なので、現在が西暦 2022 年の 1 月である時、次の開催は同年の 6 月です。


入力例 2

2023

出力例 2

2026

入力例 3

3000

出力例 3

3002

Score : 100 points

Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

  • 2000 \leq Y \leq 3000
  • Y is an integer.

Input

Input is given from Standard Input in the following format:

Y

Output

Print the answer.


Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.


Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002
B - 1-2-4 Test

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 100 点

問題文

3 問の問題からなる試験があり、それぞれの問題の配点は 1 点、2 点、4 点でした。

高橋君、青木君、すぬけ君の 3 人がこの試験を受け、 高橋君は A 点、青木君は B 点を取りました。

すぬけ君は、高橋君と青木君のうち少なくとも一方が解けた問題は解け、 2 人とも解けなかった問題は解けませんでした。

すぬけ君の点数を求めてください。

ただし、この問題の制約下で、すぬけ君の点数は一意に定まる事が証明できます。

制約

  • 0\leq A,B \leq 7
  • A,B は整数

入力

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

A B

出力

すぬけ君の点数を整数で出力せよ。


入力例 1

1 2

出力例 1

3

高橋君は 1 点を取った事から、 1 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。
同様に、青木君は 2 点を取った事から、 2 点の問題のみを正解し、それ以外の 2 問は解けなかったことがわかります。

よって、すぬけ君は 1 点の問題と 2 点の問題を正解し、高橋君と青木君がともに解けなかった 4 点の問題はすぬけ君も解けなかったことになるので、3 点を取ったことがわかります。よって、3 を出力します。


入力例 2

5 3

出力例 2

7

高橋君は 5 点を取った事から、 1 点の問題と 4 点の問題を正解し、 2 点の問題は解けなかったことがわかります。
同様に、青木君は 3 点を取った事から、 1 点の問題と 2 点の問題を正解し、 4 点の問題は解けなかったことがわかります。

よって、3 問すべてについて、高橋君と青木君の少なくとも一方が正解しているため、すぬけ君はすベての問題に正解し、7 点を取ったことがわかります。 よって、7 を出力します。


入力例 3

0 0

出力例 3

0

高橋君と青木君は 2 人ともいずれの問題も解けていません。 よって、すぬけ君もいずれの問題も解けておらず、 0 を出力します。

Score : 100 points

Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

  • 0\leq A,B \leq 7
  • A and B are integers.

Input

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

A B

Output

Print Snuke's score as an integer.


Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.


Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.


Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

C - chess960

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。 高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

  • S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。

  • K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

  • S は 長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

S

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。


入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。 また、K は 2 つの R の間にあります。よって条件を満たします。


入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。


入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

  • Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.

  • K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

  • S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

S

Output

Print Yes if S satisfies the conditions; print No otherwise.


Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.


Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.


Sample Input 3

BRKRBQNN

Sample Output 3

No
D - Digit Sum

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

正整数 n の桁和を、 n を十進法で表したときの各桁の和と定めます。例えば 2026 の桁和は 2+0+2+6=10 です。

N 以下の正整数のうち、桁和が K であるものの個数を求めてください。

制約

  • 1\leq N,K \leq 10^5
  • 入力は全て整数

入力

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

N K

出力

答えを出力せよ。


入力例 1

30 4

出力例 1

3

30 以下の正整数のうち、桁和が 4 であるものは、4,13,22 の 3 個です。


入力例 2

2026 10

出力例 2

121

入力例 3

99999 45

出力例 3

1

Score : 200 points

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits when n is represented in decimal. For example, the digit sum of 2026 is 2+0+2+6=10.

Find the number of positive integers not exceeding N whose digit sum is K.

Constraints

  • 1\leq N,K \leq 10^5
  • All input values are integers.

Input

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

N K

Output

Output the answer.


Sample Input 1

30 4

Sample Output 1

3

Among the positive integers not exceeding 30, there are three integers whose digit sum is 4: 4,13,22.


Sample Input 2

2026 10

Sample Output 2

121

Sample Input 3

99999 45

Sample Output 3

1
E - ~

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。

  • A の長さ |A| は 4 以上である
  • A_1 < A_2 である
  • A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である 
  • A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である 

数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_N) が与えられます。P の連続部分列であってチルダ型である数列の個数を求めてください。

制約

  • 4 \leq N \leq 3 \times 10^5
  • P = (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) を並べ替えて得られる数列
  • 入力される値はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。


入力例 1

6
1 3 6 4 2 5

出力例 1

2

数列 (1, 3, 6, 4, 2, 5) の連続部分列のうちチルダ型であるものは (3, 6, 4, 2, 5), (1, 3, 6, 4, 2, 5) の 2 つのみです。


入力例 2

6
1 2 3 4 5 6

出力例 2

0

入力例 3

12
11 3 8 9 5 2 10 4 1 6 12 7

出力例 3

4

Score : 350 points

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

  • The length |A| is at least 4.
  • A_1 < A_2.
  • There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
  • There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

  • 4 \leq N \leq 3 \times 10^5
  • P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
  • All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.


Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

2

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).


Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

0

Sample Input 3

12
11 3 8 9 5 2 10 4 1 6 12 7

Sample Output 3

4
F - Rotatable Array

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A があり、最初 A_i = i です。 以下のクエリを全部で Q 個処理してください。

  • タイプ 1 : A_p を x に変更する。
  • タイプ 2 : A_p を出力する。
  • タイプ 3 : 「 A の先頭の要素を末尾にする」という操作を k 回繰り返す。
    • 厳密には、 A を (A_2,A_3,\dots,A_N,A_1) に置き換えることを k 回繰り返す。

制約

  • 入力は全て整数
  • 1 \le N \le 10^6
  • 1 \le Q \le 3 \times 10^5
  • 全てのクエリは以下の制約を満たす
    • 1 \le p \le N
    • 1 \le x \le 10^6
    • 1 \le k \le 10^9

入力

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

但し、 \rm{Query}_i は i 個目のクエリを表す。

タイプ 1 のクエリは以下の形式で与えられる。

1 p x

タイプ 2 のクエリは以下の形式で与えられる。

2 p

タイプ 3 のクエリは以下の形式で与えられる。

3 k

出力

タイプ 2 のクエリが現れる度に、その解答を 1 行に出力せよ。


入力例 1

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

出力例 1

3
1
1000000

この入力には 5 個のクエリが含まれます。

  • 最初、 A=(1,2,3,4,5) です。
  • 1 番目のクエリはタイプ 2 で、 A_3=3 を出力します。
  • 2 番目のクエリはタイプ 1 で、 A_2=1000000 に置き換えます。
    • クエリの結果、 A=(1,1000000,3,4,5) となります。
  • 3 番目のクエリはタイプ 3 で、「 A の先頭の要素を末尾にする」という操作を 4 回繰り返します。
    • クエリの結果、 A=(5,1,1000000,3,4) となります。
  • 4 番目のクエリはタイプ 2 で、 A_2=1 を出力します。
  • 5 番目のクエリはタイプ 2 で、 A_3=1000000 を出力します。

入力例 2

1000000 2
1 1000000 999999
3 1000000000

出力例 2



出力が空である場合もあります。

Score : 300 points

Problem Statement

There is an integer sequence A of length N, initially A_i = i. Process a total of Q queries of the following types:

  • Type 1: Change A_p to x.
  • Type 2: Output A_p.
  • Type 3: Repeat the operation "move the first element of A to the end" k times.
    • Formally, replace A with (A_2,A_3,\dots,A_N,A_1) k times.

Constraints

  • All input values are integers.
  • 1 \le N \le 10^6
  • 1 \le Q \le 3 \times 10^5
  • All queries satisfy the following constraints:
    • 1 \le p \le N
    • 1 \le x \le 10^6
    • 1 \le k \le 10^9

Input

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

N Q
\rm{Query}_1
\rm{Query}_2
\vdots
\rm{Query}_Q

Here, \rm{Query}_i represents the i-th query.

Type 1 queries are given in the following format:

1 p x

Type 2 queries are given in the following format:

2 p

Type 3 queries are given in the following format:

3 k

Output

For each Type 2 query, output the answer on a line.


Sample Input 1

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

Sample Output 1

3
1
1000000

This input contains 5 queries.

  • Initially, A=(1,2,3,4,5).
  • The 1st query is Type 2: output A_3=3.
  • The 2nd query is Type 1: replace A_2 with 1000000.
    • After the query, A=(1,1000000,3,4,5).
  • The 3rd query is Type 3: repeat the operation "move the first element of A to the end" 4 times.
    • After the query, A=(5,1,1000000,3,4).
  • The 4th query is Type 2: output A_2=1.
  • The 5th query is Type 2: output A_3=1000000.

Sample Input 2

1000000 2
1 1000000 999999
3 1000000000

Sample Output 2



The output may be empty.

G - Left Right Operation

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

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

あなたは以下の連続する操作をちょうど一度だけ行います。

  • 整数 x\ (0\leq x \leq N) を選ぶ。x として 0 を選んだ場合何もしない。 x として 1 以上の整数を選んだ場合、A_1,A_2,\ldots,A_x をそれぞれ L で置き換える。

  • 整数 y\ (0\leq y \leq N) を選ぶ。y として 0 を選んだ場合何もしない。 y として 1 以上の整数を選んだ場合、A_{N},A_{N-1},\ldots,A_{N-y+1} をそれぞれ R で置き換える。

操作後の A の要素の総和として考えられる最小値を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • -10^9 \leq L, R\leq 10^9
  • -10^9 \leq A_i\leq 10^9
  • 入力は全て整数

入力

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

N L R
A_1 A_2 \ldots A_N

出力

答えを出力せよ。


入力例 1

5 4 3
5 5 0 6 3

出力例 1

14

x=2,y=2 として操作をすると、数列 A = (4,4,0,3,3) となり、要素の総和は 14 になります。

これが達成可能な最小値です。


入力例 2

4 10 10
1 2 3 4

出力例 2

10

x=0,y=0 として操作をすると、数列 A = (1,2,3,4) となり、要素の総和は 10 になります。

これが達成可能な最小値です。


入力例 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

出力例 3

-58

L,R,A_i は負であることがあります。

Score : 400 points

Problem Statement

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

You will perform the following consecutive operations just once:

  • Choose an integer x (0\leq x \leq N). If x is 0, do nothing. If x is 1 or greater, replace each of A_1,A_2,\ldots,A_x with L.

  • Choose an integer y (0\leq y \leq N). If y is 0, do nothing. If y is 1 or greater, replace each of A_{N},A_{N-1},\ldots,A_{N-y+1} with R.

Print the minimum possible sum of the elements of A after the operations.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • -10^9 \leq L, R\leq 10^9
  • -10^9 \leq A_i\leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N L R
A_1 A_2 \ldots A_N

Output

Print the answer.


Sample Input 1

5 4 3
5 5 0 6 3

Sample Output 1

14

If you choose x=2 and y=2, you will get A = (4,4,0,3,3), for the sum of 14, which is the minimum sum achievable.


Sample Input 2

4 10 10
1 2 3 4

Sample Output 2

10

If you choose x=0 and y=0, you will get A = (1,2,3,4), for the sum of 10, which is the minimum sum achievable.


Sample Input 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

Sample Output 3

-58

L, R, and A_i may be negative.

H - Somen Nagashi

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

そうめん流しのイベントに N 人の人が集まりました。人は一列に並んでおり、先頭から順に 1 から N の番号がついています。

そうめん流しでは次の出来事が M 回起こります。

  • 時刻 T_i に 量 W_i のそうめんを流す。列の先頭にいる人がその全てを得る(誰も列に並んでいない場合は、誰もそのそうめんを得ない)。その人はいったん列から外れ、時刻 T_i+S_i に列の元の位置に戻ってくる。

時刻 X に列に戻ってくる人は、時刻 X には列に並んでいるとみなします。

M 回の出来事が全て行われたあと、それぞれの人が合計でどれだけそうめんを得ることができたか答えてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 0 <T_1 <\ldots < T_M \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 1 \leq W_i \leq 10^9
  • 入力は全て整数

入力

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

N M
T_1 W_1 S_1
\vdots
T_M W_M S_M

出力

N 行出力せよ。 i 行目には人 i が得たそうめんの量を出力せよ。


入力例 1

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

出力例 1

101
10
1000

次のように進行します。

  • 時刻 1 に量 1 のそうめんが流される。列には人 1,2,3 が並んでおり、先頭の人 1 がそうめんを得て列から外れる。
  • 時刻 2 に量 10 のそうめんが流される。列には人 2,3 が並んでおり、先頭の人 2 がそうめんを得て列から外れる。
  • 時刻 4 に人 1 が列に戻ってくる。
  • 時刻 4 に量 100 のそうめんが流される。列には人 1,3 が並んでおり、先頭の人 1 がそうめんを得て列から外れる。
  • 時刻 10 に量 1000 のそうめんが流される。列には人 3 が並んでおり、先頭の人 3 がそうめんを得て列から外れる。
  • 時刻 100 に量 1000000000 のそうめんが流される。列には誰も並んでいないため、誰もこのそうめんを得ない。
  • 時刻 102 に人 2 が列に戻ってくる。
  • 時刻 10004 に人 1 が列に戻ってくる。
  • 時刻 1000000010 に人 3 が列に戻ってくる。

それぞれの人が得たそうめんの量の合計は、101,10,1000 です。


入力例 2

3 1
1 1 1

出力例 2

1
0
0

入力例 3

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

出力例 3

15

Score : 475 points

Problem Statement

There are N people gathered for an event called Flowing Noodles. The people are lined up in a row, numbered 1 to N in order from front to back.

During the event, the following occurrence happens M times:

  • At time T_i, a quantity W_i of noodles is flown down. The person at the front of the row gets all of it (if no one is in the row, no one gets it). That person then steps out of the row and returns to their original position in the row at time T_i+S_i.

A person who returns to the row at time X is considered to be in the row at time X.

After all the M occurrences, report the total amount of noodles each person has got.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 0 <T_1 <\ldots < T_M \leq 10^9
  • 1 \leq S_i \leq 10^9
  • 1 \leq W_i \leq 10^9
  • All input values are integers.

Input

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

N M
T_1 W_1 S_1
\vdots
T_M W_M S_M

Output

Print N lines. The i-th line should contain the amount of noodles person i has got.


Sample Input 1

3 5
1 1 3
2 10 100
4 100 10000
10 1000 1000000000
100 1000000000 1

Sample Output 1

101
10
1000

The event proceeds as follows:

  • At time 1, a quantity 1 of noodles is flown down. People 1, 2, and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
  • At time 2, a quantity 10 of noodles is flown down. People 2 and 3 are in the row, and the person at the front, person 2, gets the noodles and steps out of the row.
  • At time 4, person 1 returns to the row.
  • At time 4, a quantity 100 of noodles is flown down. People 1 and 3 are in the row, and the person at the front, person 1, gets the noodles and steps out of the row.
  • At time 10, a quantity 1000 of noodles is flown down. Only person 3 is in the row, and the person at the front, person 3, gets the noodles and steps out of the row.
  • At time 100, a quantity 1000000000 of noodles is flown down. No one is in the row, so no one gets these noodles.
  • At time 102, person 2 returns to the row.
  • At time 10004, person 1 returns to the row.
  • At time 1000000010, person 3 returns to the row.

The total amounts of noodles people 1, 2, and 3 have got are 101, 10, and 1000, respectively.


Sample Input 2

3 1
1 1 1

Sample Output 2

1
0
0

Sample Input 3

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

Sample Output 3

15
I - Two Sequence Queries

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 550 点

問題文

長さ N の数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。
Q 個のクエリが与えられるので、順に処理してください。

クエリは次の 3 種類です。

  • 1 l r x : A_l, A_{l+1}, \ldots, A_r に x を加える。
  • 2 l r x : B_l, B_{l+1}, \ldots, B_r に x を加える。
  • 3 l r : \displaystyle\sum_{i=l}^r (A_i\times B_i) を 998244353 で割った余りを出力する。

制約

  • 1\leq N,Q\leq 2\times 10^5
  • 0\leq A_i,B_i\leq 10^9
  • 1\leq l\leq r\leq N
  • 1\leq x\leq 10^9
  • 入力はすべて整数
  • 3 種類目のクエリが 1 つ以上存在する。

入力

入力は以下の形式で標準入力から与えられる。ここで、\mathrm{query}_i (1\leq i\leq Q) は i 番目に処理するクエリである。

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリは以下のいずれかの形式で与えられる。

1 l r x
2 l r x
3 l r

出力

3 種類目のクエリが K 個あるとき、K 行出力せよ。
i 行目 (1\leq i\leq K) には、i 個目の 3 種類目のクエリに対する出力を出力せよ。


入力例 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

出力例 1

16
25
84

最初、A=(1,3,5,6,8), B=(3,1,2,1,2) です。クエリは次の順で処理されます。

  • 1 個目のクエリでは (1\times 3)+(3\times 1)+(5\times 2)=16 を 998244353 で割った余りである 16 を出力します。
  • 2 個目のクエリでは A_2,A_3,A_4,A_5 に 3 を加えます。A=(1,6,8,9,11) となります。
  • 3 個目のクエリでは (1\times 3)+(6\times 1)+(8\times 2)=25 を 998244353 で割った余りである 25 を出力します。
  • 4 個目のクエリでは A_1,A_2,A_3 に 1 を加えます。A=(2,7,9,9,11) となります。
  • 5 個目のクエリでは B_5 に 2 を加えます。B=(3,1,2,1,4) となります。
  • 6 個目のクエリでは (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 を 998244353 で割った余りである 84 を出力します。

よって、1, 2, 3 行目にはそれぞれ 16, 25, 84 を出力します。


入力例 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

出力例 2

716070898
151723988

3 種類目のクエリでは 998244353 で割った余りを出力することに注意してください。

Score : 550 points

Problem Statement

You are given sequences of length N, A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You are also given Q queries to process in order.

There are three types of queries:

  • 1 l r x : Add x to each of A_l, A_{l+1}, \ldots, A_r.
  • 2 l r x : Add x to each of B_l, B_{l+1}, \ldots, B_r.
  • 3 l r : Print the remainder of \displaystyle\sum_{i=l}^r (A_i\times B_i) when divided by 998244353.

Constraints

  • 1\leq N,Q\leq 2\times 10^5
  • 0\leq A_i,B_i\leq 10^9
  • 1\leq l\leq r\leq N
  • 1\leq x\leq 10^9
  • All input values are integers.
  • There is at least one query of the third type.

Input

The input is given from Standard Input in the following format. Here, \mathrm{query}_i (1\leq i\leq Q) is the i-th query to be processed.

N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in one of the following formats:

1 l r x
2 l r x
3 l r

Output

If there are K queries of the third type, print K lines.
The i-th line (1\leq i\leq K) should contain the output for the i-th query of the third type.


Sample Input 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

Sample Output 1

16
25
84

Initially, A=(1,3,5,6,8) and B=(3,1,2,1,2). The queries are processed in the following order:

  • For the first query, print (1\times 3)+(3\times 1)+(5\times 2)=16 modulo 998244353, which is 16.
  • For the second query, add 3 to A_2,A_3,A_4,A_5. Now A=(1,6,8,9,11).
  • For the third query, print (1\times 3)+(6\times 1)+(8\times 2)=25 modulo 998244353, which is 25.
  • For the fourth query, add 1 to A_1,A_2,A_3. Now A=(2,7,9,9,11).
  • For the fifth query, add 2 to B_5. Now B=(3,1,2,1,4).
  • For the sixth query, print (2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84 modulo 998244353, which is 84.

Thus, the first, second, and third lines should contain 16, 25, and 84, respectively.


Sample Input 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

Sample Output 2

716070898
151723988

Make sure to print the sum modulo 998244353 for the third type of query.