Problem Statement

There are 3 cards. The 1-st card has an integer A written on it; the 2-nd has an integer B; the 3-rd has an integer C.

When choosing 2 cards out of these 3 cards, find the minimum and maximum possible products of the integers written on the chosen 2 cards.

Constraints

• -100 \leq A, B, C \leq 100
• A, B, and C are integers

Sample Input 1

5 -2 4

Sample Output 1

-10 20

The product of the integers written on the chosen 2 cards will be

• 5 \times (-2) = -10 if the 1-st and the 2-nd cards were chosen;
• 5 \times 4 = 20 if the 1-st and the 3-rd cards were chosen;
• (-2) \times 4 = -8 if the 2-nd and the 3-rd cards were chosen.

Therefore, the minimum possible product of the 2 integers written on the chosen 2 cards are -10, and the maximum is 20.

Sample Input 2

0 0 0

Sample Output 2

0 0

Problem Statement

Takahashi wants to make many bouquets. Each bouquet should consist of A red flowers and B blue flowers.

Takahashi has X red flowers and Y blue flowers. How many bouquets can he make at most?

Constraints

• 1 \leq A,B \leq 100
• 0 \leq X,Y \leq 100
• All values in input are integers.

Sample Input 1

3 2 6 4

Sample Output 1

2

He can make 2 bouquets.

Sample Input 2

3 3 100 0

Sample Output 2

0

Sample Input 3

5 10 30 23

Sample Output 3

2

Problem Statement

A monomial consisting of a number and an English lowercase variable is said to be a good monomial if an English lowercase single-letter variable is multiplied from the left by an integer coefficient between 1 and 999 (inclusive). Here, we assume that the coefficient in a good monomial is never omitted even if the coefficient is 1.
For example, 123a and 1z are good monomials, while 0a, 1000b, 123, 12ab, a123, and a are not.

Next, let us define the value of a good monomial by the value when certain values are assigned to the monomial. Specifically, the value for each variable to be assigned is determined by the following equations:

• a=1000
• b=1000a
• \dots
• z=1000y

For instance, the value of 123a is 123000, the value of 20b is 20000000, and the value of 1c is 1000000000.

Among the possible values of good monomials, print the maximum one not exceeding \alpha in the form of a good monomial.
We can prove that such monomial always uniquely exists under the Constraints of this problem.

Constraints

• 1000 \le \alpha < 10^{81}
• \alpha is an integer.

Sample Input 1

123456789

Sample Output 1

123b

We have 123b = 123000000, which is the maximum possible value of a good monomial not exceeding \alpha = 123456789.

Sample Input 2

77777

Sample Output 2

77a

Sample Input 3

9982443539982448531000000007

Sample Output 3

9i

The input may not fit into 64-bit integer type.

Problem Statement

Takahashi took T tests of the same format. Each test has N subjects numbered 1 to N.
In the i-th test, he scored P_{i,j} points in Subject j.

For each K=1,2,\ldots,T, answer the following question.

Question:
Let C_j be the highest score in Subject j in the first K tests. Find C_1+\ldots+C_N.

Constraints

• 1 \leq T \leq 10^3
• 1 \leq N \leq 10
• 0 \leq P_{i,j} \leq 10^5
• All values in input are integers.

Sample Input 1

2 3
50 80 60
60 70 70

Sample Output 1

190
210

In the 1-st test, Takahashi scored 50,80,60 in Subject 1,2,3, respecitively. In the 2-nd test, he scored 60,70,70.

• The answer for K=1 is 50+80+60=190.
• The answer for K=2 is 60+80+70=210.

Sample Input 2

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

Sample Output 2

10
13
15
16

Problem Statement

YYYY/MM/DD format is a notation of date, consisting of the zero-padded 4-digit year, zero-padded 2-digit month, and zero-padded 2-digit day, separated by slashes. For example, January 1, 2022 is represented as 2022/01/01.

A date is called good when it has two or fewer different digits in YYYY/MM/DD format.

You are given a date S in YYYY/MM/DD format. Print the first good day not earlier than S, in YYYY/MM/DD format.
Here, we use the Gregorian calendar.

