Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

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

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

• Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 2 \leq M \leq 2 \times 10^5
• 1 \leq k_i\ (1 \leq i \leq M)
• 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
• \sum_{i=1}^{M} k_i = 2N
• For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
• All values in input are integers.

Sample Input 1

2 2
2
1 2
2
1 2

Sample Output 1

Yes

The objective can be achieved as follows.

1. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
2. Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

2 2
2
1 2
2
2 1

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

• 2 \leq N,M \leq 10^6
• N and M are integers.

Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

Problem Statement

We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.

Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.

There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 10^6
• All input values are integers.

Sample Input 1

4
1 7 2 9

Sample Output 1

942786334

For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.

On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.

In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.

Sample Input 2

7
1 10 100 1000 10000 100000 1000000

Sample Output 2

996117877