Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
英小文字のみからなる文字列 S が与えられます。
S の各文字を英大文字に変換して得られる文字列 T を出力してください。
制約
- S は英小文字のみからなる、長さが 1 以上 100 以下の文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
T を出力せよ。
入力例 1
abc
出力例 1
ABC
abc
の各文字を英大文字に変換すると ABC
になります。
入力例 2
a
出力例 2
A
入力例 3
abcdefghjiklnmoqprstvuwxyz
出力例 3
ABCDEFGHJIKLNMOQPRSTVUWXYZ
Score : 100 points
Problem Statement
You are given a string S consisting of lowercase English letters.
Uppercase each character of S and print the resulting string T.
Constraints
- S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print T.
Sample Input 1
abc
Sample Output 1
ABC
Uppercase each character of abc
, and you have ABC
.
Sample Input 2
a
Sample Output 2
A
Sample Input 3
abcdefghjiklnmoqprstvuwxyz
Sample Output 3
ABCDEFGHJIKLNMOQPRSTVUWXYZ
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1 から N までの番号がついた N 人の選手がサッカーの試合をします。
選手が反則を犯したとき、その選手には イエローカード と レッドカード のどちらかが提示されます。
以下の条件のうち一方を満たした選手は 退場処分 と呼ばれるペナルティを受けます。
- イエローカードを累計 2 回提示される。
- レッドカードを提示される。
なお、退場処分を受けた選手にそれ以降カードが提示されることはありません。
あなたはこの試合を観戦します。はじめ、すべての選手はカードを 1 回も提示されていません。
Q 個のイベントが発生するので、イベントで聞かれる質問に正しく答えてください。
イベントは 3 種類あり、c x
(c は 1, 2, 3 のいずれか) という形式で入力から与えられます。イベントの説明は次の通りです。
1 x
: 選手 x にイエローカードが提示される。2 x
: 選手 x にレッドカードが提示される。3 x
: あなたは選手 x が退場処分を受けたかを質問される。選手 x が退場処分を受けていればYes
と、そうでなければNo
と答える。
制約
- 1 \leq N \leq 100
- 1 \leq Q \leq 100
- 全てのイベントにおいて 1 \leq x \leq N
- 3 種類目のイベントは少なくとも 1 個以上存在する
- すでに退場処分を受けた選手にカードが提示されることはない
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ただし、\text{event}_i は i 番目に発生するイベントを意味する。
N Q \text{event}_1 \text{event}_2 \vdots \text{event}_Q
イベントは次の 3 つのいずれかの形式で入力される。
1 x
2 x
3 x
出力
入力で与えられる 3 種類目のイベントの個数を X として、X 行出力せよ。
i 行目には、3 種類目のイベントのうち i 番目のもので聞かれる質問について、選手 x が退場処分を受けていれば Yes
を、そうでなければ No
を出力せよ。
入力例 1
3 9 3 1 3 2 1 2 2 1 3 1 3 2 1 2 3 2 3 3
出力例 1
No No Yes No Yes No
イベントを時系列順にすべて説明すると次の通りです。
1 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けていないので No
を出力します。
2 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No
を出力します。
3 番目のイベントでは、選手 2 にイエローカードが提示されます。
4 番目のイベントでは、選手 1 にレッドカードが提示されます。選手 1 は退場処分を受けます。
5 番目のイベントでは、あなたは選手 1 が退場処分を受けたかを質問されます。選手 1 は退場処分を受けたので Yes
を出力します。
6 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けていないので No
を出力します。
7 番目のイベントでは、選手 2 にイエローカードが提示されます。選手 2 は退場処分を受けます。
8 番目のイベントでは、あなたは選手 2 が退場処分を受けたかを質問されます。選手 2 は退場処分を受けたので Yes
を出力します。
9 番目のイベントでは、あなたは選手 3 が退場処分を受けたかを質問されます。選手 3 は退場処分を受けていないので No
を出力します。
Score : 200 points
Problem Statement
N players numbered 1 to N will play a soccer game.
When a player commits an offense, that player will receive a yellow card or a red card.
A player who satisfies one of the following conditions will be removed from the game.
- Accumulates two yellow cards.
- Receives a red card.
Once a player is removed, that player will no longer receive any cards.
You will watch this game. Initially, the players have not received any cards.
There will be Q events. Correctly answer the questions asked in the events.
There are three kinds of events, which are given in the format c x
from the input, where c is 1, 2, or 3. The events are as follows.
1 x
: Player x receives a yellow card.2 x
: Player x receives a red card.3 x
: You are asked whether player x has been removed from the game. AnswerYes
orNo
.
Constraints
- 1 \leq N \leq 100
- 1 \leq Q \leq 100
- 1 \leq x \leq N in all events.
- There is at least one event of the third kind.
- A player who has been removed will no longer receive any cards.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format, where \text{event}_i denotes the i-th event.
N Q \text{event}_1 \text{event}_2 \vdots \text{event}_Q
Each event is in one of the following formats:
1 x
2 x
3 x
Output
Print X lines, where X is the number of events of the third kind in the input.
The i-th line should contain Yes
if, for the i-th event of the third kind, player x has been removed from the game, and No
otherwise.
Sample Input 1
3 9 3 1 3 2 1 2 2 1 3 1 3 2 1 2 3 2 3 3
Sample Output 1
No No Yes No Yes No
Here are all the events in chronological order.
In the 1-st event, you are asked whether player 1 has been removed from the game. Player 1 has not been removed, so you should print No
.
In the 2-nd event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No
.
In the 3-rd event, player 2 receives a yellow card.
In the 4-th event, player 1 receives a red card and is removed from the game.
In the 5-th event, you are asked whether player 1 has been removed from the game. Player 1 has been removed, so you should print Yes
.
In the 6-th event, you are asked whether player 2 has been removed from the game. Player 2 has not been removed, so you should print No
.
In the 7-th event, player 2 receives a yellow card and is removed from the game.
In the 8-th event, you are asked whether player 2 has been removed from the game. Player 2 has been removed, so you should print Yes
.
In the 9-th event, you are asked whether player 3 has been removed from the game. Player 3 has not been removed, so you should print No
.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
正整数 N が与えられます。
正整数の組 (A,B,C,D) であって、AB + CD = N を満たすものの個数を求めてください。
なお、本問の制約の下、答えが 9 \times 10^{18} 以下であることが証明できます。
制約
- 2 \leq N \leq 2 \times 10^5
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを出力せよ。
入力例 1
4
出力例 1
8
(A,B,C,D) として以下の 8 個が考えられます。
- (A,B,C,D)=(1,1,1,3)
- (A,B,C,D)=(1,1,3,1)
- (A,B,C,D)=(1,2,1,2)
- (A,B,C,D)=(1,2,2,1)
- (A,B,C,D)=(1,3,1,1)
- (A,B,C,D)=(2,1,1,2)
- (A,B,C,D)=(2,1,2,1)
- (A,B,C,D)=(3,1,1,1)
入力例 2
292
出力例 2
10886
入力例 3
19876
出力例 3
2219958
Score : 300 points
Problem Statement
You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.
Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- N is an integer.
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
4
Sample Output 1
8
Here are the eight desired quadruples.
- (A,B,C,D)=(1,1,1,3)
- (A,B,C,D)=(1,1,3,1)
- (A,B,C,D)=(1,2,1,2)
- (A,B,C,D)=(1,2,2,1)
- (A,B,C,D)=(1,3,1,1)
- (A,B,C,D)=(2,1,1,2)
- (A,B,C,D)=(2,1,2,1)
- (A,B,C,D)=(3,1,1,1)
Sample Input 2
292
Sample Output 2
10886
Sample Input 3
19876
Sample Output 3
2219958
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
このグラフのすべての連結成分が次の条件を満たすかどうかを判定してください。
- その連結成分に含まれる頂点の個数と辺の本数が等しい。
注釈
無向グラフ とは、辺に向きの無いグラフのことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i \leq v_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 \vdots u_M v_M
出力
すべての連結成分が条件を満たすならば Yes
と、そうでなければ No
と出力せよ。
入力例 1
3 3 2 3 1 1 2 3
出力例 1
Yes
このグラフには頂点 1 のみからなる連結成分と頂点 2,3 からなる連結成分があります。
前者には 1 本の辺(辺 2 )が、後者には 2 本の辺(辺 1,3 )が含まれており、条件を満たします。
入力例 2
5 5 1 2 2 3 3 4 3 5 1 5
出力例 2
Yes
入力例 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
出力例 3
No
Score : 400 points
Problem Statement
You are given an undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Determine whether every connected component in this graph satisfies the following condition.
- The connected component has the same number of vertices and edges.
Notes
An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i \leq v_i \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 \vdots u_M v_M
Output
If every connected component satisfies the condition, print Yes
; otherwise, print No
.
Sample Input 1
3 3 2 3 1 1 2 3
Sample Output 1
Yes
The graph has a connected component formed from just vertex 1, and another formed from vertices 2 and 3.
The former has one edge (edge 2), and the latter has two edges (edges 1 and 3), satisfying the condition.
Sample Input 2
5 5 1 2 2 3 3 4 3 5 1 5
Sample Output 2
Yes
Sample Input 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
Sample Output 3
No
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純有向グラフが与えられます。辺 i は頂点 u_i から頂点 v_i への有向辺です。
また、あなたは次の操作を 0 回以上何度でも行えます。
- 相異なる頂点 x,y であって頂点 x から頂点 y への有向辺が存在しないようなものを選ぶ。そして、頂点 x から頂点 y への有向辺を追加する。
このグラフが次の条件を満たす状態にするために最小で何回操作を行う必要があるかを求めてください。
- 相異なる頂点 a,b,c すべてについて、頂点 a から頂点 b への有向辺と頂点 b から頂点 c への有向辺がともに存在するならば頂点 a から頂点 c への有向辺も存在する。
制約
- 3 \leq N \leq 2000
- 0 \leq M \leq 2000
- 1 \leq u_i ,v_i \leq N
- u_i \neq v_i
- i \neq j ならば (u_i,v_i) \neq (u_j,v_j)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
4 3 2 4 3 1 4 3
出力例 1
3
初め、一例として頂点 2,4,3 について、頂点 2 から頂点 4 への有向辺と頂点 4 から頂点 3 への有向辺がともに存在するにもかかわらず、頂点 2 から頂点 3 への有向辺は存在せず、条件を満たさない状態です。
そこで、以下の 3 本の有向辺を追加すると条件を満たす状態になります。
- 頂点 2 から頂点 3 への有向辺
- 頂点 2 から頂点 1 への有向辺
- 頂点 4 から頂点 1 への有向辺
一方、3 本未満の追加で条件を満たす状態には出来ないため、答えは 3 です。
入力例 2
292 0
出力例 2
0
入力例 3
5 8 1 2 2 1 1 3 3 1 1 4 4 1 1 5 5 1
出力例 3
12
Score : 500 points
Problem Statement
You are given a simple directed graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i is a directed edge from vertex u_i to vertex v_i.
You may perform the following operation zero or more times.
- Choose distinct vertices x and y such that there is no directed edge from vertex x to vertex y, and add a directed edge from vertex x to vertex y.
Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.
- For every triple of distinct vertices a, b, and c, if there are directed edges from vertex a to vertex b and from vertex b to vertex c, there is also a directed edge from vertex a to vertex c.
Constraints
- 3 \leq N \leq 2000
- 0 \leq M \leq 2000
- 1 \leq u_i ,v_i \leq N
- u_i \neq v_i
- (u_i,v_i) \neq (u_j,v_j) if i \neq j.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 \vdots u_M v_M
Output
Print the answer.
Sample Input 1
4 3 2 4 3 1 4 3
Sample Output 1
3
Initially, the condition is not satisfied because, for instance, for vertices 2, 4, and 3, there are directed edges from vertex 2 to vertex 4 and from vertex 4 to vertex 3, but not from vertex 2 to vertex 3.
You can make the graph satisfy the condition by adding the following three directed edges:
- one from vertex 2 to vertex 3,
- one from vertex 2 to vertex 1, and
- one from vertex 4 to vertex 1.
On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 3.
Sample Input 2
292 0
Sample Output 2
0
Sample Input 3
5 8 1 2 2 1 1 3 3 1 1 4 4 1 1 5 5 1
Sample Output 3
12
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
縦の長さが A、横の長さが B の長方形の内部に描ける正三角形の一辺の長さの最大値を求めてください。
制約
- 1 \leq A,B \leq 1000
- A,B は整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解として扱われる。
入力例 1
1 1
出力例 1
1.03527618041008295791
下図のように描くのが最適で、一辺の長さが \sqrt{6} - \sqrt{2} になります。
なお、この出力例の値は \sqrt{6}- \sqrt{2} と厳密には一致しませんが、誤差が 10^{-9} 以下なので正解として扱われます。
Score : 500 points
Problem Statement
Find the maximum side length of a regular triangle that can be drawn within a rectangle whose side lengths are A and B.
Constraints
- 1 \leq A,B \leq 1000
- A and B are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Your output is considered correct if the absolute or relative error from the true answer is at most 10^{-9}.
Sample Input 1
1 1
Sample Output 1
1.03527618041008295791
The following figure shows an optimal drawing, with the side length of \sqrt{6} - \sqrt{2}.
Note that the sample output does not strictly match \sqrt{6}- \sqrt{2}, but the error is within 10^{-9}, so it is considered correct.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
数字( 0123456789
)と ?
からなる長さ M の文字列の列 S_1,\ldots,S_N が与えられます。
?
を独立に数字に置き換える方法は 10^q(q は S_1,\ldots,S_N に含まれる ?
の個数の合計) 通りありますが、そのうち置き換え後の文字列をそれぞれ整数値とみなしたときに S_1\lt S_2 \lt \ldots \lt S_N が成り立つようなものが何通りあるかを 998244353 で割った余りを求めてください。
なお、?
を置き換えた後の S_i は先頭に 1 個以上の 0
が連続していても構いません。例えば、0000000292
を整数値とみなすと 292 となります。
制約
- 2 \leq N \leq 40
- 1 \leq M \leq 40
- N,M は整数
- S_i は数字と
?
からなる長さ M の文字列
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 \vdots S_N
出力
答えを出力せよ。
入力例 1
3 2 ?0 ?? 05
出力例 1
4
条件を満たす置き換え方は以下の 4 通りです。
- S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,1
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,2
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,3
に置き換える。 - S_1 の 1 文字目の
?
を0
に、S_2 の 1,2 文字目の?
をそれぞれ0
,4
に置き換える。
入力例 2
2 1 0 0
出力例 2
0
入力例 3
10 10 1?22??37?4 1??8?0??49 3?02??8044 51?4?8?7?? 5?9?20???2 68?7?6?800 ?3??2???23 ?442312158 ??2??921?8 ????5?96??
出力例 3
137811792
答えを 998244353 で割った余りを求めてください。
Score : 600 points
Problem Statement
You are given a sequence S_1,\ldots,S_N of length-M strings consisting of digits (0123456789
) and ?
.
There are 10^q ways to replace the occurrences of ?
with digits independently, where q is the total number of ?
in S_1,\ldots,S_N. Among them, how many satisfy S_1\lt S_2 \lt \ldots \lt S_N when the resulting strings are seen as integers? Find this count modulo 998244353.
The resulting strings may have leading zeros. For instance, 0000000292
is seen as 292.
Constraints
- 2 \leq N \leq 40
- 1 \leq M \leq 40
- N and M are integers.
- S_i is a string of length M consisting of digits and
?
.
Input
The input is given from Standard Input in the following format:
N M S_1 \vdots S_N
Output
Print the answer.
Sample Input 1
3 2 ?0 ?? 05
Sample Output 1
4
Here are the four desired replacements.
- Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and1
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and2
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and3
, respectively. - Replace the first character of S_1 with
0
, and the first and second characters of S_2 with0
and4
, respectively.
Sample Input 2
2 1 0 0
Sample Output 2
0
Sample Input 3
10 10 1?22??37?4 1??8?0??49 3?02??8044 51?4?8?7?? 5?9?20???2 68?7?6?800 ?3??2???23 ?442312158 ??2??921?8 ????5?96??
Sample Output 3
137811792
Find the count modulo 998244353.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
あなたは N 個のコンテストに参加します。コンテストが開催される順にコンテスト 1, コンテスト 2, \dots コンテスト N と呼びます。
各コンテストに参加すると、コンテストごとに パフォーマンス という値が与えられます。コンテスト i で与えられるパフォーマンスを P_i とします。
また、あなたは レーティング という値を持っています。レーティングはコンテストでのパフォーマンスによって変化する値です。コンテストに参加する前のレーティングの値は 0 で、コンテスト n に出た後のレーティングの値は \frac{1}{n} \left(\sum_{i=1}^n P_i \right) に変化します。
ただし、あなたのレーティングが一度 B 以上 になると、それ以降はコンテストに参加してもレーティングは変動しなくなります。
あなたはコンテストに出る前に、それぞれのコンテストで得られるパフォーマンスを予測することにしました。はじめ、コンテスト i のパフォーマンスの予測値を a_i とします。クエリが Q 個与えられるので入力される順にすべて処理してください。
各クエリでは 2 個の整数 c, x が与えられます。あなたは、まずコンテスト c のパフォーマンスの予測値を x に変更します。(この変更は永続的です。) そして、あなたが N 個のコンテスト全てで現在の予測値通りのパフォーマンスを得られた場合の、全てのコンテストに参加した後のレーティングの値を答えてください。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq B \leq 10^9
- 1 \leq Q \leq 10^5
- 0 \leq a_i \leq 10^9
- 1 \leq c \leq N
- 0 \leq x \leq 10^9
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。ただし、c_i, x_i は i 番目のクエリで与えられる c, x を意味する。
N B Q a_1 a_2 \dots a_N c_1 x_1 c_2 x_2 \vdots c_Q x_Q
出力
Q 行出力せよ。i 行目には i 番目のクエリに対する答えを出力せよ。
なお、真の値との絶対誤差または相対誤差が 10^{-9} 以下であれば正解として扱われる。
入力例 1
5 6 7 5 1 9 3 8 4 9 2 10 1 0 3 0 3 30 5 100 1 100
出力例 1
6.000000000000000 7.500000000000000 6.333333333333333 5.400000000000000 13.333333333333334 13.333333333333334 100.000000000000000
はじめ、(a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8) です。
1 番目のクエリによって a_4 が 9 に変更されて (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8) となります。
このとき、コンテスト i でパフォーマンス a_i を取った場合のあなたのレーティングの推移は次の通りです。
- はじめ、レーティングは 0 です。
- コンテスト 1 が終了した時点でレーティングは 5 / 1 = 5 に変化します。
- コンテスト 2 が終了した時点でレーティングは (5 + 1) / 2 = 3 に変化します。
- コンテスト 3 が終了した時点でレーティングは (5 + 1 + 9) / 3 = 5 に変化します。
- コンテスト 4 が終了した時点でレーティングは (5 + 1 + 9 + 9) / 4 = 6 に変化します。
- 以降、レーティングの値は変化しません。なぜならば、4 番目のコンテストが終了した時点でレーティングが B 以上の値になっているからです。
よって、全てのコンテストが終了した時点でのレーティングは 6 なので、1 行目にはこれを出力します。
Score : 600 points
Problem Statement
You will participate in N contests, numbered 1 to N in chronological order.
A participant in each contest will be given a value called performance for that contest. Let P_i be the performance for contest i.
Additionally, you have a value called rating, which changes according to the performances in contests. The initial rating is 0, and the rating after contest n is \frac{1}{n} \left(\sum_{i=1}^n P_i \right).
However, once your rating is B or higher, later contests will not affect your rating.
Before the contests, you have decided to estimate your performance in each contest. Let a_i be the initial estimate of your performance in contest i. Process Q queries in the order they are given.
In each query, you are given two integers c and x. First, change the estimate of your performance in contest c to x. (This change is persistent.) Then, assuming that you get the estimated performances in all N contests, print your final rating after the contests.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq B \leq 10^9
- 1 \leq Q \leq 10^5
- 0 \leq a_i \leq 10^9
- 1 \leq c \leq N
- 0 \leq x \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format, where c_i and x_i are the c and x for the i-th query:
N B Q a_1 a_2 \dots a_N c_1 x_1 c_2 x_2 \vdots c_Q x_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Your output is considered correct if the absolute or relative error from the true answer is at most 10^{-9}.
Sample Input 1
5 6 7 5 1 9 3 8 4 9 2 10 1 0 3 0 3 30 5 100 1 100
Sample Output 1
6.000000000000000 7.500000000000000 6.333333333333333 5.400000000000000 13.333333333333334 13.333333333333334 100.000000000000000
Initially, (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 3, 8).
The first query changes a_4 to 9, making (a_1, a_2, a_3, a_4, a_5) = (5, 1, 9, 9, 8).
Here, assuming that your performance in contest i is a_i, your rating will change as follows.
- Initially, your rating is 0.
- After contest 1, your rating will be 5 / 1 = 5.
- After contest 2, your rating will be (5 + 1) / 2 = 3.
- After contest 3, your rating will be (5 + 1 + 9) / 3 = 5.
- After contest 4, your rating will be (5 + 1 + 9 + 9) / 4 = 6.
- Your rating will no longer change, because your rating after contest 4 is not less than B.
Thus, your final rating after the contests is 6, which should be printed in the first line.