AtCoder Daily Training ALL 2026/11/12 18:00start

A - Sequence of Strings

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

配点 : 100 点

問題文

N 個の文字列 S_1,S_2,\ldots,S_N がこの順番で与えられます。

S_N,S_{N-1},\ldots,S_1 の順番で出力してください。

制約

1\leq N \leq 10
N は整数
S_i は英小文字、英大文字、数字からなる長さ 1 以上 10 以下の文字列

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 行出力せよ。 i\ (1\leq i \leq N) 行目には、S_{N+1-i} を出力せよ。

入力例 1

3
Takahashi
Aoki
Snuke

出力例 1

Snuke
Aoki
Takahashi

N=3、S_1= Takahashi、S_2= Aoki、S_3= Snuke です。

よって、Snuke、Aoki、Takahashi の順で出力します。

入力例 2

4
2023
Year
New
Happy

出力例 2

Happy
New
Year
2023

与えられる文字列が数字を含むこともあります。

Score : 100 points

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N in this order.

Print S_N,S_{N-1},\ldots,S_1 in this order.

Constraints

1\leq N \leq 10
N is an integer.
S_i is a string of length between 1 and 10, inclusive, consisting of lowercase English letters, uppercase English letters, and digits.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print N lines. The i-th (1\leq i \leq N) line should contain S_{N+1-i}.

Sample Input 1

3
Takahashi
Aoki
Snuke

Sample Output 1

Snuke
Aoki
Takahashi

We have N=3, S_1= Takahashi, S_2= Aoki, and S_3= Snuke.

Thus, you should print Snuke, Aoki, and Takahashi in this order.

Sample Input 2

4
2023
Year
New
Happy

Sample Output 2

Happy
New
Year
2023

The given strings may contain digits.

B - Water Pressure

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

配点 : 100 点

問題文

水圧は水深のみに依存し、水深 x [m] の場所では \dfrac{x}{100} [MPa] になるものとします。

水深 D [m] の場所の水圧は何 [MPa] ですか？

制約

1 \leq D \leq 10000
D は整数である。

入力

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

出力

答えを出力せよ。想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。

入力例 1

出力例 1

水深 1000 [m] の場所の水圧は 10 [MPa] です。10.0 や 9.999999 などを出力しても正解となります。

入力例 2

出力例 2

0.5

入力例 3

出力例 3

31.41

Score : 100 points

Problem Statement

Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.

What is the water pressure in megapascals at a depth of D meters?

Constraints

1 \leq D \leq 10000
D is an integer.

Input

Input is given from Standard Input in the following format:

Output

Print the answer. Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-3}.

Sample Input 1

Sample Output 1

The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.

Sample Input 2

Sample Output 2

0.5

Sample Input 3

Sample Output 3

31.41

C - Line Sensor

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

配点 : 200 点

問題文

縦 H マス、横 W マスのグリッドがあります。上から i 行目、左から j 列目のマスを (i,j) と表します。
各マスの状態は文字 C_{i,j} で表されます。C_{i,j} が . ならば (i, j) には何も置かれておらず、 # ならば箱が 1 個置かれています。

1 \leq j \leq W を満たす整数 j に対して、整数 X_j を次のように定義します。

j 列目に置かれている箱の個数。言い換えると、C_{i,j} が # であるような整数 i の個数。

X_1, X_2, \dots, X_W をすべて求めてください。

制約

1 \leq H \leq 1000
1 \leq W \leq 1000
H, W は整数
C_{i, j} は . または #

入力

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

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}

出力

X_1, X_2, \dots, X_W を以下の形式に従って出力せよ。

X_1 X_2 \dots X_W

入力例 1

3 4
#..#
.#.#
.#.#

出力例 1

1 2 0 3

1 列目の箱が置かれているマスは (1, 1) の 1 ヵ所です。よって X_1 = 1 です。
2 列目の箱が置かれているマスは (2, 2), (3, 2) の 2 ヵ所です。よって X_2 = 2 です。
3 列目の箱が置かれているマスは存在しません。よって X_3 = 0 です。
4 列目の箱が置かれているマスは (1, 4), (2, 4), (3, 4) の 3 ヵ所です。よって X_4 = 3 です。
よって (X_1, X_2, X_3, X_4) = (1, 2, 0, 3) が答えとなります。

入力例 2

3 7
.......
.......
.......

出力例 2

0 0 0 0 0 0 0

箱が置かれているマスが存在しない場合もあります。

入力例 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

出力例 3

2 7 4

入力例 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

出力例 4

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

Score : 200 points

Problem Statement

