Problem Statement

There is a grid with 10^{100} rows and 10^{100} columns.
In what follows, the cell at the i-th row from the top and j-th column from the left is denoted as cell (i,j).

In this grid, only the 100\times 100 region with cell (P,Q) as the top-left cell is painted black, and all other cells are painted white.
Determine whether cell (X,Y) is painted black.

Constraints

• 1 \leq P,Q,X,Y \leq 10000
• P,Q,X,Y are integers.

Sample Input 1

3 3
5 10

Sample Output 1

Yes

The 100\times 100 region with cell (3,3) as the top-left cell is painted black.
Cell (5,10) is included in this region, so print Yes.

Sample Input 2

5 5
10 1000

Sample Output 2

No

The 100\times 100 region with cell (5,5) as the top-left cell is painted black.
Cell (10,1000) is not included in this region, so print No.

Sample Input 3

1 2
1 1

Sample Output 3

No

The 100\times 100 region with cell (1,2) as the top-left cell is painted black.
Cell (1,1) is not included in this region, so print No.

Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

• 1\leq N \leq 100
• 1\leq H_i \leq 10^9
• All H_i are different.
• All values in the input are integers.

Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.

Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.

Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

Problem Statement

You are given N strings S_1,S_2,\ldots,S_N consisting of lowercase English letters.
Determine if there are distinct integers i and j between 1 and N, inclusive, such that the concatenation of S_i and S_j in this order is a palindrome.

A string T of length M is a palindrome if and only if the i-th character and the (M+1-i)-th character of T are the same for every 1\leq i\leq M.

Constraints

• 2\leq N\leq 100
• 1\leq \lvert S_i\rvert \leq 50
• N is an integer.
• S_i is a string consisting of lowercase English letters.
• All S_i are distinct.

Sample Input 1

5
ab
ccef
da
a
fe

Sample Output 1

Yes

If we take (i,j)=(1,4), the concatenation of S_1=ab and S_4=a in this order is aba, which is a palindrome, satisfying the condition.
Thus, print Yes.

Here, we can also take (i,j)=(5,2), for which the concatenation of S_5=fe and S_2=ccef in this order is feccef, satisfying the condition.

Sample Input 2

3
a
b
aba

Sample Output 2

No

No two distinct strings among S_1, S_2, and S_3 form a palindrome when concatenated. Thus, print No.
Note that the i and j in the statement must be distinct.

Sample Input 3

2
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Sample Output 3

Yes

Problem Statement

There are three dice, each with six faces.
The j-th face of the i-th die has A_{i,j} written on it.
For each die, each face comes up with probability \frac{1}{6}.

When these dice are rolled simultaneously, find the probability that the values 4,5,6 each appear exactly once.

Constraints

• A_{i,j} is an integer between 1 and 6, inclusive.

Sample Input 1

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

Sample Output 1

0.0277777778

The desired probability is \frac{1}{36}. An output such as 0.027778 is also accepted.

Sample Input 2

4 5 6 4 5 6
4 4 5 5 6 6
6 5 4 4 5 6

Sample Output 2

0.2222222222

The desired probability is \frac{2}{9}.

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

• 1\le A_i \le M (1 \le i \le N)

• \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

• 1 \leq N, M \leq 50
• N \leq K \leq NM
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

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

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

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

Sample Input 1

5 3
1 2
1 3
4 5

Sample Output 1

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
• a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

5

Sample Input 3

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

Sample Output 3

1

Problem Statement

This problem is a subproblem of Problem G.

A non-empty string S consisting of 0 and 1 is called a beautiful string when it satisfies the following condition:

• (Condition) You can perform the following sequence of operations until the length of S becomes 1 and make the only character remaining in S be 1.
  1. Choose any integer i satisfying 1 \leq i \leq |S| - 1.
  2. Define an integer x as follows:
     • If S_i = 0 and S_{i+1} = 0, let x = 1.
     • If S_i = 0 and S_{i+1} = 1, let x = 0.
     • If S_i = 1 and S_{i+1} = 0, let x = 0.
     • If S_i = 1 and S_{i+1} = 1, let x = 1.
  3. Remove S_i and S_{i+1}, and insert the digit corresponding to x in their place.
     For example, if S= 10101 and you choose i=2, the string after the operation is 1001.

You are given a string T of length N consisting of 0 and 1.
Find the number of beautiful strings that are substrings of T. Even if two substrings are identical as strings, count them separately if they are taken from different positions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
110

Sample Output 1

3

The string 11 obtained by taking the 1st through 2nd characters of T is a beautiful string, because if you choose i=1 and perform the operation, the string becomes 1. The beautiful strings that are substrings of T are the following three strings:

• The string 1 obtained by taking the 1st character of T.
• The string 1 obtained by taking the 2nd character of T.
• The string 11 obtained by taking the 1st through 2nd characters of T.

Sample Input 2

4
0000

Sample Output 2

4

Sample Input 3

