Problem Statement

You are given two strings S and T consisting of lowercase English letters. Here, S and T have equal lengths.

Let X be an empty array, and repeat the following operation until S equals T:

• Change one character in S, and append S to the end of X.

Find the array of strings X with the minimum number of elements obtained in this way. If there are multiple such arrays with the minimum number of elements, find the lexicographically smallest one among them.

Constraints

• S and T are strings consisting of lowercase English letters with length between 1 and 100, inclusive.
• The lengths of S and T are equal.

Sample Input 1

adbe
bcbc

Sample Output 1

3
acbe
acbc
bcbc

Initially, S = adbe.

We can obtain X = ( acbe , acbc , bcbc ) by performing the following operations:

• Change S to acbe and append acbe to the end of X.

• Change S to acbc and append acbc to the end of X.

• Change S to bcbc and append bcbc to the end of X.

Sample Input 2

abcde
abcde

Sample Output 2

0

Sample Input 3

afwgebrw
oarbrenq

Sample Output 3

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

Problem Statement

You have N socks. The color of the i-th sock is A_i.

You want to perform the following operation as many times as possible. How many times can it be performed at most?

• Choose two same-colored socks that are not paired yet, and pair them.

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq A_i \leq 10^9
• All values in the input are integers.

Sample Input 1

6
4 1 7 4 1 4

Sample Output 1

2

You can do the operation twice as follows.

• Choose two socks with the color 1 and pair them.
• Choose two socks with the color 4 and pair them.

Then, you will be left with one sock with the color 4 and another with the color 7, so you can no longer do the operation. There is no way to do the operation three or more times, so you should print 2.

Sample Input 2

1
158260522

Sample Output 2

0

Sample Input 3

10
295 2 29 295 29 2 29 295 2 29

Sample Output 3

4

Problem Statement

You are given positive integers N and M.
Find the smallest positive integer X that satisfies both of the conditions below, or print -1 if there is no such integer.

• X can be represented as the product of two integers a and b between 1 and N, inclusive. Here, a and b may be the same.
• X is at least M.

Constraints

• 1\leq N\leq 10^{12}
• 1\leq M\leq 10^{12}
• N and M are integers.

Sample Input 1

5 7

Sample Output 1

8

First, 7 cannot be represented as the product of two integers between 1 and 5.
Second, 8 can be represented as the product of two integers between 1 and 5, such as 8=2\times 4.

Thus, you should print 8.

Sample Input 2

2 5

Sample Output 2

-1

Since 1\times 1=1, 1\times 2=2, 2\times 1=2, and 2\times 2=4, only 1, 2, and 4 can be represented as the product of two integers between 1 and 2, so no number greater than or equal to 5 can be represented as the product of two such integers.
Thus, you should print -1.

Sample Input 3

100000 10000000000

Sample Output 3

10000000000

For a=b=100000 (=10^5), the product of a and b is 10000000000 (=10^{10}), which is the answer.
Note that the answer may not fit into a 32-bit integer type.

Problem Statement

There are N towns numbered 1, \dots, N, and M roads numbered 1, \dots, M.
Every road is directed; road i (1 \leq i \leq M) leads you from Town A_i to Town B_i. The length of road i is C_i.

You are given a sequence E = (E_1, \dots, E_K) of length K consisting of integers between 1 and M. A way of traveling from town 1 to town N using roads is called a good path if:

• the sequence of the roads' numbers arranged in the order used in the path is a subsequence of E.

Note that a subsequence of a sequence is a sequence obtained by removing 0 or more elements from the original sequence and concatenating the remaining elements without changing the order.

Find the minimum sum of the lengths of the roads used in a good path.
If there is no good path, report that fact.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M, K \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq N, A_i \neq B_i \, (1 \leq i \leq M)
• 1 \leq C_i \leq 10^9 \, (1 \leq i \leq M)
• 1 \leq E_i \leq M \, (1 \leq i \leq K)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

4

There are two possible good paths as follows:

• Using road 4. In this case, the sum of the length of the used road is 5.
• Using road 1 and 2 in this order. In this case, the sum of the lengths of the used roads is 2 + 2 = 4.

Therefore, the desired minimum value is 4.

Sample Input 2

3 2 3
1 2 1
2 3 1
2 1 1

Sample Output 2

-1

There is no good path.

Sample Input 3

4 4 5
3 2 2
1 3 5
2 4 7
3 4 10
2 4 1 4 3

Sample Output 3

14

Problem Statement

Takahashi is participating in a lottery.

Each time he takes a draw, he gets one of the N prizes available. Prize i is awarded with probability \frac{W_i}{\sum_{j=1}^{N}W_j}. The results of the draws are independent of each other.

What is the probability that he gets exactly M different prizes from K draws? Find it modulo 998244353.

Note

To print a rational number, start by representing it as a fraction \frac{y}{x}. Here, x and y should be integers, and x should not be divisible by 998244353 (under the Constraints of this problem, such a representation is always possible). Then, print the only integer z between 0 and 998244352 (inclusive) such that xz\equiv y \pmod{998244353}.

Constraints

• 1 \leq K \leq 50
• 1 \leq M \leq N \leq 50
• 0 < W_i
• 0 < W_1 + \ldots + W_N < 998244353
• All values in input are integers.

Sample Input 1

2 1 2
2
1

Sample Output 1

221832079

Each draw awards Prize 1 with probability \frac{2}{3} and Prize 2 with probability \frac{1}{3}.

He gets Prize 1 at both of the two draws with probability \frac{4}{9}, and Prize 2 at both draws with probability \frac{1}{9}, so the sought probability is \frac{5}{9}.

The modulo 998244353 representation of this value, according to Note, is 221832079.

Sample Input 2

3 3 2
1
1
1

Sample Output 2

0

It is impossible to get three different prizes from two draws, so the sought probability is 0.

Sample Input 3

3 3 10
499122176
499122175
1

Sample Output 3

335346748

Sample Input 4

10 8 15
1
1
1
1
1
1
1
1
1
1

Sample Output 4

755239064