Problem Statement

There are four cards with integers A,B,C,D written on them.
Determine whether a Full House can be formed by adding one card.

A set of five cards is called a Full House if and only if the following condition is satisfied:

• For two distinct integers x and y, there are three cards with x written on them and two cards with y written on them.

Constraints

• All input values are integers.
• 1 \le A,B,C,D \le 13

Sample Input 1

7 7 7 1

Sample Output 1

Yes

Adding 1 to 7,7,7,1 forms a Full House.

Sample Input 2

13 12 11 10

Sample Output 2

No

Adding anything to 13,12,11,10 does not form a Full House.

Sample Input 3

3 3 5 5

Sample Output 3

Yes

Adding 3,3,5,5 to 3 forms a Full House.
Also, adding 5 forms a Full House.

Sample Input 4

8 8 8 8

Sample Output 4

No

Adding anything to 8,8,8,8 does not form a Full House.
Note that five identical cards do not form a Full House.

Sample Input 5

1 3 4 1

Sample Output 5

No

Problem Statement

There is a calculator with the buttons 00, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
When a string x is displayed on this calculator and you press a button b, the resulting displayed string becomes the string x with b appended to its end.

Initially, the calculator displays the empty string (a string of length 0).
Find the minimum number of button presses required to display the string S on this calculator.

Constraints

• S is a string of length at least 1 and at most 1000, consisting of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.
• The first character of S is not 0.

Sample Input 1

1000000007

Sample Output 1

6

To display 1000000007, you can press the buttons 1, 00, 00, 00, 00, 7 in this order. The total number of button presses is 6, and this is the minimum possible.

Sample Input 2

998244353

Sample Output 2

9

Sample Input 3

32000

Sample Output 3

4

Problem Statement

This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• \color{red}{K=1}

Sample Input 1

1
abc
agc

Sample Output 1

Yes

Replacing the second character b of abc with g converts abc to agc in one operation.

Sample Input 2

1
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf in one operation.

Sample Input 3

1
abc
ac

Sample Output 3

Yes

Deleting the second character b of abc converts abc to ac in one operation.

Sample Input 4

1
back
black

Sample Output 4

Yes

Inserting l between the first and second characters of back converts back to black in one operation.

Sample Input 5

1
same
same

Sample Output 5

Yes

It is also possible that S = T from the beginning.

Sample Input 6

1
leap
read

Sample Output 6

No

Problem Statement

There is an N \times N grid. Takahashi wants to color each cell black or white so that all of the following conditions are satisfied:

• For every row, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the leftmost i cells are colored black, and the rest are colored white.
• For every column, the following condition holds:
• There exists an integer i\ (0\leq i\leq N) such that the topmost i cells are colored black, and the rest are colored white.

Out of these N^2 cells, M of them have already been colored. Among them, the i-th one is at the X_i-th row from the top and the Y_i-th column from the left, and it is colored black if C_i is B and white if C_i is W.

Determine whether he can color the remaining uncolored N^2 - M cells so that all the conditions are satisfied.

Constraints

• 1\leq N\leq 10^9
• 1\leq M\leq \min(N^2,2\times 10^5)
• 1\leq X_i,Y_i\leq N
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• C_i is B or W.
• All input numbers are integers.

Sample Input 1

4 3
4 1 B
3 2 W
1 3 B

Sample Output 1

Yes

For example, one can color the grid as in the following figure to satisfy the conditions. The cells already colored are surrounded by red borders.

Sample Input 2

2 2
1 2 W
2 2 B

Sample Output 2

No

No matter how the remaining two cells are colored, the conditions cannot be satisfied.

Sample Input 3

1 1
1 1 W

Sample Output 3

Yes

Sample Input 4

2289 10
1700 1083 W
528 967 B
1789 211 W
518 1708 W
1036 779 B
136 657 B
759 1497 B
902 1309 B
1814 712 B
936 763 B

Sample Output 4

No

Problem Statement

You are given a sequence A of non-negative integers of length N, and an integer K. It is guaranteed that the binomial coefficient \dbinom{N}{K} is at most 10^6.

When choosing K distinct elements from A, find the maximum possible value of the XOR of the K chosen elements.

That is, find \underset{1\leq i_1\lt i_2\lt \ldots\lt i_K\leq N}{\max} A_{i_1}\oplus A_{i_2}\oplus \ldots \oplus A_{i_K}.

Constraints

• 1\leq K\leq N\leq 2\times 10^5
• 0\leq A_i<2^{60}
• \dbinom{N}{K}\leq 10^6
• All input values are integers.

Sample Input 1

4 2
3 2 6 4

Sample Output 1

7

Here are six ways to choose two distinct elements from (3,2,6,4).

• (3,2): The XOR is 3\oplus 2 = 1.
• (3,6): The XOR is 3\oplus 6 = 5.
• (3,4): The XOR is 3\oplus 4 = 7.
• (2,6): The XOR is 2\oplus 6 = 4.
• (2,4): The XOR is 2\oplus 4 = 6.
• (6,4): The XOR is 6\oplus 4 = 2.

Hence, the maximum possible value is 7.

Sample Input 2

10 4
1516 1184 1361 2014 1013 1361 1624 1127 1117 1759

Sample Output 2

2024

Problem Statement

This problem fully contains Problem C (Operate 1), with K \le 20.
You can solve Problem C by submitting a correct solution to this problem for Problem C.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• K is an integer satisfying \color{red}{1 \le K \le 20}.

Sample Input 1

3
abc
awtf

Sample Output 1

Yes

For example, here is a way to convert abc to awtf with three operations:

• Replace the second character b with w. After the operation, the string becomes awc.
• Replace the third character c with f. After the operation, the string becomes awf.
• Insert t between the second and third characters. After the operation, the string becomes awtf.

Sample Input 2

2
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf with two or fewer operations.

Sample Input 3

17
twothousandtwentyfour
happynewyear

Sample Output 3

Yes

Problem Statement

You are given positive integers N and M. Consider a weighted complete graph with N vertices labeled from 1 to N, where the weight of each edge is an integer between 1 and M, inclusive. There are M^{N(N-1)/2} such graphs. For each of them, consider the sum of the weights of the edges included in its Minimum Spanning Tree. What is the total of these sums? Print the result modulo 998244353.

Constraints

• 2 \le N \le 500
• 1 \le M \le 500
• All input values are integers.

Sample Input 1

3 2

Sample Output 1

21

Here are eight complete graphs with three vertices where edge weights are 1 or 2. The edges in each graph’s MST are highlighted in red in the figure below.

The sums of the MST edges for these graphs are 2,2,2,3,2,3,3,4, so the total is 2+2+2+3+2+3+3+4=21.

Sample Input 2

2 100

Sample Output 2

5050

Sample Input 3

20 24

Sample Output 3

707081320