There is a grid with H rows from top to bottom and W columns from left to right. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
The squares are described by characters C_{i,j}. If C_{i,j} is ., (i, j) is empty; if it is #, (i, j) contains a box.

For integers j satisfying 1 \leq j \leq W, let the integer X_j defined as follows.

X_j is the number of boxes in the j-th column. In other words, X_j is the number of integers i such that C_{i,j} is #.

Find all of X_1, X_2, \dots, X_W.

Constraints

1 \leq H \leq 1000
1 \leq W \leq 1000
H and W are integers.
C_{i, j} is . or #.

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 X_1, X_2, \dots, X_W in the following format:

X_1 X_2 \dots X_W

Sample Input 1

3 4
#..#
.#.#
.#.#

Sample Output 1

1 2 0 3

In the 1-st column, one square, (1, 1), contains a box. Thus, X_1 = 1.
In the 2-nd column, two squares, (2, 2) and (3, 2), contain a box. Thus, X_2 = 2.
In the 3-rd column, no squares contain a box. Thus, X_3 = 0.
In the 4-th column, three squares, (1, 4), (2, 4), and (3, 4), contain a box. Thus, X_4 = 3.
Therefore, the answer is (X_1, X_2, X_3, X_4) = (1, 2, 0, 3).

Sample Input 2

3 7
.......
.......
.......

Sample Output 2

0 0 0 0 0 0 0

There may be no square that contains a box.

Sample Input 3

8 3
.#.
###
.#.
.#.
.##
..#
##.
.##

Sample Output 3

2 7 4

Sample Input 4

5 47
.#..#..#####..#...#..#####..#...#...###...#####
.#.#...#.......#.#...#......##..#..#...#..#....
.##....#####....#....#####..#.#.#..#......#####
.#.#...#........#....#......#..##..#...#..#....
.#..#..#####....#....#####..#...#...###...#####

Sample Output 4

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

D - Enlarged Checker Board

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

配点 : 200 点

問題文

縦 A 行、横 B 列のマスからなるタイルを縦 N 行、横 N 列に並べてできた、縦 (A\times N) 行、横 (B\times N) 列のマス目 X があります。
1\leq i,j \leq N について、上から i 行目、左から j 列目のタイルをタイル (i,j) とします。

X の各マスは以下のように塗られています。

各タイルは白いタイルまたは黒いタイルである。
白いタイルのすべてのマスは白で塗られ、黒いタイルのすべてのマスは黒で塗られている。
タイル (1,1) は白いタイルである。
辺で隣接する 2 つのタイルは異なる色のタイルである。ただし、タイル (a,b) とタイル (c,d) が辺で隣接するとは、|a-c|+|b-d|=1 ( |x| を x の絶対値とする)であることを言う。

マス目 X を出力の形式に従って出力してください。

制約

1 \leq N,A,B \leq 10
入力は全て整数

入力

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

N A B

出力

次の条件をみたす (A\times N) 個の文字列 S_1,\ldots,S_{A\times N} を改行区切りで出力せよ。

S_1,\ldots,S_{A\times N} はそれぞれ長さ (B\times N) の . または # からなる文字列である。
各 i,j (1 \leq i \leq A\times N,1 \leq j \leq B\times N) に対し、マス目 X の上から i 行目かつ左から j 列目のマスが白で塗られているならば S_i の j 文字目は .であり、黒く塗られているならば # である。

入力例 1

4 3 2

出力例 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

入力例 2

5 1 5

出力例 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

入力例 3

4 4 1

出力例 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

入力例 4

1 4 4

出力例 4

....
....
....
....

Score : 200 points

Problem Statement

Tiles are aligned in N horizontal rows and N vertical columns. Each tile has a grid with A horizontal rows and B vertical columns. On the whole, the tiles form a grid X with (A\times N) horizontal rows and (B\times N) vertical columns.
For 1\leq i,j \leq N, Tile (i,j) denotes the tile at the i-th row from the top and the j-th column from the left.

Each square of X is painted as follows.

Each tile is either a white tile or a black tile.
Every square in a white tile is painted white; every square in a black tile is painted black.
Tile (1,1) is a white tile.
Two tiles sharing a side have different colors. Here, Tile (a,b) and Tile (c,d) are said to be sharing a side if and only if |a-c|+|b-d|=1 (where |x| denotes the absolute value of x).

Print the grid X in the format specified in the Output section.

Constraints

1 \leq N,A,B \leq 10
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N A B

Output

Print (A\times N) strings S_1,\ldots,S_{A\times N} that satisfy the following condition, with newlines in between.

