Problem Statement

In Japan, swallows can be observed from April through September.

Given an integer M between 1 and 12, determine if swallows can be observed in month M (where January is month 1).

Constraints

• M is an integer between 1 and 12, inclusive.

Sample Input 1

4

Sample Output 1

Yes

Swallows can be observed in April (month 4).

Sample Input 2

12

Sample Output 2

No

Swallows cannot be observed in December (month 12), which is not in the season from April through September.

Sample Input 3

9

Sample Output 3

Yes

Problem Statement

You are given three positive integers A, B, and C.

Print Yes if A, B, and C are all equal, and No otherwise.

Constraints

• 1\leq A ,B,C\leq 9
• A, B, and C are integers.

Sample Input 1

3 3 3

Sample Output 1

Yes

A=B=C=3, so A, B, and C are all equal. Thus, Yes should be printed.

Sample Input 2

7 7 8

Sample Output 2

No

A=7 and C=8, so A and C are not equal. Thus, No should be printed.

Sample Input 3

1 2 3

Sample Output 3

No

Problem Statement

You are going to hold a competitive programming contest several times.
Holding a contest requires preparing a total of eight problems: one problem of each difficulty from 1 through 8.

You have prepared N problems, the i-th of which is of difficulty A_i.
If you cannot use the same problem for multiple contests, at most how many contests can you hold with the N problems prepared?

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq A_i \leq 8
• All input values are integers.

Sample Input 1

10
1 2 3 4 5 5 6 7 8 8

Sample Output 1

1

For example, you can hold one contest with the 1-st, 2-nd, 3-rd, 4-th, 5-th, 7-th, 8-th, and 9-th problems.

Sample Input 2

27
3 1 4 1 5 2 6 5 3 5 8 7 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7

Sample Output 2

2

Sample Input 3

1
1

Sample Output 3

0

Problem Statement

You held a programming contest. There were N participants, and the i-th (1\leq i\leq N) of them scored A _ i points.

In order to make their scores integers between 0 and 10^9 (inclusive), you are going to determine the relative score of the i-th participant for each i=1,2,\ldots,N by the following expression:

• \operatorname{round}\left(10^9\times\dfrac{A _ i}{\max _ iA _ i}\right).

Here, \max _ iA _ i denotes the maximum value among A _ i, and \operatorname{round}(x) denotes x rounded off to an integer. Formally, \max _ iA _ i is A _ i that satisfies A _ j\leq A _ i for all j (1\leq j\leq N), and \operatorname{round}(x) is the unique integer n satisfying n-\dfrac12\leq x\lt n+\dfrac12.

Find the relative score of the i-th participant for i=1,2,\ldots,N.

Constraints

• 1\leq N\leq10^5
• 1\leq A _ i\leq10^9 (1\leq i\leq N)
• All input values are integers.

Sample Input 1

3
200 600 300

Sample Output 1

333333333 1000000000 500000000

The relative score of each participant is computed as follows.

\max _ iA _ i=A _ 2=600, since A _ 1\leq A _ 2,A _ 2\leq A _ 2, and A _ 3\leq A _ 2.

• The 1-st participant scored A _ 1=200 points. 10^9\times\dfrac{200}{600}=\dfrac{10^9}3 and 333333333-\dfrac12\leq\dfrac{10^9}3\lt333333333+\dfrac12, so the relative score of the 1-st participant is 333333333.
• The 2-nd participant scored A _ 2=600 points. 10^9\times\dfrac{600}{600}=10^9 and 1000000000-\dfrac12\leq10^9\lt1000000000+\dfrac12, so the relative score of the 2-nd participant is 1000000000.
• The 3-rd participant scored A _ 3=300 points. 10^9\times\dfrac{300}{600}=5\times10^8 and 500000000-\dfrac12\leq5\times10^8\lt500000000+\dfrac12, so the relative score of the 3-rd participant is 500000000.

Sample Input 2

2
1 999999999

Sample Output 2

1 1000000000

Sample Input 3

