Problem Statement

There is a traffic light with a button.
In principle, if you press the button when the light is red, it turns green X seconds later.
However, if it would turn green earlier than Y seconds after it turned red last time, it turns green Y seconds after it turned red last time instead.

Now, the button has just been pressed Z seconds after it turned red last time.
How many seconds will pass before it turns green since it turned red last time?

Constraints

• 1 \leq X,Y,Z \leq 100
• All values in input are integers.

Sample Input 1

10 20 5

Sample Output 1

20

The elapsed time Z since it turned red plus X equals 5 + 10 = 15 seconds, which is less than Y = 20 seconds. So, as mentioned in the Problem Statement, it will turn green 20 seconds after it turned red.

Sample Input 2

10 20 15

Sample Output 2

25

Sample Input 3

36 49 73

Sample Output 3

109

Problem Statement

You are given an integer N. Truncate \displaystyle\frac{N}{100} by discarding the fractional part and print the resulting integer.

Constraints

• 1 \leq N \leq 10^{500000}
• N is an integer.

Sample Input 1

9876

Sample Output 1

98

We have \displaystyle\frac{9876}{100} = 98.76, and discarding the fractional part results in 98. Thus, 98 should be printed.

Sample Input 2

99

Sample Output 2

0

We have \displaystyle\frac{99}{100} = 0.99, and discarding the fractional part results in 0. Thus, 0 should be printed.

Sample Input 3

31415926535897932384626433832795028841971693993

Sample Output 3

314159265358979323846264338327950288419716939

Note that the values in input and output may be enormous.

Problem Statement

We have three six-sided dice. When the i-th die is thrown, it shows the number j with the probability \frac{P_{i,j}} {100}.

If we throw these three dice, what is the probability that the sum of the numbers shown is K, for each K=1,2,\ldots,18?

Constraints

• 0\leq P_{i,j}\leq 100
• P_{i,1}+P_{i,2}+P_{i,3}+P_{i,4}+P_{i,5}+P_{i,6} = 100
• All values in input are integers.

Sample Input 1

10 10 20 20 20 20
10 10 20 20 20 20
10 10 20 20 20 20

Sample Output 1

0.000000
0.000000
0.001000
0.003000
0.009000
0.019000
0.036000
0.060000
0.086000
0.114000
0.132000
0.140000
0.132000
0.108000
0.080000
0.048000
0.024000
0.008000

Sample Input 2

100 0 0 0 0 0
100 0 0 0 0 0
100 0 0 0 0 0

Sample Output 2

0.000000
0.000000
1.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000
0.000000

Problem Statement

Mr. Aoki gave Takahashi, his student, an assignment that asked him to make a simple undirected graph.

An undirected graph is simple when both of the following conditions are satisfied.

• There are no multi-edges. That is, for any two vertices u and v, there is at most one edge connecting u and v.
• There are no self-loops. That is, for any vertex v, there is no edge connecting v and v itself.

Takahashi writes his undirected graph G in the following format in his notebook and submits it to his teacher.

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Here, N and M are the numbers of vertices and edges in G, respectively, and u_i and v_i for each i = 1, 2, \ldots, M means that the i-th edge connects Vertex u_i and Vertex v_i.

Mr. Aoki will check whether Takahashi's writing correctly describes a simple undirected graph. More accurately, the teacher will check whether both of the following are satisfied.

• 1 \leq u_i \leq N and 1 \leq v_i \leq N, for every i = 1, 2, \ldots, M.
• The undirected graph described is simple.

Put yourself in Mr. Aoki's shoes and check whether Takahashi's writing satisfies both conditions above.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq 2 \times 10^5
• All values in input are integers.

Sample Input 1

3 3
1 2
2 3
3 4

Sample Output 1

No

Here we have N = 3 and v_3 = 4, which is in violation of 1 \leq v_3 \leq N. Therefore, No should be printed.

Sample Input 2

2 2
1 2
2 1

Sample Output 2

No

This undirected graph has two edges connecting Vertex 1 and Vertex 2 and thus is not simple. Therefore, No should be printed.

Sample Input 3

1 1
1 1

Sample Output 3

No

This undirected graph has a self-loop connecting Vertex 1 and itself and thus is not simple. Therefore, No should be printed.

Sample Input 4