Each of S_1,\ldots,S_{A\times N} is a string of length (B\times N) consisting of . and #.
For each i and j (1 \leq i \leq A\times N,1 \leq j \leq B\times N), the j-th character of S_i is . if the square at the i-th row from the top and j-th column from the left in grid X is painted white; the character is # if the square is painted black.

Sample Input 1

4 3 2

Sample Output 1

..##..##
..##..##
..##..##
##..##..
##..##..
##..##..
..##..##
..##..##
..##..##
##..##..
##..##..
##..##..

Sample Input 2

5 1 5

Sample Output 2

.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....
#####.....#####.....#####
.....#####.....#####.....

Sample Input 3

4 4 1

Sample Output 3

.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.
.#.#
.#.#
.#.#
.#.#
#.#.
#.#.
#.#.
#.#.

Sample Input 4

1 4 4

Sample Output 4

....
....
....
....

E - Not Covered Points

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

配点 : 300 点

問題文

2 次元平面上に点 1 から点 N までの N 個の点があります。点 i (1\le i\le N) の座標は (X_i,Y_i) です。ここで、X,Y はそれぞれ (1,2,\ldots,N) の順列であることが保証されます。

左下の頂点を (0,0) 、右上の頂点を (X_i,Y_i) とする x 軸に平行な辺と y 軸に平行な辺のみからなる長方形の内部（辺上を含まない）に点 1 から点 N までの N 個の点をどれも含まないような i の個数を求めてください。

制約

1\le N\le 3\times 10^5
1\le X_i,Y_i\le N
X,Y はそれぞれ (1,2,\ldots,N) の順列
入力される値は全て整数

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを出力せよ。

入力例 1

出力例 1

i=1,2 の 2 つが条件を満たします。

i=3 の場合、左下を (0,0) 、右上を (3,2) とする x 軸に平行な辺を持つ長方形の内部（辺上を含まない）に点 1 を含みます。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

There are N points numbered 1 through N on a two-dimensional plane. Point i (1\le i\le N) has coordinates (X_i,Y_i). Here, it is guaranteed that X and Y are each permutations of (1,2,\ldots,N).

Find the number of values of i such that the interior (not including the boundary) of the rectangle with sides parallel to the x-axis and y-axis, with lower-left vertex (0,0) and upper-right vertex (X_i,Y_i), contains none of the N points numbered 1 through N.

Constraints

1\le N\le 3\times 10^5
1\le X_i,Y_i\le N
X and Y are each permutations of (1,2,\ldots,N).
All input values are integers.

Input

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Output the answer.

Sample Input 1

Sample Output 1

The two values i=1,2 satisfy the condition.

For i=3, the interior (not including the boundary) of the rectangle with sides parallel to the x-axis, with lower-left vertex (0,0) and upper-right vertex (3,2), contains point 1.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

F - Shortest Duplicate Subarray

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

配点 : 300 点

問題文

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

A の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定してください。存在するならばそのようなもののうち最も短いものの長さを求めてください。

制約