10
55580908 183811851 247188750 266233976 335843599 344138315 389659771 389921297 698238479 720357617

Sample Output 3

77157382 255167498 343147270 369585841 466217877 477732597 540925454 541288504 969294226 1000000000

Problem Statement

Given a positive integer X, find the minimum non-negative integer n such that X\leq 10^n.

Constraints

• 1\leq X\leq 10^{100000}
• X is an integer.

Sample Input 1

23

Sample Output 1

2

23>1=10^0, 23>10=10^1, and 23\leq 100=10^2, so 2 should be printed.

Sample Input 2

1

Sample Output 2

0

1\leq 10^0, so 0 should be printed.

Sample Input 3

12345678901234567890

Sample Output 3

20

Problem Statement

Given a string S consisting of digits and * (multiplication sign), interpret S as a mathematical expression, evaluate it, and report the result modulo 998244353. For example, S= 5*32*2 evaluates to 5 \times 32 \times 2 = 320.

Here, it is guaranteed that S is a valid expression. In other words, it is guaranteed that:

• multiple * do not occur contiguously in S;
• S starts with a digit;
• S ends with a digit.

Constraints

• S is a string consisting of digits and *.
• S is a valid expression.
• S has a length between 1 and 10^6, inclusive.

Sample Input 1

5*32*2

Sample Output 1

320

This example is already described in the problem statement.

Sample Input 2

998244354

Sample Output 2

1

S may not contain *.

Be sure to report the evaluated value modulo 998244353.

Sample Input 3

05*000

Sample Output 3

0

Numbers in S may have leading zeros.

Problem Statement

There are 3N sticks. The length of the i-th stick is A_i.

How many ways are there to group them into triplets so that they form N triangles?

Here, two ways to form N triangles are distinguished if and only if there is a triplet forming a triangle in one way that does not form a triangle in the other way.
For more details, see the description of Sample Input 1.

Constraints

• 1 \leq N \leq 4
• 1 \leq A_i \leq 100
• All input values are integers.

Sample Input 1

2
3 3 3 4 4 6

Sample Output 1

7

We denote by (i,j,k) the triangle formed by the following three sticks: i-th, j-th, and k-th.

There are seven ways as follows. Note that equal-length sticks are distinguished.

• (1,2,3),(4,5,6)
• (1,2,4),(3,5,6)
• (1,2,5),(3,4,6)
• (1,3,4),(2,5,6)
• (1,3,5),(2,4,6)
• (2,3,4),(1,5,6)
• (2,3,5),(1,4,6)

On the other hand, for instance, the 1-st, 2-nd, and 6-th sticks do not form a triangle.

Sample Input 2

4
100 100 100 100 100 100 100 100 100 100 100 100

Sample Output 2

15400

Problem Statement

You are making plans for an upcoming N-day vacation.

On each day, you will either "play" or "study."
Among the N days, you need to study on at least M days.
You will not study on two or more days in a row.
If you play on day i, you get a joy of A_i; if you study, the joy is 0 on that day.

Find the maximum possible total joy of the N days.

Constraints

• 1 \leq N \leq 3000
• 0 \leq M \leq \frac{N+1}{2}
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5 2
3 2 4 1 5

Sample Output 1

12

You can play on days 1, 3, and 5, and study on days 2 and 4 to get a joy of 12.

Sample Input 2

5 2
3 5 4 1 2

Sample Output 2

11

You can play on days 2, 3, and 5, and study on days 1 and 4 to get a joy of 11.
Note that you cannot study on two or more days in a row.

Sample Input 3

10 0
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

10000000000

Problem Statement

N children are standing in line. Initially, the i-th child from the front has A_i candies.

You are going to repeat the following operation M times.

• Give K candies to the child with the fewest candies (if there are multiple such children, to the frontmost one among them).

Find how many candies the children will have after the M operations.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^{12}
• 1 \leq K \leq 10^5
• 0 \leq A_i \leq 10^{12}
• All input values are integers.

Sample Input 1

4 3 2
3 4 1 10

Sample Output 1

5 4 5 10

