Problem Statement

You are given two strings S and T of length N consisting of A and B. Let S_i denote the i-th character from the left of S.

You can repeat the following operation any number of times, possibly zero:

• Choose integers i and j such that 1\leq i < j \leq N. Replace S_i with A and S_j with B.

Determine if it is possible to make S equal T. If it is possible, find the minimum number of operations required.

Constraints

• 2 \leq N \leq 2 \times 10^5
• Each of S and T is a string of length N consisting of A and B.
• All input numbers are integers.

Sample Input 1

5
BAABA
AABAB

Sample Output 1

2

Performing the operation with i=1 and j=3 changes S to AABBA.

Performing the operation with i=4 and j=5 changes S to AABAB.

Thus, you can make S equal T with two operations. It can be proved that this is the minimum number of operations required, so the answer is 2.

Sample Input 2

2
AB
BA

Sample Output 2

-1

It can be proved that no matter how many operations you perform, you cannot make S equal T.

Problem Statement

You are given a sequence A of length N consisting of integers between 1 and \textbf{10}, inclusive.

A pair of integers (l,r) satisfying 1\leq l \leq r\leq N is called a good pair if it satisfies the following condition:

• The sequence (A_l,A_{l+1},\ldots,A_r) contains a (possibly non-contiguous) arithmetic subsequence of length 3. More precisely, there is a triple of integers (i,j,k) with l \leq i < j < k\leq r such that A_j - A_i = A_k - A_j.

Find the number of good pairs.

Constraints

• 3 \leq N \leq 10^5
• 1\leq A_i \leq 10
• All input numbers are integers.

Sample Input 1

5
5 3 4 1 5

Sample Output 1

3

There are three good pairs: (l,r)=(1,4),(1,5),(2,5).

For example, the sequence (A_1,A_2,A_3,A_4) contains an arithmetic subsequence of length 3, which is (5,3,1), so (1,4) is a good pair.

Sample Input 2

3
1 2 1

Sample Output 2

0

There may be cases where no good pairs exist.

Sample Input 3

9
10 10 1 3 3 7 2 2 5

Sample Output 3

3

Problem Statement

For a sequence X composed of a finite number of non-negative integers, we define \mathrm{mex}(X) as the smallest non-negative integer not in X. For example, \mathrm{mex}((0,0, 1,3)) = 2, \mathrm{mex}((1)) = 0, \mathrm{mex}(()) = 0.

You are given a sequence S=(S_1,\ldots,S_N) of length N where each element is 0 or 1.

Find the number, modulo 998244353, of sequences A=(A_1,A_2,\ldots,A_N) of length N consisting of integers between 0 and M, inclusive, that satisfy the following condition:

• For each i (1\leq i\leq N), A_i = \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=1, and A_i \neq \mathrm{mex}((A_1,A_2,\ldots,A_{i-1})) if S_i=0.

Constraints

• 1 \leq N \leq 5000
• 0 \leq M \leq 10^9
• S_i is 0 or 1.
• All input numbers are integers.

Sample Input 1

4 2
1 0 0 1

Sample Output 1

4

The following four sequences satisfy the conditions:

• (0,0,0,1)
• (0,0,2,1)
• (0,2,0,1)
• (0,2,2,1)

Sample Input 2

10 1000000000
0 0 1 0 0 0 1 0 1 0

Sample Output 2

587954969

Be sure to find the count modulo 998244353.

Problem Statement

Alice and Bob will play a game.

Initially, Alice and Bob each have N cards, with the i-th card of Alice having the integer A_i written on it, and the i-th card of Bob having the integer B_i written on it.

The game proceeds as follows:

• Prepare a blackboard with nothing written on it.
• Alice eats one of her cards and writes the integer from the eaten card on the blackboard.
• Next, Bob eats one of his cards and writes the integer from the eaten card on the blackboard.
• Finally, Alice eats one more of her cards and writes the integer from the eaten card on the blackboard.

If it is possible to form a (non-degenerate) triangle with the side lengths of the three integers written on the blackboard, Alice wins; otherwise, Bob wins.

Determine who wins when both players act optimally.

Solve each of the T given test cases.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i, B_i \leq 10^9
• All input values are integers.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
3
1 2 3
4 5 6
4
6 1 5 10
2 2 4 5
10
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8

Sample Output 1

Bob
Alice
Alice

In the first test case, for example, the game could proceed as follows:

• Alice eats the card with 2 written on it and writes 2 on the blackboard.
• Bob eats the card with 4 written on it and writes 4 on the blackboard.
• Alice eats the card with 1 written on it and writes 1 on the blackboard.
• The numbers written on the blackboard are 2, 4, 1. There is no triangle with side lengths 2, 4, 1, so Bob wins.