1\leq N\leq 2\times 10^5
1\leq A_i\leq 10^6 (1\leq i\leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \dots A_N

出力

問題文中の条件を満たす連続部分列が存在しないならば -1 と出力せよ。存在するならば、そのようなもののうち最も短いものの長さを出力せよ。

入力例 1

5
3 9 5 3 1

出力例 1

(3,9,5,3) と (3,9,5,3,1) が条件を満たします。短いのは (3,9,5,3) で、その長さは 4 です。

入力例 2

4
2 5 3 1

出力例 2

-1

条件を満たす連続部分列は存在しません。

入力例 3

10
1 1 2 3 5 8 13 21 34 55

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N and an integer sequence A = (A_1,A_2,\dots,A_N) of length N.

Determine whether there exists a non-empty (contiguous) subarray of A that has a repeated value, occurring multiple times in A. If such a subarray exists, find the length of the shortest such subarray.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^6 \ (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 \dots A_N

Output

If there is no (contiguous) subarray satisfying the condition in the problem statement, print -1. Otherwise, print the length of the shortest such subarray.

Sample Input 1

5
3 9 5 3 1

Sample Output 1

(3,9,5,3) and (3,9,5,3,1) satisfy the condition. The shorter one is (3,9,5,3), which has length 4.

Sample Input 2

4
2 5 3 1

Sample Output 2

-1

There is no subarray that satisfies the condition.

Sample Input 3

10
1 1 2 3 5 8 13 21 34 55

Sample Output 3

G - String Rotation

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

配点 : 400 点

問題文

長さ N の英小文字からなる文字列 S=S_1S_2\dots S_N が与えられます。あなたは、S に対して以下の操作をちょうど 1 回行います。

S の長さ 1 以上の連続部分文字列を選んで、左に 1 だけ巡回シフトする。すなわち、整数 1 \leq \ell \leq r \leq N を選んで、S の r 文字目の右に S_\ell を挿入したのち、S の \ell 番目の文字を削除する。

操作後の S としてありえる文字列のうち、辞書順最小のものを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

1 \leq T \leq 10^5
1 \leq N \leq 10^5
S は英小文字からなる長さ N の文字列
T,N は整数
1 つの入力ファイルに含まれる N の総和は 10^5 以下

入力

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

各テストケース \mathrm{case}_i\;(1 \leq i \leq T) は以下の形式で与えられる。

N
S

出力

T 行出力せよ。i \; (1 \leq i \leq T) 行目には、\mathrm{case}_i に対する答えを出力せよ。

入力例 1

3
7
atcoder
1
x
5
snuke

出力例 1

acodert
x
nsuke

1 番目のテストケースでは、2 文字目から 7 文字目を巡回シフトして acodert とするのが辞書順最小です。
2 番目のテストケースでは、どのように操作しても x が得られます。
3 番目のテストケースでは、1 文字目から 2 文字目を巡回シフトして nsuke とするのが辞書順最小です。

Score : 400 points

Problem Statement

You are given a string S=S_1S_2\dots S_N of length N consisting of lowercase English letters. You will perform the following operation on S exactly once:

Choose a contiguous substring of S with length at least 1 and cyclically shift it to the left by 1. That is, choose integers 1 \leq \ell \leq r \leq N, insert S_\ell to the right of the r-th character of S, and then delete the \ell-th character of S.

Find the lexicographically smallest string among all possible strings that S can become after the operation.

You are given T test cases, so solve each of them.

Constraints

1 \leq T \leq 10^5
1 \leq N \leq 10^5
S is a string of length N consisting of lowercase English letters.
T and N are integers.
The sum of N over all test cases in a single input file is at most 10^5.

Input

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

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case \mathrm{case}_i\;(1 \leq i \leq T) is given in the following format:

N
S

Output

Output T lines. The i-th (1 \leq i \leq T) line should contain the answer for \mathrm{case}_i.

Sample Input 1

3
7
atcoder
1
x
5
snuke

Sample Output 1

acodert
x
nsuke

In the first test case, cyclically shifting from the 2nd to the 7th character gives acodert, which is lexicographically smallest.
In the second test case, no matter how you operate, you get x.
In the third test case, cyclically shifting from the 1st to the 2nd character gives nsuke, which is lexicographically smallest.

H - Christmas Color Grid 1

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

配点 : 450 点

問題文

この問題は問題 G と似た設定です。問題文の相違点を赤字で示します。

H 行 W 列のグリッドがあり、グリッドの各マスは赤色あるいは緑色に塗られています。

グリッドの上から i 行目、左から j 列目のマスをマス (i,j) と表記します。

マス (i,j) の色は文字 S_{i,j} で表され、S_{i,j} = . のときマス (i,j) は赤色、S_{i,j} = # のときマス (i,j) は緑色に塗られています。

グリッドにおいて、緑色に塗られたマスを頂点集合、隣り合った 2 つの緑色のマスを結ぶ辺全体を辺集合としたグラフにおける連結成分の個数を 緑の連結成分数 と呼びます。ただし、2 つのマス (x,y) と (x',y') が隣り合っているとは、|x-x'| + |y-y'| = 1 であることを指します。

赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えたとき、塗り替え後のグリッドの緑の連結成分数の期待値を \text{mod } 998244353 で出力してください。

「期待値を \text{mod } 998244353 で出力」とは

求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、 R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ 1 つ存在することが証明できます。この R を出力してください。

制約

1 \leq H,W \leq 1000
S_{i,j} = . または S_{i,j} = #
S_{i,j} = . なる (i,j) が存在する。

入力

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

出力

答えを出力せよ。

入力例 1

3 3
##.
#.#
#..

出力例 1

499122178

マス (1,3) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (2,2) を緑色に塗り替えたとき、緑の連結成分数は 1 となります。

マス (3,2) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

マス (3,3) を緑色に塗り替えたとき、緑の連結成分数は 2 となります。

よって、赤色に塗られたマスを一様ランダムに 1 つ選び、緑色に塗り替えた後の緑の連結成分数の期待値は (1+1+2+2)/4 = 3/2 となります。

入力例 2

4 5
..#..
.###.
#####
..#..

出力例 2

598946613

入力例 3

3 4
#...
.#.#
..##

出力例 3

285212675

Score : 450 points

Problem Statement

This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.

There is a grid with H rows and W columns, where each cell is painted red or green.

Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.

The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.

The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.

Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean?

It can be proved that the sought expected value is always rational. Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Constraints

1 \leq H,W \leq 1000
S_{i,j} = . or S_{i,j} = #.
There is at least one (i,j) such that S_{i,j} = ..

Input

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

H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.

If cell (2,2) is repainted green, the number of green connected components becomes 1.

If cell (3,2) is repainted green, the number of green connected components becomes 2.

If cell (3,3) is repainted green, the number of green connected components becomes 2.

Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

I - Email Scheduling Optimization

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

配点 : 525 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N),\;B=(B_1,B_2,\dots,B_N) が与えられます。
Q 個のクエリが与えられます。
各クエリは以下の 2 種類のいずれかです。

1 i x : A_i を x に変更する。
2 i x : B_i を x に変更する。

各クエリを処理するたびに、以下の問題の答えを求めてください。

高橋君は N 個の会社にメールを送り、それぞれの会社から返信をもらう必要があります。
j 個目の会社に送るメールを書くには A_j 分の時間を要し、送ってから B_j 分後に返信が届きます。
高橋君は時刻 0 からメールを書き始めます。
高橋君は N 通のメールを好きな順番で書くことができますが、2 通以上のメールを同時に書くことはできません。
高橋君がすべての返信を受け取り終える時刻としてあり得る最小値を求めてください。
ただし、メールを送るのにかかる時間は無視できるものとします。

制約

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
1 \leq A_j,B_j \leq 10^9
各クエリにおいて、1 \leq i \leq N
各クエリにおいて、1 \leq x \leq 10^9
入力される値はすべて整数

入力

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

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

各クエリ \mathrm{query}_q では、クエリの種類（1 か 2）と i と x がこの順に空白区切りで与えられる。
すなわち、各クエリは以下の 2 つの形式のいずれかである。

1 i x

2 i x

出力

答えを合計 Q 行で出力せよ。 q 行目には、q 番目のクエリを処理した後の問題の答えを出力せよ。

入力例 1

出力例 1

16
16
13

最初のクエリを行った後、A=(4,1,7), \; B=(4,6,7) です。
時刻 0 に会社 3 に送るメールを書き始め、時刻 7 に書き終えて会社 3 にメールを送ると、時刻 14 に返信を受け取ります。
時刻 7 に会社 2 に送るメールを書き始め、時刻 8 に書き終えて会社 2 にメールを送ると、時刻 14 に返信を受け取ります。
時刻 8 に会社 1 に送るメールを書き始め、時刻 12 に書き終えて会社 1 にメールを送ると、時刻 16 に返信を受け取ります。

Score : 525 points

Problem Statement

You are given length-N sequences of positive integers A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).
You are given Q queries.
Each query is of one of the following two types.

