Problem Statement

The number pi to the 100-th decimal place is

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679.

You are given an integer N between 1 and 100, inclusive.

Print the value of pi to the N-th decimal place.

More precisely, truncate the value of pi to N decimal places and print the result without removing the trailing 0s.

Constraints

• 1\leq N\leq 100
• N is an integer.

Sample Input 1

2

Sample Output 1

3.14

Truncating the value of pi to 2 decimal places results in 3.14. Thus, you should print 3.14.

Sample Input 2

32

Sample Output 2

3.14159265358979323846264338327950

Do not remove the trailing 0s.

Sample Input 3

100

Sample Output 3

3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

• Person i has bet on X.
• For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

• 1 \leq N \leq 100
• 1 \leq C_i \leq 37
• 0 \leq A_{i, j} \leq 36
• A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
• 0 \leq X \leq 36
• All input values are integers.

Sample Input 1

4
3
7 19 20
4
4 19 24 0
2
26 10
3
19 31 24
19

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

3
1
1
1
2
1
3
0

Sample Output 2

0

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

• Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq M
• N, M, and C_i are all integers.
• S is a string of length N consisting of lowercase English letters.
• For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

• For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
• For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
• For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

Problem Statement

You are given a string S of length N consisting of uppercase and lowercase English letters.

Let us perform Q operations on the string S. The i-th operation (1\leq i\leq Q) is represented by a tuple (t _ i,x _ i,c _ i) of two integers and one character, as follows.

• If t _ i=1, change the x _ i-th character of S to c _ i.
• If t _ i=2, convert all uppercase letters in S to lowercase (do not use x _ i,c _ i for this operation).
• If t _ i=3, convert all lowercase letters in S to uppercase (do not use x _ i,c _ i for this operation).

Print the S after the Q operations.

Constraints

• 1\leq N\leq5\times10^5
• S is a string of length N consisting of uppercase and lowercase English letters.
• 1\leq Q\leq5\times10^5
• 1\leq t _ i\leq3\ (1\leq i\leq Q)
• If t _ i=1, then 1\leq x _ i\leq N\ (1\leq i\leq Q).
• c _ i is an uppercase or lowercase English letter.
• If t _ i\neq 1, then x _ i=0 and c _ i= 'a'.
• N,Q,t _ i,x _ i are all integers.

Sample Input 1

7
AtCoder
5
1 4 i
3 0 a
1 5 b
2 0 a
1 4 Y

Sample Output 1

atcYber

Initially, the string S is AtCoder.

• The first operation changes the 4-th character to i, changing S to AtCider.
• The second operation converts all lowercase letters to uppercase, changing S to ATCIDER.
• The third operation changes the 5-th character to b, changing S to ATCIbER.
• The fourth operation converts all uppercase letters to lowercase, changing S to atciber.
• The fifth operation changes the 4-th character to Y, changing S to atcYber.

After the operations, the string S is atcYber, so print atcYber.

Sample Input 2

35
TheQuickBrownFoxJumpsOverTheLazyDog
10
2 0 a
1 19 G
1 13 m
1 2 E
1 21 F
2 0 a
1 27 b
3 0 a
3 0 a
1 15 i

Sample Output 2

TEEQUICKBROWMFiXJUGPFOVERTBELAZYDOG

Problem Statement

There are N roulette wheels. The i-th (1\leq i\leq N) wheel has P _ i integers S _ {i,1},S _ {i,2},\ldots,S _ {i,P _ i} written on it, and you can play it once by paying C _ i yen. When you play the i-th wheel once, an integer j between 1 and P _ i, inclusive, is chosen uniformly at random, and you earn S _ {i,j} points.

The points you earn from the wheels are determined independently of past results.

Takahashi wants to earn at least M points. Takahashi will act to minimize the amount of money he pays before he earns at least M points. After each play, he can choose which wheel to play next based on the previous results.

Find the expected amount of money Takahashi will pay before he earns at least M points.

Constraints

• 1\leq N\leq 100
• 1\leq M\leq 100
• 1\leq C _ i\leq 10 ^ 4\ (1\leq i\leq N)
• 1\leq P _ i\leq 100\ (1\leq i\leq N)
• 0\leq S _ {i,j}\leq M\ (1\leq i\leq N,1\leq j\leq P _ i)
• \displaystyle\sum _ {j=1}^{P _ i}S _ {i,j}\gt0\ (1\leq i\leq N)
• All input values are integers.

Sample Input 1

3 14
100 2 5 9
50 4 1 2 4 8
70 5 2 4 2 8 8

Sample Output 1

215.913355350494384765625

For instance, Takahashi can play the wheels as follows.

• Pay 50 yen to play roulette 2 and earn S _ {2,4}=8 points.
• Pay 50 yen to play roulette 2 and earn S _ {2,1}=1 point.
• Pay 100 yen to play roulette 1 and earn S _ {1,1}=5 points. He has earned a total of 8+1+5\geq14 points, so he quits playing.

In this case, he pays 200 yen before earning 14 points.

Your output will be considered correct when the relative or absolute error from the true value is at most 10 ^ {-5}, so outputs such as 215.9112 and 215.9155 would also be considered correct.