Constraints

• S is a valid date in the Gregorian calendar.
• S is given in YYYY/MM/DD format.
• S is between January 1, 2001 and December 31, 2999 (inclusive).

Sample Input 1

2022/01/01

Sample Output 1

2022/02/02

The first day that satisfies the condition not earlier than S = January 1, 2022 is February 2, 2022.
There are other good dates such as February 22, 2222 that are not earlier than S, but they are later than February 2, 2022 and not the first good day.

Sample Input 2

2002/02/22

Sample Output 2

2002/02/22

Sample Input 3

2002/02/23

Sample Output 3

2020/02/02

Sample Input 4

2999/12/31

Sample Output 4

3000/03/03

Problem Statement

The Kingdom of Takahashi consists of N states numbered 1 to N.
The map of the kingdom is a grid with H rows and W columns. The square at the i-th row from the top and j-th column from the left belongs to State A_{i,j}.

Is the condition below satisfied when painting State i in Color C_i in this map?

Different states that are vertically or horizontally adjacent are painted in different colors.

Constraints

• 1 \leq H \leq 200
• 1 \leq W \leq 200
• 1\leq N \leq \min(100,H\times W)
• 1\leq A_{i,j} \leq N
• For every k(1\leq k\leq N), there is at least one pair (i,j) such that A_{i,j}=k.
• 1\leq C_i \leq N
• All values in input are integers.

Sample Input 1

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

Sample Output 1

No

State 2 and State 3 are adjacent but painted in the same color, so the condition is not satisfied. (In the figure below, "色" means color.)

Sample Input 2

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

Sample Output 2

Yes

Some states, such as State 1 here, may have holes. Also, some states, such as State 2 here, may be disconnected.

Sample Input 3

2 2 3
1 2
3 1
1 2 2

Sample Output 3

Yes

Since State 2 and State 3 are not vertically or horizontally adjacent, painting them in the same color does not violate the condition.

Problem Statement

Assume that the equation a x^5 + bx + c=0 satisfies the condition below.

• It has exactly one solution in the interval 1\lt x \lt 2.

Find the solution of the equation in the interval 1\lt x \lt 2.

Constraints

• 1 \leq a \leq 10^9
• 1 \leq b \leq 10^9
• -10^9 \leq c \leq 10^9
• All values in input are integers.
• The given equation has exactly one solution in the interval 1\lt x \lt 2.

Sample Input 1

32 2 -246

Sample Output 1

1.500000000000000000

For x = 1.5, we have ax^5+bx+c=32\times(1.5)^5 + 2\times1.5 - 246 = 0.

Sample Input 2

12 3 -45

Sample Output 2

1.279562760087743278

Problem Statement

There is a graph with N vertices, numbered 1, \dots, N. Initially, there is no edge in this graph.

Process Q queries of the format below.

• 1 u v : Add an undirected edge connecting Vertex u and Vertex v.
• 2 u: List in ascending order all indices of vertices reachable from Vertex u by traversing zero or more edges at the moment the query is given.

Here, it is guaranteed that the total number of vertices to be listed in queries of the form 2 u within a single test case is at most 2 \times 10^5.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq u \lt v \leq N in a query of the form 1 u v.
• 1 \leq u \leq N in a query of the form 2 u.
• There is at least one query of the form 2 u.
• Within a single test case, the total number of vertices to be listed in queries of the form 2 u is at most 2 \times 10^5.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1 2
5
1 2 3 4
1 2 3 4

Sample Input 2

1 2
2 1
2 1

Sample Output 2

1
1

Sample Input 3

3 3
1 1 2
2 1
1 1 2

Sample Output 3

1 2

Multiple edges may be added between the same pair of vertices.

Problem Statement

Consider an infinite xy-plane.
You are given two sets of N points each: S = \lbrace (x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N) \rbrace and T = \lbrace (X_1, Y_1), (X_2, Y_2), \ldots, (X_N, Y_N) \rbrace.

You may do exactly one of the two operations below zero or one time.

