Problem Statement

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

Problem Statement

You are given N sequences numbered 1 to N.
Sequence i has a length of L_i and its j-th element (1 \leq j \leq L_i) is a_{i,j}.

Sequence i and Sequence j are considered the same when L_i = L_j and a_{i,k} = a_{j,k} for every k (1 \leq k \leq L_i).
How many different sequences are there among Sequence 1 through Sequence N?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq 2 \times 10^5 (1 \leq i \leq N)
• 0 \leq a_{i,j} \leq 10^{9} (1 \leq i \leq N, 1 \leq j \leq L_i)
• The total number of elements in the sequences, \sum_{i=1}^N L_i, does not exceed 2 \times 10^5.
• All values in input are integers.

Sample Input 1

4
2 1 2
2 1 1
2 2 1
2 1 2

Sample Output 1

3

Sample Input 1 contains four sequences:

• Sequence 1 : (1, 2)
• Sequence 2 : (1, 1)
• Sequence 3 : (2, 1)
• Sequence 4 : (1, 2)

Except that Sequence 1 and Sequence 4 are the same, these sequences are pairwise different, so we have three different sequences.

Sample Input 2

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

Sample Output 2

4

Sample Input 2 contains five sequences:

• Sequence 1 : (1)
• Sequence 2 : (1)
• Sequence 3 : (2)
• Sequence 4 : (1, 1)
• Sequence 5 : (1, 1, 1)

Sample Input 3

1
1 1

Sample Output 3

1

Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq T_i \leq 10^9
• 0 \leq K_i < i
• 1 \leq A_{i,j} < i
• \sum_{i=1}^N K_i \leq 2\times 10^5
• A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
• All values in input are integers.

Sample Input 1

3
3 0
5 1 1
7 1 1

Sample Output 1

10

Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

Sample Input 2

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

Sample Output 2

5000000000

Note that the answer may not fit into a 32-bit integer.

Problem Statement

The Republic of AtCoder lies on a Cartesian coordinate plane.
It has N towns, numbered 1,2,\dots,N. Town i is at (x_i, y_i), and no two different towns are at the same coordinates.

There are teleportation spells in the nation. A spell is identified by a pair of integers (a,b), and casting a spell (a, b) at coordinates (x, y) teleports you to (x+a, y+b).

Snuke is a great magician who can learn the spell (a, b) for any pair of integers (a, b) of his choice. The number of spells he can learn is also unlimited.
To be able to travel between the towns using spells, he has decided to learn some number of spells so that it is possible to do the following for every pair of different towns (i, j).

• Choose just one spell among the spells learned. Then, repeatedly use just the chosen spell to get from Town i to Town j.

At least how many spells does Snuke need to learn to achieve the objective above?

Constraints

• 2 \leq N \leq 500
• 0 \leq x_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq y_i \leq 10^9 (1 \leq i \leq N)
• (x_i, y_i) \neq (x_j, y_j) if i \neq j.

Sample Input 1

3
1 2
3 6
7 4

Sample Output 1

6

The figure below illustrates the positions of the towns (along with the coordinates of the four corners).

If Snuke learns the six spells below, he can get from Town i to Town j by using one of the spells once for every pair (i,j) (i \neq j), achieving his objective.

• (2, 4)
• (-2, -4)
• (4, -2)
• (-4, 2)
• (-6, -2)
• (6, 2)

Another option is to learn the six spells below. In this case, he can get from Town i to Town j by using one of the spells twice for every pair (i,j) (i \neq j), achieving his objective.

• (1, 2)
• (-1, -2)
• (2, -1)
• (-2, 1)
• (-3, -1)
• (3, 1)

There is no combination of spells that consists of less than six spells and achieve the objective, so we should print 6.

Sample Input 2

3
1 2
2 2
4 2

Sample Output 2

2

The optimal choice is to learn the two spells below:

• (1, 0)
• (-1, 0)

Sample Input 3

4
0 0
0 1000000000
1000000000 0
1000000000 1000000000

Sample Output 3

8

Problem Statement

Given is an undirected graph with N vertices and M edges. The vertices are called Vertex 1, Vertex 2, \ldots, Vertex N, and the edges are called Edge 1, Edge 2, \ldots, Edge M. Edge i (1 \leq i \leq M) connects Vertex U_i and Vertex V_i. It is guaranteed that the graph is simple: it has no self-loops and no multi-edges.

There are 2^M ways to direct every edge in this graph. We want each vertex to have exactly one edge going from that vertex to another vertex. How many ways are there to direct the edges in that way? Since the answer may be enormous, print it modulo 998244353.

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
• All values in input are integers.
• The given graph is simple.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

There are two ways to direct the edges to achieve the objective:

• 1\rightarrow 2 , 2\rightarrow 3 , 1\leftarrow 3
• 1\leftarrow 2 , 2\leftarrow 3 , 1\rightarrow 3

Sample Input 2

2 1
1 2

Sample Output 2

0

It is obviously impossible to make every vertex have one edge going from that vertex.

Sample Input 3

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

Sample Output 3

4