5 4
1 3
3 4
4 1
2 5

Sample Output 4

Yes

Problem Statement

Let us play a game of bowling consisting of R rounds.
Each round goes as follows.

• Place N pins.
• Repeat the following procedure M times.
  • Throw a ball toward them, and record the number of pins knocked down as the score.
  • Remove the pins knocked down.
  • If all N pins have been removed, end the round even if this procedure is not repeated M times.

You are given a sequence of L integers: s=(s_1,s_2,\ldots,s_L).
Determine whether this can be a sequence of scores recorded in order in the whole game.

Constraints

• 1 \leq R,N,M \leq 100
• R \leq L \leq R\times M
• 0 \leq s_i \leq N
• All values in input are integers.

Sample Input 1

3 10 5 9
7 3 0 2 4 0 1 0 10

Sample Output 1

Yes

In the first round, 7 and then 3 pins are knocked down. In the second round, 0, 2, 4, 0, and then 1 pin(s) are knocked down. In the third round, 0 and then 10 pins are knocked down.

Sample Input 2

1 100 3 2
10 20

Sample Output 2

No

Sample Input 3

2 100 3 5
100 10 20 30 40

Sample Output 3

No

Sample Input 4

3 30 100 5
20 20 15 15 30

Sample Output 4

No

Problem Statement

We have N kinds of drugs numbered 1 to N.
The efficiency of a drug is represented by an integer from 1 to 100; the greater, the more efficient. The efficiency of Drug i is A_i. (All A_i are distinct.)
The drugs also contain allergens (substances that cause allergic reactions). Allergens are represented by integers from 1 to 2 \times 10^5, and Drug i contains C_i allergens X_{i,1}, X_{i,2}, \dots, X_{i,C_i}.

You are given Q queries, which should be processed according to the instruction. The p-th query is the following:

Person p has allergies to D_p allergens Y_{p,1}, Y_{p,2}, \dots, Y_{p,D_p}, and may not be given a drug containing one or more of those allergens.
Consider giving Person p one of the drugs from Drug 1 to Drug N. Print the number representing the most efficient drug that may be given to Person p. If no drug may be given, print -1.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_j if i \neq j.
• 0 \leq C_i
• 0 \leq \sum_{i=1}^N C_i \leq 10^5
• 1 \leq X_{i,j} \leq 2 \times 10^5
• X_{i, j} \neq X_{i, k} if j \neq k.
• 1 \leq Q \leq 10^5
• 0 \leq D_p
• 0 \leq \sum_{p=1}^Q D_{p} \leq 10^5
• 1 \leq Y_{p,q} \leq 2 \times 10^5
• Y_{p,q} \neq Y_{p,r} if q \neq r.
• All values in input are integers.

Sample Input 1

3
10 9 8
3
1 2 3
1
1
2
2 3
4
0

1
1
1
2
2
1 2

Sample Output 1

1
3
2
-1

Here is a summary of information about the drugs and queries.

• Drug 1 has an efficiency of 10 and contains Allergens 1, 2, and 3.
• Drug 2 has an efficiency of 9 and contains Allergen 1.
• Drug 3 has an efficiency of 8 and contains Allergens 2 and 3.
• Person 1 may be given any drug.
• Person 2 may not be given a drug containing Allergen 1.
• Person 3 may not be given a drug containing Allergen 2.
• Person 4 may not be given a drug containing one or more of Allergens 1 and 2.

Problem Statement

Let S be a string consisting of lowercase English letters and T be a string consisting of lowercase English letters and ?.
S is said to be obtainable from T when one can replace each occurrence of ? in T with some lowercase English letter so that T equals S.

For example, abcd and addd are obtainable from a??d, while bcdd is not.

You are given N strings S_1, S_2, \ldots, S_N consisting of lowercase English letters.
All of these strings have a length of L: |S_1| = |S_2| = \cdots = |S_N| = L.

A string T of length L consisting of lowercase English letters is arbitrarily chosen so that it contains exactly K ?s.
Find the maximum possible number of strings among S_1, S_2, \ldots, S_N that are obtainable from T.

Constraints

• 1 \leq N \leq 1000
• 1 \leq L \leq 10
• 0 \leq K \leq L
• N, L, and K are integers.
• Each of S_1, S_2, \ldots, S_N is a string of length L consisting of lowercase English letters.
• S_1, S_2, \ldots, S_N are distinct.