1 i x : Change A_i to x.
2 i x : Change B_i to x.

After processing each query, solve the following problem.

Takahashi needs to send an email to each of N companies and receive a reply from each of them.
Writing the email to send to the j-th company takes A_j minutes, and the reply arrives B_j minutes after it is sent.
He starts writing emails at time 0.
He can write the N emails in any order he likes, but he cannot write two or more emails simultaneously.
Find the minimum possible time at which he finishes receiving all of the replies.
Assume that the time taken to send emails is negligible.

Constraints

1 \leq N \leq 10^5
1 \leq Q \leq 10^5
1 \leq A_j,B_j \leq 10^9
In each query, 1 \leq i \leq N.
In each query, 1 \leq x \leq 10^9.
All input values are integers.

Input

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

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

For each query \mathrm{query}_q, the type of the query (1 or 2), i, and x are given in this order, separated by spaces.
That is, each query is given in one of the following two formats:

1 i x

2 i x

Output

Output the answers in a total of Q lines. The q-th line should contain the answer to the problem after processing the q-th query.

Sample Input 1

Sample Output 1

16
16
13

After processing the first query, A=(4,1,7) and B=(4,6,7).
If Takahashi starts writing the email to send to company 3 at time 0, finishes writing it at time 7, and sends it to company 3, he receives the reply at time 14.
If he starts writing the email to send to company 2 at time 7, finishes writing it at time 8, and sends it to company 2, he receives the reply at time 14.
If he starts writing the email to send to company 1 at time 8, finishes writing it at time 12, and sends it to company 1, he receives the reply at time 16.