Problem Statement

You are given a string of length N, S=S_1S_2\dots S_N, consisting of 0, 1, and ?.

We like to replace every ? with 0 or 1 so that all of the following conditions are satisfied.

• S contains exactly K occurrences of 1.
• These K occurrences of 1 are consecutive. That is, there is an i\ (1 \leq i \le N-K+1) such that S_i=S_{i+1}=\dots=S_{i+K-1}= 1.

Determine whether there is exactly one way to replace the characters to satisfy the conditions.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 10^5
• 1 \leq K < N \leq 3 \times 10^5
• S is a string of length N consisting of 0, 1, and ?.
• The sum of N across the test cases is at most 3 \times 10^5.

Sample Input 1

4
3 2
1??
4 2
?1?0
6 3
011?1?
10 5
00?1???10?

Sample Output 1

Yes
No
No
Yes

For the first test case, turning S into 101, for instance, does not satisfy the conditions since the 1s will not be consecutive. The only way to satisfy the conditions is to turn S into 110.

For the second test case, we may turn S into 1100 or 0110 to satisfy the conditions, so there are two ways to satisfy them.

For the third test case, there is no way to replace the characters to satisfy the conditions.

Problem Statement

You are given positive integers A and B.

Find the minimum value of X+Y for non-negative integers X and Y such that B+Y is a multiple of A+X.

You have T test cases to solve.

Constraints

• 1 \leq T \leq 100
• 1 \leq A,\ B \leq 10^9
• All values in the input are integers.

Sample Input 1

5
11 23
8 16
4394 993298361
95392025 569922442
8399283 10293

Sample Output 1

2
0
65
2429708
8388990

For the first test case, if we let X=1 and Y=1, then B+Y=24 will be a multiple of A+X=12. Here, we have X+Y=2, and there is no way to make X+Y smaller, so the answer is 2.

For the second test case, if we let X=0 and Y=0, then B+Y=16 will be a multiple of A+X=8.

Problem Statement

We have a connected undirected graph G with N vertices and M edges. The vertices are numbered 1 to N. The i-th edge connects vertices U_i and V_i.

Additionally, we are given an integer sequence of length N, A=(A_1,\ A_2, \dots,\ A_N), and an integer sequence of length K, B=(B_1,\ B_2,\ \dots,\ B_K).

Determine whether G, A, and B satisfy the following condition.

• For every simple path from vertex 1 to N in G, v=(v_1,\ v_2, \dots,\ v_k)\ (v_1=1,\ v_k=N), B is a (not necessarily contiguous) subsequence of (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}).

Constraints

• 2 \leq N \leq 10^5
• 1 \leq K \leq N
• N-1 \leq M \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N
• (U_i,\ V_i) \neq (U_j,\ V_j) if i \neq j.
• 1 \leq A_i,\ B_i \leq N
• All values in the input are integers.
• The given graph G is connected.

Sample Input 1

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

Sample Output 1

Yes

There are two simple paths from vertex 1 to vertex 6: (1,\ 2,\ 4,\ 6) and (1,\ 3,\ 5,\ 6). The (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}) corresponding to these paths are (1,\ 2,\ 5,\ 6) and (1,\ 4,\ 2,\ 6). Both of them have B=(1,\ 2,\ 6) as a subsequence, so the answer is Yes.

Sample Input 2

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

Sample Output 2

No

For a simple path (1,\ 2,\ 5) from vertex 1 to vertex 5, the (A_{v_1},\ A_{v_2},\ \dots,\ A_{v_k}) is (1,\ 2,\ 2), which does not have B=(1,\ 3,\ 2) as a subsequence.

Sample Input 3

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

Sample Output 3

Yes

Problem Statement

We have a rooted tree with N vertices numbered 1 to N. Vertex 1 is the root of the tree, and the parent of vertex i\ (2\leq i) is vertex p_i.

Each vertex has a color: black or white. Initially, all vertices are white.

In this rooted tree, vertex i is said to be good when all vertices on the simple path connecting vertices 1 and i (including vertices 1 and i) are black, and bad otherwise.