Sample Input 1

5 4 2
aabc
bbaa
abbc
cccc
acba

Sample Output 1

3

If we let T = a?b?, then S_1 = aabc, S_3 = abbc, and S_5 = acba are obtainable from T. Here, three of the strings S_1, S_2, \ldots, S_N are obtainable from T, which is the maximum possible number. Note that K = 2, so T must be chosen to contain exactly two ?s.

Sample Input 2

5 4 4
aabc
bbaa
abbc
cccc
acba

Sample Output 2

5

If we let T = ????, all of S_1, S_2, S_3, S_4, S_5 are obtainable from T.

Sample Input 3

5 4 0
aabc
bbaa
abbc
cccc
acba

Sample Output 3

1

Problem Statement

Takahashi has 0 gold coins, 10^9 silver coins, and X bronze coins.

A shop sells N bags. For i = 1, 2, \ldots, N, the i-th bag can be bought by paying A_i silver coins and B_i bronze coins. The i-th bag contains C_i gold coins; by buying the bag, he obtains the gold coins in it.

A gold coin is worth 10^{100^{100}} yen (the currency in Japan), a silver coin is worth 10^{100} yen, and a bronze coin is worth 1 yen. Takahashi wants to buy some (possibly zero) of the N bags and maximize the resulting total value of the gold, silver, and bronze coins he has. Print the numbers of gold, silver, and bronze coins, when the resulting total value of the gold, silver, and bronze coins is maximized.

The bronze and silver coins required for buying a bag cannot be substituted by another kind of coin. For example, a silver coin is worth 10^{100} bronze coins when converted into yen, but it does not mean you can pay a silver coin instead of paying bronze coins.

Constraints

• 1 \leq N \leq 3000
• 0 \leq X \leq 3000
• 0 \leq A_i, B_i \leq 3000
• 1 \leq A_i + B_i
• 1 \leq C_i \leq 3000
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5 999999997 0

If Takahashi buys the 1-st and 5-th bags, he will pay A_1+A_5 = 2 + 1 = 3 silver coins and B_1+B_5 = 2 + 2 = 4 bronze coins, and obtain C_1+C_5 = 3 + 2 = 5 gold coins. As a result, he will have 5 gold coins, 10^9-3 silver coins, and 0 bronze coins, for a total value of 5 \times 10^{100^{100}} + (10^9-3) \times 10^{100} + 0 \times 1 yen, which is maximum possible.

Sample Input 2

20 50
4 3 7
2 0 8
7 2 4
9 0 9
6 5 8
4 7 1
3 9 2
3 9 2
7 4 4
2 7 3
6 3 2
4 10 8
2 2 10
8 1 5
3 2 6
3 8 5
8 1 9
3 7 4
9 6 2
5 6 7

Sample Output 2

92 999999930 0

Problem Statement

Solve the following problem for T test cases.

Takahashi has 10^{100} coupons, each worth M yen, available in Lunlun Mart.
The shop does not give change on these coupons where the price of the purchased item is less than the value of the coupons.

On the i-th day, Takahashi will buy an apple worth A \times i yen using only the coupons.
Here, the sadness of Takahashi increases by k \times M - A \times i, where k is the minimum number of (M-yen) coupons needed to pay at least A \times i yen.

In N days of shopping, how much total sadness will Takahashi accumulate?

Constraints

• All values in input are integers.
• 1 \le T \le 10^5
• 1 \le N \le 10^6
• 1 \le A,M \le 300

Sample Input 1

10
4 5 8
8 9 10
4 10 7
10 1 5
6 4 9
304607 77 89
291969 231 9
424790 216 294
76881 213 111
312895 58 1

Sample Output 1

14
36
12
20
24
13402703
875907
61169622
4151490
0

This input contains 10 test cases.
In the first case, N=4, A=5, and M=8.

• On the 1-st day, he buys an apple worth 5 yen. One 8-yen coupon is needed, and his sadness increases by 3.
• On the 2-nd day, he buys an apple worth 10 yen. Two 8-yen coupons are needed, and his sadness increases by 6.
• On the 3-rd day, he buys an apple worth 15 yen. Two 8-yen coupons are needed, and his sadness increases by 1.
• On the 4-th day, he buys an apple worth 20 yen. Three 8-yen coupons are needed, and his sadness increases by 4.