Problem Statement

For a permutation P = (p_1, p_2, \dots, p_N) of (1,2, \dots, N), let us define the score S(P) of P as follows.

• There are N people, numbered 1,2,\dots,N. Additionally, Snuke is there. Initially, Person i (1 \leq i \leq N) has Ball i.
  Each time Snuke screams, every Person i such that i \neq p_i gives their ball to Person p_i simultaneously.
  If, after screaming at least once, every Person i has Ball i, Snuke stops screaming.
  The score is the number of times Snuke screams until he stops. Here, it is guaranteed that the score will be a finite value.

There are N! permutations P of (1,2, \dots, N). Find the sum, modulo 998244353, of the scores of those permutations, each raised to the K-th power.

• Formally, let S_N be the set of the permutations of (1,2, \dots, N). Compute the following: \displaystyle \left(\sum_{P \in S_N} S(P)^K \right) \bmod {998244353}.

Constraints

• 2 \leq N \leq 50
• 1 \leq K \leq 10^4
• All values in input are integers.

Sample Input 1

2 2

Sample Output 1

5

When N = 2, there are two possible permutations P: (1,2),(2,1).

The score of the permutation (1,2) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 1.

The score of the permutation (2,1) is found as follows.

• Initially, Person 1 has Ball 1, and Person 2 has Ball 2.
  After Snuke's first scream, Person 1 has Ball 2, and Person 2 has Ball 1.
  After Snuke's second scream, Person 1 has Ball 1, and Person 2 has Ball 2.
  Here, every Person i has Ball i, so he stops screaming.
  Thus, the score is 2.

Therefore, the answer in this case is 1^2 + 2^2 = 5.

Sample Input 2

3 3

Sample Output 2

79

All permutations and their scores are listed below.

• (1,2,3): The score is 1.
• (1,3,2): The score is 2.
• (2,1,3): The score is 2.
• (2,3,1): The score is 3.
• (3,1,2): The score is 3.
• (3,2,1): The score is 2.

Thus, we should print 1^3 + 2^3 + 2^3 + 3^3 + 3^3 + 2^3 = 79.

Sample Input 3

50 10000

Sample Output 3

77436607

Problem Statement

We have parcels with five different weights: 1, 2, 3, 4, 5. For each i (1 \leq i \leq 5), there are A_i parcels of weight i.
Additionally, we have people with five different strengths: 1, 2, 3, 4, 5. For each i (1 \leq i \leq 5), there are B_i people with strength i.
Each person can carry any number of parcels (possibly zero), but the total weight of the parcels must not exceed their strength.

You are given T test cases. For each case, determine whether it is possible for the people to carry all parcels with the appropriate allocation of parcels. That is, determine whether it is possible to allocate each parcel to someone so that each person is allocated parcels whose total weight does not exceed their strength. It is fine to have someone who carries no parcels.

Constraints

• 1 \leq T \leq 5\times 10^4
• 0 \leq A_i,B_i \leq 10^{16}
• 1 \leq A_1+A_2+A_3+A_4+A_5
• 1 \leq B_1+B_2+B_3+B_4+B_5
• All values in input are integers.

Sample Input 1

3
5 1 0 0 1
0 0 0 2 1
0 3 0 0 0
0 0 2 0 0
10000000000000000 0 0 0 0
0 0 0 0 2000000000000000

Sample Output 1

Yes
No
Yes

In the first test case, all parcels can be carried. Here is one way to do so:

• The first person with strength 4 carries four parcels of weight 1.
• The second person with strength 4 carries one parcel of weight 1 and another of weight 2.
• The person with strength 5 carries one parcel of weight 5.

In the second test case, one of the two people with strength 3 has to carry two or more parcels of weight 2, which is impossible.

Problem Statement

We have N continuous random variables X_1,X_2,\dots,X_N. X_i has a continuous uniform distribution over the interval \lbrack L_i, R_i \rbrack.
Let E be the expected value of the K-th greatest value among the N random variables. Print E \bmod {998244353} as specified in Notes.

Notes

In this problem, we can prove that E is always a rational number. Additionally, the Constraints of this problem guarantee that, when E is represented as an irreducible fraction \frac{y}{x}, x is indivisible by 998244353.
Here, there uniquely exists an integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353}. Print this z as the value E \bmod {998244353}.

Constraints

• 1 \leq N \leq 50
• 1 \leq K \leq N
• 0 \leq L_i \lt R_i \leq 100
• All values in input are integers.

Sample Input 1

1 1
0 2

Sample Output 1

1

The answer is the expected value of the random variable with a continuous uniform distribution over the interval \lbrack 0, 2 \rbrack. Thus, we should print 1.

Sample Input 2

2 2
0 2
1 3

Sample Output 2

707089751

The answer represented as a rational number is \frac{23}{24}. We have 707089751 \times 24 \equiv 23 \pmod{998244353}, so we should print 707089751.

Sample Input 3

10 5
35 48
44 64
47 59
39 97
36 37
4 91
38 82
20 84
38 50
39 69

Sample Output 3

810056397