Sample Input 2

2 100
1 2 1 2
10 6 0 0 0 0 0 100

Sample Output 2

60

It is optimal to keep spinning roulette 2 until you get 100 points.

Sample Input 3

20 90
3252 9 0 4 2 7 3 2 3 2 4
2147 1 1
4033 8 0 4 1 7 5 2 5 0
3795 6 6 6 2 3 2 2
3941 7 2 4 4 7 2 0 5
2815 6 2 1 0 5 2 2
3020 2 3 6
3858 9 4 2 7 3 0 4 4 6 5
4533 10 3 6 4 0 6 4 4 2 7 7
4198 8 6 7 0 6 3 6 5 6
3739 8 2 7 1 5 1 4 4 7
2465 4 1 4 0 1
4418 9 7 6 2 4 6 1 5 0 7
5450 12 0 4 4 7 7 4 4 5 4 5 3 7
4196 9 1 6 5 5 7 2 3 6 3
4776 9 2 2 7 3 6 6 1 6 6
2286 3 3 5 6
3152 3 4 1 5
3509 7 0 6 7 0 1 0 3
2913 6 0 1 5 0 5 6

Sample Output 3

45037.072314895291126319493887599716

Problem Statement

N players, player 1, player 2, ..., player N, participate in a game tournament. Just before the tournament starts, each player forms a one-person team, so there are N teams in total.

The tournament has a total of N-1 matches. In each match, two different teams are chosen. One team goes first, and the other goes second. Each match will result in exactly one team winning. Specifically, for each i = 1, 2, \ldots, N-1, the i-th match proceeds as follows.

• The team with player p_i goes first, and the team with player q_i goes second.
• Let a and b be the numbers of players in the first and second teams, respectively. The first team wins with probability \frac{a}{a+b}, and the second team wins with probability \frac{b}{a+b}.
• Then, the two teams are combined into a single team.

The result of each match is independent of those of the others.

For each of the N players, print the expected number of times the team with that player wins throughout the tournament, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i, q_i \leq N
• Just before the i-th match, player p_i and player q_i belong to different teams.
• All input values are integers.

Sample Input 1

5
1 2
4 3
5 3
1 4

Sample Output 1

698771048 698771048 964969543 964969543 133099248

We call a team formed by player x_1, player x_2, \ldots, player x_k as team \lbrace x_1, x_2, \ldots, x_k \rbrace.

• The first match is played by team \lbrace 1 \rbrace, with player 1, and team \lbrace 2 \rbrace, with player 2. Team \lbrace 1 \rbrace wins with probability \frac{1}{2}, and team \lbrace 2 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 1, 2 \rbrace.
• The second match is played by team \lbrace 4 \rbrace, with player 4, and team \lbrace 3 \rbrace, with player 3. Team \lbrace 4 \rbrace wins with probability \frac{1}{2}, and team \lbrace 3 \rbrace wins with probability \frac{1}{2}. Then, the two teams are combined into a single team \lbrace 3, 4 \rbrace.
• The third match is played by team \lbrace 5 \rbrace, with player 5, and team \lbrace 3, 4 \rbrace, with player 3. Team \lbrace 5 \rbrace wins with probability \frac{1}{3}, and team \lbrace 3, 4 \rbrace wins with probability \frac{2}{3}. Then, the two teams are combined into a single team \lbrace 3, 4, 5 \rbrace.
• The fourth match is played by team \lbrace 1, 2 \rbrace, with player 1, and team \lbrace 3, 4, 5 \rbrace, with player 4. Team \lbrace 1, 2 \rbrace wins with probability \frac{2}{5}, and team \lbrace 3, 4, 5 \rbrace wins with probability \frac{3}{5}. Then, the two teams are combined into a single team \lbrace 1, 2, 3, 4, 5 \rbrace.

The expected numbers of times the teams with players 1, 2, 3, 4, 5 win throughout the tournament, E_1, E_2, E_3, E_4, E_5, are \frac{9}{10}, \frac{9}{10}, \frac{53}{30}, \frac{53}{30}, \frac{14}{15}, respectively.

Sample Input 2

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

Sample Output 2

43970290 310168785 806914186 501498951 950708909 272140427 335124893 168750835 310168785 168750835 280459129 280459129 272140427 476542843 43970290

Problem Statement

There are N monsters in a cave: monster 1, monster 2, \ldots, monster N. Each monster has a positive integer attack power and a type represented by an integer between 1 and M, inclusive. Specifically, for i = 1, 2, \ldots, N, the attack power and type of monster i are A_i and B_i, respectively.

Takahashi will go on an adventure in this cave with a health of H and some of the M amulets: amulet 1, amulet 2, \ldots, amulet M.

In the adventure, Takahashi performs the following steps for i = 1, 2, \ldots, N in this order (as long as his health does not drop to 0 or below).

• If Takahashi has not brought amulet B_i with him, monster i will attack him and decrease his health by A_i.
• Then,
  • if his health is greater than 0, he defeats monster i;
  • otherwise, he dies without defeating monster i and ends his adventure.

