Problem Statement

Takahashi is making a computer baseball game.
He will write a program that shows a batter's batting average with a specified number of digits.

There are integers A and B, which satisfy 1 \leq A \leq 10 and 0 \leq B \leq A.
Let S be the string obtained as follows.

• Round off \dfrac{B}{A} to three decimal digits, then write the integer part (1 digit), . (the decimal point), and the decimal part (3 digits) in this order, with trailing zeros.

For example, if A=7 and B=4, then \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

You are given A and B as the input and asked to print S.

Constraints

• 1 \leq A \leq 10
• 0 \leq B \leq A
• A and B are integers.

Sample Input 1

7 4

Sample Output 1

0.571

As explained in the Problem Statement, \dfrac{B}{A} = \dfrac{4}{7} = 0.571428\dots rounded off to three decimal digits is 0.571. Thus, S is 0.571.

Sample Input 2

7 3

Sample Output 2

0.429

\dfrac{B}{A} = \dfrac{3}{7} = 0.428571\dots rounded off to three decimal digits is 0.429. (Note that it got rounded up.)
Thus, S is 0.429.

Sample Input 3

2 1

Sample Output 3

0.500

\dfrac{B}{A} = \dfrac{1}{2} = 0.5 rounded off to three decimal digits is again 0.5.
Thus, S is 0.500. Note that it must have three decimal places.

Sample Input 4

10 10

Sample Output 4

1.000

Sample Input 5

1 0

Sample Output 5

0.000

Problem Statement

Takahashi had his N-th birthday, when he was T centimeters tall.
Additionally, we know the following facts:

• In each year between Takahashi's birth (0-th birthday) and his X-th birthday, his height increased by D centimeters. More formally, for each i = 1, 2, \ldots, X, his height increased by D centimeters between his (i-1)-th birthday and his i-th birthday.
• Between Takahashi's X-th birthday and his N-th birthday, his height did not change.

Find Takahashi's height on his M-th birthday, in centimeters.

Constraints

• 0 \leq M \lt N \leq 100
• 1 \leq X \leq N
• 1 \leq T \leq 200
• 1 \leq D \leq 100
• Takahashi was at least 1 centimeter tall at his birth.
• All values in input are integers.

Sample Input 1

38 20 17 168 3

Sample Output 1

168

In this sample, Takahashi was 168 centimeters tall on his 38-th birthday. Also, his height did not change between his 17-th birthday and 38-th birthday.
From these facts, we find that he was 168 centimeters tall on his 20-th birthday, so the answer is 168.

Sample Input 2

1 0 1 3 2

Sample Output 2

1

In this sample, Takahashi was 1 centimeter tall on his 0(=M)-th birthday and 3(=T) centimeters tall on his 1(=N)-st birthday.

Sample Input 3

100 10 100 180 1

Sample Output 3

90

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

• 2 \leq N \leq 100
• A_{i,j} \in \lbrace 0,1 \rbrace
• A_{i,i} = 0
• A_{i,j} = A_{j,i}
• All input values are integers.

Sample Input 1

4
0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Sample Output 1

2 3
1 4
1
2

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

5
0 1 0 1 1
1 0 0 1 0
0 0 0 0 1
1 1 0 0 1
1 0 1 1 0

Sample Output 3

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

Problem Statement

There are two grids S and T, each with N rows and N columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell of grids S and T is colored either white or black. Cell (i,j) of S is white if S_{i,j} is ., and black if S_{i,j} is #. The same applies to T.

You may perform the following two types of operations any number of times in any order. Find the minimum number of operations required to make grid S identical to grid T.

• Choose one cell of grid S and change its color.
• Rotate the entire grid S 90 degrees clockwise.

Constraints

• 1 \le N \le 100
• N is an integer.
• Each of S_{i,j} and T_{i,j} is . or #.

Sample Input 1

4
###.
..#.
..#.
..#.
...#
...#
###.
....

Sample Output 1

2

You can match S to T in two operations as shown below.

Sample Input 2

13
.#..###..##..
#.#.#..#.#.#.
#.#.###..#...
###.#..#.#.#.
#.#.###..##..
.............
..#...#....#.
.##..#.#..##.
#.#..#.#.#.#.
####.#.#.####
..#..#.#...#.
..#...#....#.
.............
.............
.#....#...#..
.#...#.#..#..
####.#.#.####
.#.#.###..#.#
.##....#..##.
.#....#...#..
.............
..##..###.#.#
.#.#.#..#.###
.#.#..###.#.#
.#.#.#..#.#.#
..##..###..#.

Sample Output 2

5

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq A_i \leq 10^{9}
• 1 \leq C_i \leq 10^{9}
• All input values are integers.

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

There is a pond with a circumference of M, and on its shore stand one hut and N people.
For a real number x (0\leq x <M), define point x as the location that is x distance clockwise from the hut.
The i-th person is at point A_i. Multiple people may be standing at the same location.

Additionally, an integer C not greater than N is given. For i=0,1,\ldots,M-1, define X_i as follows:

1. Takahashi starts at point (i+0.5) and begins moving clockwise.
2. Takahashi continues moving (clockwise) as long as the total number of people he has met is less than C, and stops when it becomes C or more. Here, "meeting a person at point y" means that Takahashi reaches point y.
3. Let X_i be the number of people Takahashi met before stopping. Here, if there are multiple people at the point where Takahashi stopped, all the people there are counted as people he met, and particularly, X_i may be greater than C.

Find the sum of X_i over i=0,1,\ldots,M-1, that is, \displaystyle\sum_{i=0}^{M-1} X_i.

Constraints

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

Sample Input 1

5 3 2
1 2 1 0 1

Sample Output 1