30
011011100101110111100010011010

Sample Output 3

225

Problem Statement

Takahashi has a playlist with N songs. Song i (1 \leq i \leq N) lasts T_i seconds.
Takahashi has started random play of the playlist at time 0.

Random play repeats the following: choose one song from the N songs with equal probability and play that song to the end. Here, songs are played continuously: once a song ends, the next chosen song starts immediately. The same song can be chosen consecutively.

Find the probability that song 1 is being played (X + 0.5) seconds after time 0, modulo 998244353.

Constraints

• 2 \leq N\leq 10^3
• 0 \leq X\leq 10^4
• 1 \leq T_i\leq 10^4
• All input values are integers.

Sample Input 1

3 6
3 5 6

Sample Output 1

369720131

Song 1 will be playing 6.5 seconds after time 0 if songs are played in one of the following orders.

• Song 1 \to Song 1 \to Song 1
• Song 2 \to Song 1
• Song 3 \to Song 1

The probability that one of these occurs is \frac{7}{27}.
We have 369720131\times 27\equiv 7 \pmod{998244353}, so you should print 369720131.

Sample Input 2

5 0
1 2 1 2 1

Sample Output 2

598946612

0.5 seconds after time 0, the first song to be played is still playing, so the sought probability is \frac{1}{5}.
Note that different songs may have the same length.

Sample Input 3

5 10000
1 2 3 4 5

Sample Output 3

586965467

Problem Statement

There are N cat towers arranged in a row from left to right, and the height of the i-th tower from the left (1\leq i\leq N) is P_i.
Here, (P_1,P_2,\ldots,P_N) is a permutation of (1,2,\ldots,N).
The distance between the i-th tower and the j-th tower from the left is defined as \lvert i-j\rvert.

There is one cat, initially on top of the cat tower of height N.
Takahashi wants to exercise this cat by repeatedly choosing and removing towers.

When Takahashi removes a tower, the cat moves as follows:

• If the cat is not on top of the tower being removed, the cat does not move.
• If the cat is on top of the tower being removed and at least one of the towers adjacent to the left or right of that tower exists, the cat moves to the tallest tower (excluding the tower being removed) among the towers that can be reached by repeatedly moving to adjacent towers starting from the tower being removed. At this time, the cat moves the distance between the tower before movement and the tower after movement (the heights of the towers before, after, and during movement do not matter).
• If the cat is on top of the tower being removed and no towers adjacent to the left or right of that tower exist, the cat jumps into Takahashi's arms, and the exercise ends here. In this case, no movement occurs.

Here, the spaces between removed towers are not filled in. That is, the towers adjacent to the i-th tower from the left initially are only the (i-1)-th and (i+1)-th towers from the left (if they exist), and they will never become adjacent to other towers due to the removal of other towers afterward.

Find the maximum possible total distance the cat moves before the exercise ends.

Constraints

• 1\leq N\leq 2\times 10^5
• (P_1,P_2,\ldots, P_N) is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

5
5 3 4 1 2

Sample Output 1

5

Initially, the heights of the cat towers are 5,3,4,1,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 5) is called tower i.
Initially, the cat is on tower 1 (height 5).

If Takahashi removes towers in the order 1,2,3,5,4, the cat moves as follows:

• Takahashi removes tower 1. The towers that can be reached by only moving to adjacent towers from tower 1 are towers 2,3,4,5 (excluding tower 1). The cat moves to tower 3 (height 4), which is the tallest among them.
• Takahashi removes tower 2. The cat does not move.
• Takahashi removes tower 3. The towers that can be reached by only moving to adjacent towers from tower 3 are towers 4,5 (excluding tower 3). The cat moves to tower 5 (height 2), which is the tallest among them.
• Takahashi removes tower 5. The towers that can be reached by only moving to adjacent towers from tower 5 are only tower 4 (excluding tower 5). The cat moves to tower 4 (height 1).
• Takahashi removes tower 4. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 1-3\rvert+\lvert 3-5\rvert+\lvert 5-4\rvert=5. There is no way to remove towers that makes the total distance moved 6 or more, so output 5.

Sample Input 2

3
1 3 2

Sample Output 2

1

Initially, the heights of the cat towers are 1,3,2 from left to right.
Hereafter, the i-th cat tower from the left (1\leq i\leq 3) is called tower i.
Initially, the cat is on tower 2 (height 3).

If Takahashi removes towers in the order 2,3, the cat moves as follows:

• Takahashi removes tower 2. The towers that can be reached by only moving to adjacent towers from tower 2 are towers 1,3 (excluding tower 2). The cat moves to tower 3 (height 2), which is the tallest among them.
• Takahashi removes tower 3. The cat jumps into Takahashi's arms, and the exercise ends.

Here, the cat moves the total distance of \lvert 2-3\rvert=1, which is the maximum.
Note that after removing tower 2, tower 1 and tower 3 are not considered to be adjacent.