Until all vertices are black, let us repeat the following operation: choose one vertex from the bad vertices uniformly at random, and repaint the chosen vertex black.

Find the expected value of the number of times we perform the operation, modulo 998244353.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq p_i < i
• All values in the input are integers.

Sample Input 1

4
1 1 3

Sample Output 1

831870300

Consider a case where the first three operations have chosen vertices 1, 2, and 4 in this order. Then, vertices 1 and 2 are good, but vertex 4 is still bad since vertex 3, an ancestor of vertex 4, is white. Thus, the fourth operation will choose vertex 3 or 4 uniformly at random.

The expected value of the number of times we perform the operation is \displaystyle \frac{35}{6}.

Sample Input 2

15
1 2 1 1 4 5 3 3 5 10 3 6 3 13

Sample Output 2

515759610

Problem Statement

NK people are standing in a line from left to right. Let us denote them as person i (0\leq i \leq NK-1) from left to right.

Each person is always facing either left or right. The direction of each person at time t=0 is represented by a string of length N, S=S_0 S_1 \dots S_{N-1}, consisting of L and R. At time t=0, person i is facing left if S_{i \bmod N} is L, and right if it is R.

At time t=0.5,\ 1.5,\ 2.5 ,\ \dots, these people simultaneously change their directions according to the following rules.

• When a person is facing left:
  If there are one or more people in the direction the person is facing, and more than half of those people are facing right, the person changes direction and faces right. Otherwise, the person does not change direction.
• When a person is facing right:
  If there are one or more people in the direction the person is facing, and more than half of those people are facing left, the person changes direction and faces left. Otherwise, the person does not change direction.

Find the sum, modulo 998244353, of the numbers of times the NK people change direction from time t=0 to t=10^{100}.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 2 \times 10^5
• S is a string of length N consisting of L and R.
• All numerical values in the input are integers.

Sample Input 1

7 1
RRLRLLL

Sample Output 1

9

If we represent the directions of the seven people at each time, we have LLRLRRL at t=1, LLRLRLL at t=2, and LLLLLLL at t=3.

After t=3, the directions of the seven people do not change. Therefore, the answer is 1+1+2+1+2+2+0=9.

Sample Input 2

4 10
LLRR

Sample Output 2

0

Sample Input 3

23 200
RLRRRLLLLLLLLRRRLLRLRRR

Sample Output 3

2207

Problem Statement

We have a sequence of positive integers of length N^2, A=(A_1,\ A_2,\ \dots,\ A_{N^2}), and a positive integer S. For this sequence of positive integers, A_i=A_{i+N} holds for positive integers i\ (1\leq i \leq N^2-N), and only A_1,\ A_2,\ \dots,\ A_N are given as the input.

Find the minimum integer L such that every sequence B of positive integers totaling S is a (not necessarily contiguous) subsequence of the sequence (A_1,\ A_2,\ \dots,\ A_L) of positive integers.

It can be shown that at least one such L exists under the Constraints of this problem.

Constraints

• 1 \leq N \leq 1.5 \times 10^6
• 1 \leq S \leq \min(N,2 \times 10^5)
• 1 \leq A_i \leq S
• For every positive integer x\ (1\leq x \leq S), (A_1,\ A_2,\ \dots,\ A_N) contains at least one occurrence of x.
• All values in the input are integers.

Sample Input 1

6 4
1 1 2 1 4 3

Sample Output 1

9

There are eight sequences B to consider: B=(1,\ 1,\ 1,\ 1),\ (1,\ 1,\ 2),\ (1,\ 2,\ 1),\ (1,\ 3),\ (2,\ 1,\ 1),\ (2,\ 2),\ (3,\ 1),\ (4).

For L=8, for instance, B=(2,\ 2) is not a subsequence of (A_1,A_2,\ \dots,\ A_8)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1).

For L=9, on the other hand, every B is a subsequence of (A_1,A_2,\ \dots,\ A_9)=(1,\ 1,\ 2,\ 1,\ 4,\ 3,\ 1,\ 1,\ 2).

Sample Input 2

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

Sample Output 2

11

Sample Input 3

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

Sample Output 3

39