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.

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

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. Answer Yes or No.

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.

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.

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.

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

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.

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

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.

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

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.

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.

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 ?.

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 with 0 and 1, respectively.
• Replace the first character of S_1 with 0, and the first and second characters of S_2 with 0 and 2, respectively.
• Replace the first character of S_1 with 0, and the first and second characters of S_2 with 0 and 3, respectively.
• Replace the first character of S_1 with 0, and the first and second characters of S_2 with 0 and 4, 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.

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.

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.