Problem Statement

Takahashi eats three plates for breakfast: rice, miso soup, and salad.

His table is long and narrow, so he arranged the three plates in a row. The arrangement is given by a string S, where the i-th plate from the left is rice if S_i is R, miso soup if S_i is M, and salad if S_i is S.

Determine whether the plate of rice is to the left of the plate of miso soup.

Constraints

• |S| = 3
• S contains one R, one M, and one S.

Sample Input 1

RSM

Sample Output 1

Yes

The plate of rice is at the 1st position from the left, and the plate of miso soup is at the 3rd position from the left. Since the plate of rice is to the left, print Yes.

Sample Input 2

SMR

Sample Output 2

No

The plates are arranged as salad, miso soup, and rice from left to right.

Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

• 1 \leq N \leq 100
• N is an integer.
• Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.

Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.

Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

• N is an integer between 1 and 1000, inclusive.
• S is a string of length N consisting of lowercase English letters.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

• Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
• Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
• Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....

Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872

Problem Statement

There are N researchers, numbered 1, 2, \ldots, N.

There are M conflicts of interest among the researchers; for i = 1, 2, \ldots, M, researchers A_i and B_i have a conflict of interest with each other.

The reviewers of a paper must be three distinct researchers who are different from the author of the paper and have no conflict of interest with the author.

For i = 1, 2, \ldots, N, solve the following problem:

• Find the number of possible triples of reviewers for a paper authored by researcher i.

Assume that all papers are single-authored.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• (A_i, B_i) \neq (B_j, A_j) if i \neq j.
• All input values are integers.

Sample Input 1

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

Sample Output 1

0 1 0 4 4 10

Below, we represent a set of researchers by the set of their numbers.

• There are no possible triples of reviewers for a paper authored by researcher 1.

• The possible triple of reviewers for a paper authored by researcher 2 is \lbrace 4, 5, 6 \rbrace, which is 1 triple.

• There are no possible triples of reviewers for a paper authored by researcher 3.

• The possible triples of reviewers for a paper authored by researcher 4 are \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 5 are \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace, which is 4 triples.

• The possible triples of reviewers for a paper authored by researcher 6 are \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace, which is 10 triples.

Sample Input 2

7 3
1 2
3 4
5 6

Sample Output 2

10 10 10 10 10 10 20

Sample Input 3

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

Sample Output 3

1 0 0 1 0 1

Problem Statement

You observed amoebae and kept some records.

Initially, there was one amoeba, numbered 1.

You made N records. According to the i-th record, the amoeba numbered A_i disappeared by dividing itself into two new amoebae, which were then numbered 2i and 2i+1.
Here, amoeba A_i is said to be the parent of amoebae 2i and 2i+1.

For each k=1,\ldots,2N+1, how many generations away is amoeba k from amoeba 1?

Constraints

• 1 \leq N \leq 2\times 10^5
• The records are consistent. That is:
  • 1\leq A_i \leq 2i-1.
  • A_i are distinct integers.

Sample Input 1

2
1 2

Sample Output 1

0
1
1
2
2

From amoeba 1, amoebae 2 and 3 were born. From amoeba 2, amoebae 4 and 5 were born.

• Amoeba 1 is zero generations away from amoeba 1.
• Amoeba 2 is one generation away from amoeba 1.
• Amoeba 3 is one generation away from amoeba 1.
• Amoeba 4 is one generation away from amoeba 2, and two generations away from amoeba 1.
• Amoeba 5 is one generation away from amoeba 2, and two generations away from amoeba 1.

Sample Input 2

4
1 3 5 2

Sample Output 2

0
1
1
2
2
3
3
2
2

Problem Statement

A superman, Takahashi, is about to jump off the roof of a building to help a person in trouble on the ground. Takahashi's planet has a constant value g that represents the strength of gravity, and the time it takes for him to reach the ground after starting to fall is \frac{A}{\sqrt{g}}.

It is now time 0, and g = 1. Takahashi will perform the following operation as many times as he wants (possibly zero).

• Use a superpower to increase the value of g by 1. This takes a time of B.

Then, he will jump off the building. After starting to fall, he cannot change the value of g. Additionally, we only consider the time it takes to perform the operation and fall.

Find the earliest time Takahashi can reach the ground.

Constraints

• 1 \leq A \leq 10^{18}
• 1 \leq B \leq 10^{18}
• All values in the input are integers.

Sample Input 1

10 1

Sample Output 1

7.7735026919

• If he performs the operation zero times, he will reach the ground at time 1\times 0+\frac{10}{\sqrt{1}} = 10.
• If he performs the operation once, he will reach the ground at time 1\times 1+\frac{10}{\sqrt{2}} \fallingdotseq 8.07.
• If he performs the operation twice, he will reach the ground at time 1\times 2+\frac{10}{\sqrt{3}} \fallingdotseq 7.77.
• If he performs the operation three times, he will reach the ground at time 1\times 3+\frac{10}{\sqrt{4}} = 8.

Performing the operation four or more times will only delay the time to reach the ground. Therefore, it is optimal to perform the operation twice before jumping off, and the answer is 2+\frac{10}{\sqrt{3}}.

Sample Input 2

5 10

Sample Output 2

5.0000000000

It is optimal not to perform the operation at all.

Sample Input 3

1000000000000000000 100

Sample Output 3

8772053214538.5976562500

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges.
Edge i connects Vertex A_i and Vertex B_i, and has a length of C_i.

Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

• The graph is still connected after the deletion.
• For every pair of vertices (s, t), the distance between s and t remains the same before and after the deletion.

Notes

A simple connected undirected graph is a graph that is simple and connected and has undirected edges.
A graph is simple when it has no self-loops and no multi-edges.
A graph is connected when, for every pair of two vertices s and t, t is reachable from s by traversing edges.
The distance between Vertex s and Vertex t is the length of a shortest path between s and t.

Constraints

• 2 \leq N \leq 300
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i \lt B_i \leq N
• 1 \leq C_i \leq 10^9
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• The given graph is connected.
• All values in input are integers.

Sample Input 1

3 3
1 2 2
2 3 3
1 3 6

Sample Output 1

1

The distance between each pair of vertices before the deletion is as follows.

• The distance between Vertex 1 and Vertex 2 is 2.
• The distance between Vertex 1 and Vertex 3 is 5.
• The distance between Vertex 2 and Vertex 3 is 3.

Deleting Edge 3 does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is 1.

Sample Input 2

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

Sample Output 2

0

No edge can be deleted.

Sample Input 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

Sample Output 3

5

Problem Statement

In an N-dimensional space, the Manhattan distance d(x,y) between two points x=(x_1, x_2, \dots, x_N) and y = (y_1, y_2, \dots, y_N) is defined by:

A point x=(x_1, x_2, \dots, x_N) is said to be a lattice point if the components x_1, x_2, \dots, x_N are all integers.

You are given lattice points p=(p_1, p_2, \dots, p_N) and q = (q_1, q_2, \dots, q_N) in an N-dimensional space.
How many lattice points r satisfy d(p,r) \leq D and d(q,r) \leq D? Find the count modulo 998244353.

Constraints

• 1 \leq N \leq 100
• 0 \leq D \leq 1000
• -1000 \leq p_i, q_i \leq 1000
• All values in input are integers.

Sample Input 1

1 5
0
3

Sample Output 1

8

When N=1, we consider points in a one-dimensional space, that is, on a number line.
8 lattice points satisfy the conditions: -2,-1,0,1,2,3,4,5.

Sample Input 2

3 10
2 6 5
2 1 2

Sample Output 2

632

Sample Input 3

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

Sample Output 3

145428186