Solve the following problem for each K = 0, 1, \ldots, M independently.

Find the maximum number of monsters that Takahashi can defeat when choosing K of the M amulets to bring on the adventure.

The constraints guarantee that there is at least one monster of type i for each i = 1, 2, \ldots, M.

Constraints

• 1 \leq M \leq N \leq 3 \times 10^5
• 1 \leq H \leq 10^9
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq M
• For each 1 \leq i \leq M, there is 1 \leq j \leq N such that B_j = i.
• All input values are integers.

Sample Input 1

7 3 7
3 2
1 1
4 2
1 2
5 1
9 3
2 3

Sample Output 1

2 5 7 7

Consider the case K = 1. Here, Takahashi can bring amulet 2 to defeat the maximum possible number of monsters, which is 5. The adventure proceeds as follows.

• For i = 1, he avoids the attack of monster 1 since he has amulet 2. Then, he defeats monster 1.
• For i = 2, he takes the attack of monster 2 and his health becomes 6 since he does not have amulet 1. Then, he defeats monster 2.
• For i = 3, he avoids the attack of monster 3 since he has amulet 2. Then, he defeats monster 3.
• For i = 4, he avoids the attack of monster 4 since he has amulet 2. Then, he defeats monster 4.
• For i = 5, he takes the attack of monster 5 and his health becomes 1 since he does not have amulet 1. Then, he defeats monster 5.
• For i = 6, he takes the attack of monster 6 and his health becomes -8 since he does not have amulet 3. Then, he dies without defeating monster 6 and ends his adventure.

Similarly, when K=0, he can defeat 2 monsters; when K=2, he can defeat all 7 monsters by bringing amulets 2 and 3; when K=3, he can defeat all 7 monsters by bringing amulets 1, 2, and 3.

Sample Input 2

15 5 400
29 5
27 4
79 1
27 2
30 3
4 1
89 2
88 3
75 5
3 1
39 4
12 1
62 4
38 2
49 1

Sample Output 2

8 12 15 15 15 15

Problem Statement

There are N line segments in a coordinate plane, and the i-th line segment (1\leq i\leq N) has two points (a _ i,b _ i) and (c _ i,d _ i) as its endpoints. Here, each line segment includes its endpoints. Additionally, no two line segments share a point.

We want to place a single closed disk in this plane so that it shares a point with each line segment. In other words, we want to draw a single circle so that each line segment shares a point with either the circumference of the circle or its interior (or both). Find the smallest possible radius of such a disk.

Constraints

• 2\leq N\leq 100
• 0\leq a _ i,b _ i,c _ i,d _ i\leq1000\ (1\leq i\leq N)
• (a _ i,b _ i)\neq(c _ i,d _ i)\ (1\leq i\leq N)
• The i-th and j-th line segments do not share a point (1\leq i\lt j\leq N).
• All input values are integers.

Sample Input 1

4
2 3 2 10
4 0 12 6
4 8 6 3
7 8 10 8

Sample Output 1

3.319048676309097923796460081961

The given line segments are shown in the figure below. The closed disk shown in the figure, centered at \left(\dfrac{32-\sqrt{115}}4,\dfrac{21-\sqrt{115}}2\right) with a radius of \dfrac{24-\sqrt{115}}4, shares a point with all the line segments.

It is impossible to place a disk with a radius less than \dfrac{24-\sqrt{115}}4 so that it shares a point with all the line segments, so the answer is \dfrac{24-\sqrt{115}}4.

Your output will be considered correct if the absolute or relative error from the true value is at most 10^{-5}, so outputs such as 3.31908 and 3.31902 would also be considered correct.

Sample Input 2

20
0 18 4 28
2 21 8 21
3 4 10 5
3 14 10 13
5 9 10 12
6 9 10 6
6 28 10 18
12 11 15 13
12 17 12 27
13 17 20 18
13 27 19 26
16 1 16 13
16 22 19 25
17 22 20 19
18 4 23 4
18 5 23 11
22 16 22 23
23 15 30 15
23 24 30 24
24 0 24 11

Sample Output 2

12.875165712523887403637822024952

The closed disk shown in the figure, centered at \left(\dfrac{19817-8\sqrt{5991922}}{18},\dfrac{-2305+\sqrt{5991922}}9\right) with a radius of \dfrac{3757\sqrt{29}-44\sqrt{206618}}{18}, shares a point with all the line segments.

Sample Input 3

30
526 655 528 593
628 328 957 211
480 758 680 794
940 822 657 949
127 23 250 385
281 406 319 305
277 598 190 439
437 450 725 254
970 478 369 466
421 225 348 141
872 64 600 9
634 460 759 337
878 514 447 534
142 237 191 269
983 34 554 284
694 160 589 239
391 631 22 743
377 656 500 606
390 576 184 312
556 707 457 699
796 870 186 773
12 803 505 586
343 541 42 165
478 340 176 2
39 618 6 651
753 883 47 833
551 593 873 672
983 729 338 747
721 77 541 255
0 32 98 597

Sample Output 3

485.264732620930836460637042310401