• The 1-st operation gives candies to the 3-rd child from the front. Now, the children have 3,4,3, and 10 candies.
• The 2-nd operation gives candies to the 1-st child from the front. Now, the children have 5,4,3, and 10 candies.
• The 3-rd operation gives candies to the 3-rd child from the front. Now, the children have 5,4,5, and 10 candies.

Sample Input 2

2 1000000000000 100000
1000000000000 1

Sample Output 2

50000500000000000 50000500000000001

Sample Input 3

3 1415 9
26 53 58

Sample Output 3

4292 4292 4288

Problem Statement

The New Year's bell rang N times at equal intervals. More specifically, the bell rang at times t, d+t, 2d+t, \ldots, (N-1)d+t for some positive integer d and integer t.

Takahashi heard the bell ring at times A_1, A_2, \ldots, A_K. Although it is certain that the bell actually rang when Takahashi heard the sound, the bell may have also rung at other times.

You are given N, K, and A_1, A_2, \ldots, A_K. List all possible values for the positive integer d in ascending order.

Under the constraints of this problem, it can be proved that the number of possible values for d is finite.

Constraints

• 2 \leq N \leq 10^9
• 2 \leq K \leq \min \lbrace N, 2 \times 10^5 \rbrace
• 0 \leq A_1 \lt A_2 \lt \cdots \lt A_K \leq 10^9
• All input values are integers.
• There is at least one possible value for the positive integer d.

Sample Input 1

8 3
3 7 15

Sample Output 1

2
2 4

There are two possible values for d: 2 and 4.

• For d = 2, it is possible that the bell rang eight times, for instance, at times 3, 5, 7, 9, 11, 13, 15, 17.
• For d = 4, it is possible that the bell rang eight times, for instance, at times -5, -1, 3, 7, 11, 15, 19, 23.

Sample Input 2

500 22
30 42 138 318 354 378 450 462 522 582 630 738 834 894 930 942 1002 1050 1062 1110 1146 1158

Sample Output 2

4
3 4 6 12

Problem Statement

There is an N \times N grid. Let (i,j) denote the square at the i-th row from the top and j-th square from the left.

Each square is one of the following: the starting point, a goal, a passage, and a hole. The state of the square (i,j) is given as S_{i,j}.

• S indicates that the square is the starting point. There is exactly one starting point.
• G indicates that the square is a goal. There is one or more goals.
• . indicates that the square is a passage.
• X indicates that the square is a hole.

Solve the following problem for k=1,2,\dots,N-1.

You are initially at the starting square. Then, you repeat the following operation.

• Choose one of the four directions: up, down, left, right. Move k squares consecutively in the chosen direction.

You may not pass through a hole square or exit the grid by the operation.

Determine if you can be at a goal square at the end of an operation, and if so, find the minimum number of operations required to do so.

Note that passing through a goal in the middle of an operation does not count as finishing at a goal square.

Constraints

• 1 \le N \le 1500
• S_{i,j} is S, G, ., or X.
• There is exactly one pair (i,j) such that S_{i,j}=S.
• There is one or more pairs (i,j) such that S_{i,j}=G.
• N is an integer.

Sample Input 1

5
SX...
.....
..GX.
..XG.
X.X.G

Sample Output 1

4
2
-1
-1

For k=2, you can perform two operations as follows to be at the goal square at the end of an operation.

• Choose down. Move from (1,1) to (3,1).
• Choose right. Move from (3,1) to (3,3).

With just one operation, you cannot be at a goal square at the end of an operation, so the answer is 2.

Note that for k=3, the operation cannot be performed as follows.

• Choose right. Move from (1,1) to (1,4).

This operation is not allowed because it passes through (1,2), which is a hole.

Sample Input 2

2
GX
XS

Sample Output 2

-1

Problem Statement

You are given a sequence of length N consisting of positive integers, A=(A_1,A_2,\ldots,A_N), and an empty set S.

Let us define f(L,R) as \displaystyle\sum_{i=L+1}^R \frac{A_i}{R-L} for a pair of integers (L,R) such that 0\leq L<R\leq N.