• Choose a line parallel to the x-axis and reflect each point in S over the chosen line.
• Choose a line parallel to the y-axis and reflect each point in S over the chosen line.

Determine whether it is possible to make S equal T as a set.

Constraints

• 1 \leq N \leq 2 \times 10^5
• |x_i|, |y_i|, |X_i|, |Y_i| \leq 10^9
• i \neq j \Rightarrow (x_i, y_i) \neq (x_j, y_j)
• i \neq j \Rightarrow (X_i, Y_i) \neq (X_j, Y_j)
• All values in input are integers.

Sample Input 1

3
2 3
0 3
0 1
-1 3
1 1
1 3

Sample Output 1

Yes

We have S = \lbrace (0, 1), (0, 3), (2, 3) \rbrace, T = \lbrace (1, 3), (-1, 3), (1, 1) \rbrace.
If you choose the line x = 0.5, which is parallel to the y-axis, each point in S moves as follows: (0, 1) \rightarrow (1, 1), (0, 3) \rightarrow (1, 3), (2, 3) \rightarrow (-1, 3), after which S is equal to T as a set. Thus, Yes should be printed.

Sample Input 2

2
1 1
0 0
0 0
-1 -1

Sample Output 2

No

There is no way to do an operation to make S equal T as a set, so No should be printed. Note that you may do only one of the two operations in the Problem Statement.

Sample Input 3

3
3 1
4 1
5 9
5 9
3 1
4 1

Sample Output 3

Yes

Before doing any operation, S is already equal to T.

Problem Statement

From N integers A_1,A_2,\ldots,A_N, we will choose K distinct integers. Here, any combination of K of the integers is chosen with equal probability.

Let X and Y be the maximum and minimum values among the chosen integers, respectively. Find the expected value of X-Y, modulo 998244353.

Notes

Under the Constraints of this problem, it can be proved that the sought expected value can be represented as p/q using two coprime integers p,q, and there uniquely exists an integer r such that rq\equiv p \pmod{998244353} and 0\leq r < 998244353. You should find this r.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• All A_i are distinct.
• All values in input are integers.

Sample Input 1

3 2
3 7 5

Sample Output 1

665496238

There are three possible choices of K integers, as follows, chosen with equal probability.

\{3,7\}: Here we have X-Y=7-3=4.

\{3,5\}: Here we have X-Y=5-3=2.

\{7,5\}: Here we have X-Y=7-5=2.

The expected value is \dfrac{4+2+2}{3}=\dfrac{8}{3}, which modulo 998244353 is 665496238.

Sample Input 2

3 1
3 7 5

Sample Output 2

0

Sample Input 3

10 5
384 887 778 916 794 336 387 493 650 422

Sample Output 3

621922587

Problem Statement

You are given a weighted directed graph with N vertices and M edges.

The vertices are numbered 1 to N.
The i-th edge (1 \leq i \leq M) goes from Vertex u_i to Vertex v_i and has a weight of w_i.

For each k=1,2,\ldots,N, solve the problem below.

• Determine whether there is a path that starts at Vertex 1, visits Vertex k one or more times, and ends at Vertex N. If it exists, print the shortest possible length of such a path.

Constraints

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

Sample Input 1

3 3
1 2 3
2 3 4
1 3 2

Sample Output 1

2
7
2

• For k=1, the shortest path traverses the 3-rd edge to reach Vertex 3 directly.
• For k=2, the shortest path first traverses the 1-rd edge to get to Vertex 2 and then traverses the 2-nd edge to reach Vertex 3.
• For k=3, the shortest path traverses the 3-rd edge to reach Vertex 3 directly.

Sample Input 2

5 10
2 1 1
2 5 5
1 2 6
2 5 4
5 3 2
1 3 1
1 3 4
3 5 4
1 5 3
5 2 3

Sample Output 2

3
10
5
-1
3

Problem Statement

Find the remainder when an integer N is divided by M.

Since N is enormous, it is given to you in the format below.

Format: You are given K characters C_i and K positive integers D_i. Let S_i be the concatenation of D_i copies of the character C_i. N is the concatenation of S_1,\ldots,S_N in this order, seen as a decimal integer.

