Problem Statement

Determine whether there is a string S of length N consisting of X and Y that satisfies the following condition.

Condition: Among the (N - 1) pairs of consecutive characters in S,

• exactly A are XX,
• exactly B are XY,
• exactly C are YX, and
• exactly D are YY.

Constraints

• 1 \leq N \leq 2 \times 10^5
• A \geq 0
• B \geq 0
• C \geq 0
• D \geq 0
• A + B + C + D = N - 1

Sample Input 1

5 1 1 1 1

Sample Output 1

Yes

For instance, if S = {}XXYYX, the pairs of consecutive characters are XX, XY, YY, and YX from left to right. Each pattern occurs exactly once, so the condition is satisfied.

Sample Input 2

5 1 2 1 0

Sample Output 2

Yes

For instance, S = {}XXYXY satisfies the condition.

Sample Input 3

5 0 4 0 0

Sample Output 3

No

No string satisfies the condition.

Problem Statement

You are given a string S of length N consisting of X and Y. You will choose K characters at distinct positions in S and change each of them: X becomes Y and Y becomes X. Find the maximum possible number of pairs of consecutive Ys in the resulting string.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq K \leq N
• S is a string of length N consisting of X and Y.

Sample Input 1

5 1
XYXYX

Sample Output 1

2

You will choose one character.

• If you choose the 1-st character, the resulting string is YYXYX, with one pair of consecutive Ys at positions 1, 2.
• If you choose the 2-nd character, the resulting string is XXXYX, with no pair of consecutive Ys.
• If you choose the 3-rd character, the resulting string is XYYYX, with two pairs of consecutive Ys at positions 2, 3 and 3, 4.
• If you choose the 4-th character, the resulting string is XYXXX, with no pair of consecutive Ys.
• If you choose the 5-th character, the resulting string is XYXYY, with one pair of consecutive Ys at positions 4, 5.

Thus, the sought maximum number is 2.

Sample Input 2

5 4
XYXYX

Sample Output 2

2

It is optimal to choose the 1-st, 2-nd, 3-rd, and 5-th characters to get YXYYY, or choose the 1-st, 3-rd, 4-th, and 5-th characters to get YYYXY. Note that you may not choose a character at the same position multiple times.

Problem Statement

There is a grid with H rows and W columns where each square has one of the characters X and Y written on it. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. The characters on the grid are given as H strings S_1, S_2, \dots, S_H: the j-th character of S_i is the character on square (i, j).

For a path P from square (1, 1) to square (H, W) obtained by repeatedly moving down or right to the adjacent square, the score is defined as follows.

• Let \mathrm{str}(P) be the string of length (H + W - 1) obtained by concatenating the characters on the squares visited by P in the order they are visited.
• The score of P is the square of the number of pairs of consecutive Ys in \mathrm{str}(P).

There are \displaystyle\binom{H + W - 2}{H - 1} such paths. Find the sum of the scores over all those paths, modulo 998244353.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• S_i \ (1 \leq i \leq H) is a string of length W consisting of X and Y.

Sample Input 1

2 2
YY
XY

Sample Output 1

4

There are two possible paths P: (1, 1) \to (1, 2) \to (2, 2) and (1, 1) \to (2, 1) \to (2, 2).

• For (1, 1) \to (1, 2) \to (2, 2), we have \mathrm{str}(P) = {}YYY, with two pairs of consecutive Ys at positions 1, 2 and 2, 3, so the score is 2^2 = 4.
• For (1, 1) \to (2, 1) \to (2, 2), we have \mathrm{str}(P) = {}YXY, with no pairs of consecutive Ys , so the score is 0^2 = 0.

Thus, the sought sum is 4 + 0 = 4.

Sample Input 2

2 2
XY
YY

Sample Output 2

2

For either of the two possible paths P, we have \mathrm{str}(P) = {}XYY, for a score of 1^2 = 1.

Sample Input 3

10 20
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY
YYYYYYYYYYYYYYYYYYYY

Sample Output 3

423787835

Print the sum of the scores modulo 998244353.

Problem Statement

There is a grid with H rows and W columns where each square has one of the characters X and Y written on it. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. The characters on the grid are given as H strings S_1, S_2, \dots, S_H: the j-th character of S_i is the character on square (i, j).

You can set up fences across the grid between adjacent rows and columns. Fences may intersect. After setting up fences, a block is defined as the set of squares reachable from some square by repeatedly moving up, down, left, or right to the adjacent square without crossing fences. (See also Sample Output 1.)

There are 2^{H-1} \times 2^{W-1} ways to set up fences. How many of them satisfy the following condition, modulo 998244353?

Condition: Each block has exactly two squares with Y written on it.