9

When i=0, Takahashi starts at point 0.5 and moves clockwise. Then, the following happens:

• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 3. This is not less than C=2, so Takahashi stops there. Therefore, X_0=3.

When i=1, Takahashi starts at point 1.5 and moves clockwise. Then, the following happens:

• At point 2, he meets the 2nd person. The total number of people met so far is 1, so he continues moving.
• At point 0, he meets the 4th person, and the total number of people met so far is 2. This is not less than C=2, so Takahashi stops there. Therefore, X_1=2.

When i=2, Takahashi starts at point 2.5 and moves clockwise. Then, the following happens:

• At point 0, he meets the 4th person. The total number of people met so far is 1, so he continues moving.
• At point 1, he meets the 1st, 3rd, and 5th people, a total of three people, and the total number of people met so far is 4. This is not less than C=2, so Takahashi stops there. Therefore, X_2=4.

Therefore, the answer is X_0+X_1+X_2=3+2+4=9.

Sample Input 2

1 1000000000000 1
1

Sample Output 2

1000000000000

Regardless of the starting position, Takahashi stops when he meets the only person standing around the pond, who is at point 1.
Therefore, X_i=1 regardless of i, and the answer is 10^{12}.

Problem Statement

Given is a weighted undirected connected graph G with N vertices and M edges, which may contain self-loops and multi-edges.
The vertices are labeled as Vertex 1, Vertex 2, \dots, Vertex N.
The edges are labeled as Edge 1, Edge 2, \ldots, Edge M. Edge i connects Vertex a_i and Vertex b_i and has a weight of c_i. Here, for every pair of integers (i, j) such that 1 \leq i \lt j \leq M, c_i \neq c_j holds.

Process the Q queries explained below.
The i-th query gives a triple of integers (u_i, v_i, w_i). Here, for every integer j such that 1 \leq j \leq M, w_i \neq c_j holds.
Let e_i be an undirected edge that connects Vertex u_i and Vertex v_i and has a weight of w_i. Consider the graph G_i obtained by adding e_i to G. It can be proved that the minimum spanning tree T_i of G_i is uniquely determined. Does T_i contain e_i? Print the answer as Yes or No.

Note that the queries do not change T. In other words, even though Query i considers the graph obtained by adding e_i to G, the G in other queries does not have e_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N - 1 \leq M \leq 2 \times 10^5
• 1 \leq a_i \leq N (1 \leq i \leq M)
• 1 \leq b_i \leq N (1 \leq i \leq M)
• 1 \leq c_i \leq 10^9 (1 \leq i \leq M)
• c_i \neq c_j (1 \leq i \lt j \leq M)
• The graph G is connected.
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq u_i \leq N (1 \leq i \leq Q)
• 1 \leq v_i \leq N (1 \leq i \leq Q)
• 1 \leq w_i \leq 10^9 (1 \leq i \leq Q)
• w_i \neq c_j (1 \leq i \leq Q, 1 \leq j \leq M)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

Yes
No
Yes

Below, let (u,v,w) denote an undirected edge that connects Vertex u and Vertex v and has the weight of w. Here is an illustration of G:

For example, Query 1 considers the graph G_1 obtained by adding e_1 = (1,3,1) to G. The minimum spanning tree T_1 of G_1 has the edge set \lbrace (1,2,2),(1,3,1),(2,4,5),(3,5,8) \rbrace, which contains e_1, so Yes should be printed.

Sample Input 2

2 3 2
1 2 100
1 2 1000000000
1 1 1
1 2 2
1 1 5

Sample Output 2

Yes
No

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges. (A graph is said to be simple if it has no multi-edges and no self-loops.)
For i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.

A sequence (A_1, A_2, \ldots, A_k) is said to be a path of length k if both of the following two conditions are satisfied:

• For all i = 1, 2, \dots, k, it holds that 1 \leq A_i \leq N.
• For all i = 1, 2, \ldots, k-1, Vertex A_i and Vertex A_{i+1} are directly connected by an edge.

An empty sequence is regarded as a path of length 0.

Let S = s_1s_2\ldots s_N be a string of length N consisting of 0 and 1. A path A = (A_1, A_2, \ldots, A_k) is said to be a good path with respect to S if the following conditions are satisfied:

• For all i = 1, 2, \ldots, N, it holds that:
  • if s_i = 0, then A has even number of i's.
  • if s_i = 1, then A has odd number of i's.

There are 2^N possible S (in other words, there are 2^N strings of length N consisting of 0 and 1). Find the sum of "the length of the shortest good path with respect to S" over all those S.

Under the Constraints of this problem, it can be proved that, for any string S of length N consisting of 0 and 1, there is at least one good path with respect to S.

Constraints

• 2 \leq N \leq 17
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq u_i, v_i \leq N
• The given graph is simple and connected.
• All values in input are integers.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

14

• For S = 000, the empty sequence () is the shortest good path with respect to S, whose length is 0.
• For S = 100, (1) is the shortest good path with respect to S, whose length is 1.
• For S = 010, (2) is the shortest good path with respect to S, whose length is 1.
• For S = 110, (1, 2) is the shortest good path with respect to S, whose length is 2.
• For S = 001, (3) is the shortest good path with respect to S, whose length is 1.
• For S = 101, (1, 2, 3, 2) is the shortest good path with respect to S, whose length is 4.
• For S = 011, (2, 3) is the shortest good path with respect to S, whose length is 2.
• For S = 111, (1, 2, 3) is the shortest good path with respect to S, whose length is 3.

Therefore, the sought answer is 0 + 1 + 1 + 2 + 1 + 4 + 2 + 3 = 14.

Sample Input 2

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

Sample Output 2

108