For this test case, the above process is not necessarily optimal for the players, but it can be shown that Bob will win if both players act optimally.

Problem Statement

You are given integers N and P.

There is a graph with N vertices and N edges, where each vertex is labeled 1 to N. The i-th edge connects vertices i and i+1 bidirectionally. Here, vertex N+1 refers to vertex 1.

Perform the following algorithm to obtain a sequence D=(D_1,D_2,\ldots,D_N) of length N:

• Set an integer sequence D of length N to D=(D_1,\ldots,D_N)=(-1,\ldots,-1). Also, set a sequence Q of number pairs to Q=((1,0)). Repeat the following process while Q is not empty:

  • Let (v,d) be the first element of Q. Remove this element.

  • If D_v = -1, then set D_v := d, and for each vertex x adjacent to vertex v such that D_x=-1, perform the following process. If there are multiple such x that satisfy the condition, process them in ascending order of vertex number:

    1. With probability \frac{P}{100}, add (x,d+1) to the front of Q.
    2. If (x,d+1) was not added to the front of Q, add it to the end of Q.

Find the expected value of the sum of the elements of the final sequence D obtained, modulo 998244353.

Solve each of the T test cases given.

Constraints

• 1 \leq T \leq 10^4
• 3 \leq N \leq 10^{18}
• 1\leq P \leq 99
• All input numbers are integers.

Sample Input 1

3
3 50
4 1
1000000000000000000 70

Sample Output 1

499122179
595552585
760296751

In the first test case, the algorithm may operate as follows:

• Initially, D=(-1,-1,-1) and Q=((1,0)). Remove the first element (1,0) from Q.
• D_1 = -1, so set D_1 := 0. The vertices x adjacent to vertex 1 such that D_x= -1 are 2 and 3.
• Add (2,1) to the front of Q. Add (3,1) to the end of Q. Now Q=((2,1),(3,1)).
• Remove the first element (2,1) from Q.
• D_2 = -1, so set D_2 := 1. The vertex x adjacent to vertex 2 such that D_x= -1 is 3.
• Add (3,2) to the front of Q. Now Q=((3,2),(3,1)).
• Remove the first element (3,2) from Q.
• D_3 = -1, so set D_3 := 2. There are no vertices x adjacent to vertex 3 such that D_x= -1, so do nothing.
• Remove the first element (3,1) from Q.
• D_3 =2, so do nothing.
• Q is now empty, so the process ends.

In this case, the final sequence obtained is D=(0,1,2). The probability that the algorithm operates as described above is \frac{1}{8}, and the expected sum of the elements of D is \frac{5}{2}.

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge of the tree connects vertices u_i and v_i bidirectionally.

For a permutation P=(P_1,\ldots,P_N) of (1,2,\ldots,N), we define the sequence A(P) as follows:

• A(P) is initially empty. Write P_i on each vertex i.
• For i=1,2,\ldots,N in this order, perform the following:
  • If vertex i is an isolated vertex, append 0 to the end of A(P). Otherwise, select the adjacent vertex with the smallest written integer. Append the integer written on the selected vertex to the end of A(P) and remove the edge connecting vertex i and the selected vertex.

Find the lexicographically smallest sequence among all possible A(P).

Solve each of the T given test cases.

Constraints

• 1 \leq T \leq 10^5
• 2 \leq N \leq 2 \times 10^5
• 1\leq u_i,v_i\leq N
• The given graph is a tree.
• All input numbers are integers.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.

Sample Input 1

3
5
1 2
2 3
2 4
4 5
8
8 6
7 2
2 1
3 7
5 6
1 6
4 3
7
7 1
5 2
1 2
6 5
4 1
5 3

Sample Output 1

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

In the first test case, for P=(4,1,2,3,5), one can obtain A(P)=(1,2,0,1,3) as follows:

• The vertex adjacent to vertex 1 with the smallest written integer is vertex 2. Append P_2=1 to the end of A(P) and remove the edge connecting vertices 1 and 2.

• The vertex adjacent to vertex 2 with the smallest written integer is vertex 3. Append P_3=2 to the end of A(P) and remove the edge connecting vertices 2 and 3.

• Vertex 3 is an isolated vertex, so append 0 to the end of A(P).

• The vertex adjacent to vertex 4 with the smallest written integer is vertex 2. Append P_2=1 to the end of A(P) and remove the edge connecting vertices 4 and 2.

• The vertex adjacent to vertex 5 with the smallest written integer is vertex 4. Append P_4=3 to the end of A(P) and remove the edge connecting vertices 5 and 4.

It can be proved that this is the lexicographically smallest sequence among all possible A(P).