Therefore, the answer to this case is 3+6+1+4=14.

Problem Statement

There is a rectangular garden that is H meters long and W meters wide.

At the center of the garden is a sprinkler, which sprays water within a radius of D meters from it.

Find the proportion of the area sprayed by the sprinkler in the garden.

Constraints

• 1 \leq H,W \leq 10^5
• 1 \leq D \leq 10^5
• All values in input are integers.

Sample Input 1

10 15 3

Sample Output 1

0.1884955592

The sprinkler sprays the interior of a circle of radius 3 meters, whose area is about 28.3 square meters.
The area of the garden is 10\times 15=150 square meters, so the desired proportion is 0.1884955592\ldots.

Sample Input 2

10 15 6

Sample Output 2

0.6939614954

The sprinkler sprays the interior of a circle of radius 6 meters, some of which sticks out of the garden.
The area of the region sprayed by the sprinkler is about 104.1 square meters, and the area of the garden is 10\times 15=150 square meters, so the desired proportion is 0.6939614954\ldots.

Problem Statement

There is an undirected graph with N vertices and M edges. Initially, the i-th edge connects Vertex a_i and Vertex b_i.

Process Q queries. The i-th query is represented by t_i, x_i, and y_i as follows.

• If t_i=1, add an edge connecting Vertex x_i and Vertex y_i. There are at most 10 queries of this kind in a single test case.
• If t_i=2, delete the edge connecting Vertex x_i and Vertex y_i.
• If t_i=3, print Yes if Vertex x_i and Vertex y_i belong to the same connected component, and No otherwise.

Constraints

• 1 \leq N,M,Q \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• (a_i,b_i) \neq (a_j,b_j) if i \neq j.
• t_i \in \{ 1,2,3 \}
• 1 \leq x_i \lt y_i \leq N
• There are at most 10 indices i such that t_i=1.
• If t_i=1, there is no edge connecting Vertex x_i and Vertex y_i when the query is given.
• If t_i=2, there is an edge connecting Vertex x_i and Vertex y_i when the query is given.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
Yes

Sample Input 2

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

Sample Output 2

There may be no query such that t_i=3.

Problem Statement

There are N paintings numbered 1, \dots, N. We are going to choose some of them to display in an exhibition.

Takahashi the critic has decided to score the exhibition as follows:

• For i = 1, \dots, N, add A_i points if Painting i is exhibited.
• Additionally, for j = 1 \dots, M, add P_j points if all of the following conditions are satisfied:
  • The number of exhibited paintings with indices strictly less than Q_j is congruent to L_j modulo 3.
  • The number of exhibited paintings with indices greater than or equal to Q_j is congruent to R_j modulo 3.