Constraints

• 1 \leq H \leq 2000
• 1 \leq W \leq 2000
• S_i \ (1 \leq i \leq H) is a string of length W consisting of X and Y.

Sample Input 1

2 3
XYY
YXY

Sample Output 1

2

Below are the eight ways to set up fences.

X Y Y    X|Y Y    X Y|Y    X|Y|Y
          |          |      | |
Y X Y    Y|X Y    Y X|Y    Y|X|Y


X Y Y    X|Y Y    X Y|Y    X|Y|Y
-----    -+---    ---+-    -+-+-
Y X Y    Y|X Y    Y X|Y    Y|X|Y

For instance, if a fence is set up between the 2-nd and 3-rd columns, the blocks are:

XY
YX

Y
Y

Each of these blocks has exactly two Ys, so the condition is satisfied.

If a fence is set up between the 1-st and 2-nd rows and the 1-st and 2-nd columns, the blocks are:

X

YY

Y

XY

These blocks, except the second, do not have exactly two Ys, so the condition is not satisfied.

Sample Input 2

2 3
XYX
YYY

Sample Output 2

0

There is no way to set up fences to satisfy the condition.

Sample Input 3

2 58
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY
YXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXYXXY

Sample Output 3

164036797

Print the number of ways modulo 998244353.

Problem Statement

You are given a rooted tree with N vertices. The vertices are numbered 1 to N, and the root is vertex 1. The parent of each vertex i except the root is vertex P_i. Each vertex, including the root, has no child or exactly two children.

Determine whether it is possible to write one of the characters X and Y on each vertex of the given tree to satisfy the following condition.

Condition: For each edge of the tree, consider the string of length 2 obtained by concatenating the characters written on the endpoints in the order from the parent P_i to the child i. Among the (N - 1) strings obtained in this way,

• exactly A are XX,
• exactly B are XY,
• exactly C are YX, and
• none is YY.

You have T test cases to solve.

Constraints

• T \geq 1
• N \geq 1
• For each input, the sum of N over the test cases is at most 10^4.
• A \geq 0
• B \geq 0
• C \geq 0
• A + B + C = N - 1
• 1 \leq P_i < i \ \ (2 \leq i \leq N)
• Each vertex k \ (1 \leq k \leq N) occurs as a parent P_i \ (2 \leq i \leq N) zero times or twice in total.

Sample Input 1

3
7 2 2 2
1 1 2 2 3 3
7 0 2 4
1 1 2 2 3 3
7 2 0 4
1 1 2 2 4 4

Sample Output 1

Yes
Yes
No

For the first test case, if you, for instance, write XXYXYXX in this order on vertices 1 to 7,

• from the edge (1, 2), we obtain XX,
• from the edge (1, 3), we obtain XY,
• from the edge (2, 4), we obtain XX,
• from the edge (2, 5), we obtain XY,
• from the edge (3, 6), we obtain YX, and
• from the edge (3, 7), we obtain YX.

Each of XX, XY, and YX occurs twice, so the condition is satisfied.

For the second case, one way to satisfy the condition is to write XYYXXXX.

For the third case, there is no way to satisfy the condition.

Problem Statement

You are given strings S and T of length N consisting of X and Y. For each i = 1, 2, \dots, N, you can swap the i-th character of S and the i-th character of T or choose not to do it. There are 2^N pairs of strings that can result from this process, including duplicates. Find the longest string that is a common subsequence (not necessarily contiguous) of one of such pairs. If there are multiple such strings, find the lexicographically smallest of them.

Constraints

• 1 \leq N \leq 50
• Each of S and T is a string of length N consisting of X and Y.

Sample Input 1

3
XXX
YYY

Sample Output 1

XY

• If you swap nothing, the only common subsequence of XXX and YYY is the empty string.
• If you swap the 1-st characters, the common subsequences of YXX and XYY are the empty string, X, and Y.
• If you swap the 2-nd characters, the common subsequences of XYX and YXY are the empty string, X, Y, XY, and YX.
• If you swap the 3-rd characters, the common subsequences of XXY and YYX are the empty string, X and Y.

Doing two or more swaps is equivalent to one of the above after swapping S and T themselves. Thus, the longest strings that can be a common subsequence are XY and YX. The lexicographically smaller of them, XY, is the answer.

Sample Input 2

1
X
Y

Sample Output 2

The answer may be the empty string.

Sample Input 3

4
XXYX
YYYY

Sample Output 3

XYY

XYY will be a common subsequence after, for instance, swapping just the 2-nd characters. Any string that is longer or has the same length and is lexicographically smaller will not be a common subsequence after any combination of swaps, so this is the answer.