Constraints

• 2\leq M \leq 10^9
• 1 \leq K \leq 10^5
• C_i is a digit between 0 and 9 (inclusive).
• C_1 is not 0.
• 1\leq D_i \leq 10^{12}
• All values in input are integers.

Sample Input 1

3 11
1 4
2 2
3 1

Sample Output 1

3

We have N=1111223. The remainder when N is divided by 11 is 3.

Sample Input 2

2 10000
1 1
0 1000000000000

Sample Output 2

0

N is written as 1 followed by 10^{12} zeros. The remainder when N is divided by 10000 is 0.

Sample Input 3

8 5054049
1 41421356
1 7320508075
2 2360679
3 141592653589
0 57721566
1 644934066848
2 99792458
9 192631770

Sample Output 3

3689688

Problem Statement

N players called Player 1, Player 2, \ldots, Player N are playing a game. The initial score of Player i is P_i points.

Process Q queries in the order they are given. There are three kinds of queries, as follows.

• 1 a x: Change the score of Player a to x.
• 2 a: Print the current rank of Player a among the N players. Specifically, if Player a has the r-th highest score, print the integer r.
• 3 r: Print the player who currently ranks r-th. Specifically, if Player a has the r-th highest score, print the integer a.

Here, it is guaranteed that the initial scores of the players, and the scores after the changes given as queries of the first kind, are all distinct.

Constraints

• 1 \leq N,Q \leq 5\times 10^5
• 0\leq P_i \leq 10^9
• P_i \neq P_j (i\neq j)
• 1\leq a \leq N
• 0\leq x \leq 10^9
• 1\leq r \leq N
• All x in the queries of the first kind are distinct and different from all of P_i.
• There is at least one query of the second or third kind.
• All values in input are integers.

Sample Input 1

3 5
10 30 20
2 1
3 1
1 2 0
2 1
3 2

Sample Output 1

3
2
2
1

Initially, Player 1, Player 2, Player 3 has 10, 30, 20 points, respectively.

• For the first query, Player 1 has the third highest score, so 3 should be printed.
• For the second query, Player 2 has the first highest score, so 2 should be printed.
• In the third query, the score of Player 2 is changed to 0. Now, Player 1, Player 2, Player 3 has 10, 0, 20 points, respectively.
• For the fourth query, Player 1 has the second highest score, so 2 should be printed.
• For the fifth query, Player 1 has the second highest score, so 1 should be printed.

Problem Statement

You are given an integer sequence A of length N.
In an N \times N grid, Takahashi has written the value A_i-A_j in the square at the i-th row from the top and j-th column from the left.
How many different values are written in the grid?

Constraints

• All values in input are integers.
• 1 \le N \le 2 \times 10^5
• 1 \le A_i \le 2 \times 10^5

Sample Input 1

3
5 2 3

Sample Output 1

7

After the numbers are written, the grid looks as follows, containing 7 different values.

Sample Input 2

10
13 21 34 55 89 1 2 3 5 8

Sample Output 2

75

Problem Statement

You are given M pairs (A_i,B_i) of distinct integers between 1 and N (inclusive).
Determine whether there is a permutation P=(P_1, P_2,\ldots , P_N) of the integers 1 to N such that P_{A_i}+P_{B_i} is a multiple of 3 for all 1\leq i\leq M.

Constraints

• 2 \leq N \leq 1000
• 0 \leq M \leq \min\left( \frac{N(N-1)}{2},2\times 10^5 \right)
• 1 \leq A_i<B_i \leq N
• The pairs (A_i, B_i) are all distinct.
• All values in input are integers.

Sample Input 1

5 2
1 2
2 3

Sample Output 1

Yes

If we choose P=(1,2,4,3,5), for example, we have P_1+P_2=1+2=3 and P_2+P_3=2+4=6, satisfying the conditions.

Sample Input 2

3 2
1 2
2 3

Sample Output 2

No

There are 3!=6 possible permutations, but none satisfies all of the conditions.