Process Q queries in the given order. Each query is of one of the following two types.

• Type 1 : You are given an integer x satisfying 0\leq x\leq N. If x is not in S, add x to S; otherwise, remove x from S.
• Type 2 : Let X be the maximum value of f(l,r) over all pairs of integers (l,r) such that l,r\in S and 0\leq l<r\leq N. Then, X is uniquely represented as \frac{P}{Q} using positive integers P and Q that are coprime. Print P and Q separated by spaces. It is guaranteed that at the time this query is given, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Constraints

• 1\leq N\leq 10^5
• 3\leq Q\leq 3\times 10^5
• 1\leq A_i\leq 10^9
• 0\leq x\leq N
• All input values are integers.
• There is at least one query of type 2.
• At the time of processing a query of type 2, there is at least one pair (l,r) such that l,r\in S and 0\leq l<r\leq N.

Sample Input 1

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

Sample Output 1

10 3
5 1
3 1

The values of f(L,R) are as follows.

• f(0,1)=\frac{2}{1}=\frac{2}{1}
• f(0,2)=\frac{2+3}{2}=\frac{5}{2}
• f(0,3)=\frac{2+3+5}{3}=\frac{10}{3}
• f(1,2)=\frac{3}{1}=\frac{3}{1}
• f(1,3)=\frac{3+5}{2}=\frac{8}{2}
• f(2,3)=\frac{5}{1}=\frac{5}{1}

The queries are processed as follows.

• The first query is of type 1 and gives x=0. Since 0\notin S, add 0 to S.
• The second query adds 3 to S.
• The third query is of type 2, and we have S= \{ 0,3 \} at this point, so (0,3) is the only (l,r) such that l,r\in S and 0\leq l<r\leq N. We have f(0,3)=\frac{10}{3}, so print 10 and 3 separated by spaces.
• The fourth query adds 2 to S.
• At the time of the fifth query, we have S=\{0,2,3\}, and the pairs (l,r) that satisfy the condition are (0,2), (0,3), and (2,3). The maximum f(l,r) over these pairs is f(2,3)=\frac{5}{1}. Thus, print 5 and 1 in this order.
• The sixth query adds 1 to S.
• We have 3\in S just before the seventh query, so remove 3 from S.
• At the time of the eighth query, we have S=\{ 0,1,2\}, and the maximum f(l,r) over the pairs satisfying the conditions is f(1,2)=\frac{3}{1}. Thus, print 3 and 1 in this order.

Sample Input 2

2 3
1 1
1 0
1 2
2

Sample Output 2

1 1

Note that P and Q in each query of type 2 must be coprime. That is, you must not print 2 2 in this test case.

Problem Statement

There are two line segments in the xy-plane. The endpoints of the i-th line segment are at coordinates (a_i,b_i) and (c_i,d_i).
Determine if these two line segments intersect.

Constraints

• -1000 \leq a_i,b_i,c_i,d_i \leq 1000
• (a_i,b_i)\neq (c_i,d_i)
• All input values are integers.

Sample Input 1

0 0 10 10
0 10 10 0

Sample Output 1

Yes

As shown below, the two line segments intersect at coordinates (5,5).

Sample Input 2

0 0 10 0
0 10 0 0

Sample Output 2

Yes

Sample Input 3

0 0 10 0
0 10 0 1

Sample Output 3

No

Sample Input 4

0 3 8 7
0 3 8 7

Sample Output 4

Yes

Problem Statement

For a multiset (set with duplicate elements allowed) S of positive integers, let us define the function f(S) as follows.

• First, let A=(A_0,A_1,...,A_{|S|-1}) be the sorted list of the elements of S in ascending order.
• Then, let f(S)=\displaystyle \sum_{i=0}^{|S|-1} K^i A_i. This constant K is given from the input.
• Here, let f(S)=0 if S is empty.

There is an initially empty multiset T. Let us perform the following operations on this set Q times in total.

+ X

Add one instance of x to T.

- x