Print the maximum possible score of the exhibition.

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)
• 1 \leq P_j \leq 10^9 \, (1 \leq j \leq M)
• 1 \leq Q_j \leq N + 1 \, (1 \leq j \leq M)
• 0 \leq L_j, R_j \leq 2 \, (1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

8

When only the 3-rd painting is exhibited, the score is 3 + 5 = 8 points, which is maximum possible.

Sample Input 2

1 1
1
10 1 0 0

Sample Output 2

10

It is optimal to exhibit no paintings.

Sample Input 3

4 1
3 1 4 1
5 3 1 1

Sample Output 3

12

Problem Statement

There is a series of manga consisting of N books. The i-th (1 \leq i \leq N) book is sold for A_i yen.

These books are also sold in sets. There are M sets, the j-th (1 \leq j \leq M) of which is sold for B_j yen and contains the L_j-th, (L_j + 1)-th, \ldots, R_j-th books of the series.

At least how many yen does one have to pay to get at least one of each of the N books?

Constraints

• 1 \leq N, M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9 \, (1 \leq i \leq N)
• 1 \leq B_j \leq 10^9 \, (1 \leq j \leq M)
• 1 \leq L_j \leq R_j \leq N \, (1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

5 3
5 4 6 2 3
4 1 2
7 2 4
14 2 5

Sample Output 1

14

One can get at least one of each of the N = 5 books for 14 yen as follows. This is the minimum one has to pay.

• Buy the 1-st set for B_1 = 4 yen to get the 1-st and 2-nd books.
• Buy the 2-nd set for B_2 = 7 yen to get the 2-nd, 3-rd, and 4-th books.
• Buy the 5-th book for A_5 = 3 yen.

Sample Input 2

6 3
3 1 4 1 5 9
3 1 2
12 4 6
10 3 4

Sample Output 2

19

Problem Statement

We have a grid with H horizontal rows and W vertical columns. The square at the i-th row from the top and j-th column from the left has a lowercase English character a_{i,j} written on it. Additionally, we have an empty string S.

Process Q queries in the order given by the input, and print the resulting S after processing the Q queries.

Each query is of one of the following two kinds.

• 1 p c:Append the character a_{p,W} to the tail of the string S. Then, set a_{p,1}=c,a_{p,2}=a_{p,1},a_{p,3}=a_{p,2},\dots,a_{p,W}=a_{p,W-1} simultaneously.
• 2 p c:Append the character a_{H,p} to the tail of the string S. Then, set a_{1,p}=c,a_{2,p}=a_{1,p},a_{3,p}=a_{2,p},\dots,a_{H,p}=a_{H-1,p} simultaneously.

Constraints

• 1 \le H,W \le 2 \times 10^5
• 1 \le H \times W \le 2 \times 10^5
• 1 \le Q \le 2 \times 10^5
• H, W, and Q are integers.
• a_{i,j} is a lowercase English character.
• Each query is in one of the two formats specified in the Problem Statement.
• For each query of type 1, 1 \le p \le H, p is an integer, and c is a lowercase English letter.
• For each query of type 2, 1 \le p \le W, p is an integer, and c is a lowercase English letter.

Sample Input 1

2 2 2
ab
cd
1 2 x
2 1 y

Sample Output 1

dx

The grid transitions as follows:

ab
cd

ab
xc

yb
ac

S results in dx, so dx should be printed.

Sample Input 2

3 4 8
abcd
defg
ghij
1 2 a
1 2 b
1 2 c
1 2 d
2 3 x
2 3 y
2 3 y
2 3 y

Sample Output 2

gfedibcx

Problem Statement

There are two boxes A and B that contain balls with integers between 0 and 2^N-1 written on them. Box A contains A_i balls with the integer i (0 \leq i \lt 2^N), and Box B contains B_i balls with the integer i (0 \leq i \lt 2^N). All balls are distinguishable.

Consider picking up one ball from each of Box A and Box B. Among the (number of balls in Box A) \times (number of balls in Box B) ways to do so, let f(x, y) be the number of ones that satisfy the following condition.

• Here we denote by \mathrm{popcount}(x) the number of 1s in the binary notation of x.
  Let a and b be the integers written on the balls from A and B, respectively. Then, the bitwise OR of a and b is x, and \mathrm{popcount}(a) + \mathrm{popcount}(b) is y.

You are given sequences X and Y of length Q each. Compute f(X_i, Y_i) modulo 998244353 for every i (1 \leq i \leq Q).

Constraints

• 1 \leq N \leq 17
• 1 \leq Q \leq 10^5
• 0 \leq A_i \lt 998244353 (0 \leq i \lt 2^N)
• 0 \leq B_i \lt 998244353 (0 \leq i \lt 2^N)
• 0 \leq X_i \lt 2^N (1 \leq i \leq Q)
• 0 \leq Y_i \leq 2N (1 \leq i \leq Q)
• All values in input are integers.

Sample Input 1

2 3
3 1 4 1
5 9 2 6
1 1
3 2
2 0

Sample Output 1

32
61
0

• For x = 1 and y = 1, the corresponding pairs (a, b) are (a,b) = (0, 1), (1, 0). Thus, the sought number is A_0 \times B_1 + A_1 \times B_0 = 32.
• For x = 3 and y = 2, the corresponding pairs (a, b) are (a,b) = (0,3),(1,2),(2,1),(0,3). Thus, the sought number is A_0 \times B_3 + A_1 \times B_2 + A_2 \times B_1 + A_3 \times B_0 = 61.
• For x = 2 and y = 0, there are no corresponding pairs (a, b). Thus, the sought number is 0.

Sample Input 2

1 1
0 0
1 2
1 1

Sample Output 2

0

One or more of the boxes may be empty.