Remove one instance of x from T. It is guaranteed that at least one instance of x exists in T at this time.

After each operation, find the value of f(T) modulo 998244353 at that time.

Constraints

• Q and K are integers.
• 1 \le Q \le 3 \times 10^5
• 1 \le K < 998244353
• For every operation, x is an integer.
• For each operation +, 1 \le x < 998244353.
• For each operation -, there is one or more instances of x in T at that time.

Sample Input 1

10 2
+ 7
- 7
+ 2
+ 3
- 2
+ 3
+ 5
- 3
+ 998244352
+ 5

Sample Output 1

7
0
2
8
3
9
29
13
9
25

• The first operation adds one instance of 7 to T.
  • Now, T=\{7\} and f(T)=7.
• The second operation removes one instance of 7 from T.
  • Now, T=\{\} and f(T)=0.
• The third operation adds one instance of 2 to T.
  • Now, T=\{2\} and f(T)=2.
• The fourth operation adds one instance of 3 to T.
  • Now, T=\{2,3\} and f(T)=8.
• The fifth operation removes one instance of 2 from T.
  • Now, T=\{3\} and f(T)=3.
• The sixth operation adds one instance of 3 to T.
  • Now, T=\{3,3\} and f(T)=9.
• The seventh operation adds one instance of 5 to T.
  • Now, T=\{3,3,5\} and f(T)=29.
• The eighth operation removes one instance of 3 from T.
  • Now, T=\{3,5\} and f(T)=13.
• The ninth operation adds one instance of 998244352 to T.
  • Now, T=\{3,5,998244352\} and f(T)=3992977421, so print this modulo 998244353, that is, 9.
• The tenth operation adds one instance of 5 to T.
  • Now, T=\{3,5,5,998244352\} and f(T)=7985954849, so print this modulo 998244353, that is, 25.

Problem Statement

You are given a sequence of length N, A=(A_1,A_2,\ldots,A_N), and another of length K, P=(P_1,P_2,\ldots,P_K).

We now perform the following Q operations on the sequence A.

• The q-th operation (1\leq q \leq Q) is represented by integers l_q,r_q\ (1\leq l_q \leq r_q\leq N) and a sequence of length K, b_q = (b_{q,1},b_{q,2},\ldots,b_{q,K}). For the q-th operation, consider the infinite sequence B=(B_1,B_2,\ldots) determined by the following linear recurrence relation, and add B_i to A_{l_q+i-1} for each i=1,2,\ldots,r_q-l_q+1.
  • B_j=b_{q,j}\ (1\leq j \leq K)
  • B_j=P_1B_{j-1}+P_2B_{j-2}+\ldots +P_KB_{j-K}\ (j > K)

Find the value, modulo 998244353, of each element of A after all the operations.

Constraints

• 1\leq N,Q \leq 2\times 10^5
• 1\leq K \leq 10
• 1\leq l_q \leq r_q\leq N
• 0\leq A_i,P_i,b_{q,i} < 998244353
• All input values are integers.

Sample Input 1

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

Sample Output 1

3 6 9 12 6

Initially, A=(0,0,0,0,0,0).

• In the first operation, B=(3,1,5,11,27,\ldots). After this operation, A=(3,1,5,11,0,0).
• In the second operation, B=(4,1,6,13,32,\ldots). After this operation, A=(3,1,9,12,6).
• In the third operation, B=(5,9,23,55,133,\ldots). After this operation, A=(3,6,9,12,6).

Thus, after all the operations, A is (3,6,9,12,6).

Sample Input 2

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

Sample Output 2

8

Sample Input 3

10 3 5
306334866 801978559 895954374 576826717 755317213 872021310 894146017 171871727 347837426 489203653
259995927 523608184 755770553
4 7
822177140 73169010 811074390
7 8
739309938 819084714 711663615
1 9
105947194 88003242 226522376
6 8
544083472 975159386 830222368
1 9
478160947 233931690 460328037

Sample Output 3

890443007 125669138 584560434 427420890 15883850 302004751 273022029 711724605 576696309 489203653