Problem Statement

Snuke has a sequence of N integers a=(a_1,a_2,\cdots,a_N) consisting of 0s and 1s, and an empty integer sequence b. The initial state a_i=S_i is given to you as input.

Snuke can do the following three operations any number of times in any order.

• Shift a to the right. In other words, replace a with (a_N,a_1,a_2,\cdots,a_{N-1}).

• Shift a to the left. In other words, replace a with (a_2,a_3,\cdots,a_N,a_1).

• Append the current value of a_1 at the end of b.

You are also given a sequence of M integers T=(T_1,T_2,\cdots,T_M). Determine whether it is possible to make b equal to T. If it is possible, find the minimum number of operations needed to do so.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 0 \leq S_i \leq 1
• 0 \leq T_i \leq 1
• All values in input are integers.

Sample Input 1

3 4
0 0 1
0 1 1 0

Sample Output 1

6

The following sequence of six operations will do the job.

• Append the current value of a_1 at the end of b, making b=(0).

• Shift a to the right, making a=(1,0,0).

• Append the current value of a_1 at the end of b, making b=(0,1).

• Append the current value of a_1 at the end of b, making b=(0,1,1).

• Shift a to the right, making a=(0,1,0).

• Append the current value of a_1 at the end of b, making b=(0,1,1,0).

Sample Input 2

1 1
0
1

Sample Output 2

-1

Problem Statement

You are given an integer N. Find the number of pairs of integers (x, y) that satisfy the following conditions, modulo 998244353.

• 1 \leq x,y \leq N.

• x^2-y is a square number. (Assume 0 is also a square number.)

Constraints

• 1 \leq N \leq 10^{12}
• All values in input are integers.

Sample Input 1

3

Sample Output 1

2

We have the following two pairs.

• x=1,y=1

• x=2,y=3

Sample Input 2

10

Sample Output 2

8

Sample Input 3

10000000000

Sample Output 3

52583544

Problem Statement

Given are an integer N and a monotonically increasing sequence of K integers A=(A_1,A_2,\cdots,A_K). Find the lexicographically smallest permutation P of (1,2,\cdots,N) that satisfies the following condition.

• A is a longest increasing subsequence of P (a monotonically increasing subsequence of P with the maximum possible length). It is fine if P has multiple longest increasing subsequences, one of which is A.

From the Constraints of this problem, we can prove that there always exists a P that satisfies the condition.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_1 < A_2 < \cdots < A_K \leq N
• All values in input are integers.

Sample Input 1

3 2
2 3

Sample Output 1

2 1 3

A is a longest increasing subsequence of P when P=(2,1,3),(2,3,1). The answer is the lexicographically smallest of the two, or (2,1,3).

Sample Input 2

5 1
4

Sample Output 2

5 4 3 2 1

Problem Statement

Given is a sequence of N integers A_1,A_2,\cdots,A_N.

Find the number of non-empty subsequences s of A satisfying the following condition, modulo 998244353.

• There is only one way to extract s from A. Formally, there uniquely exists a sequence of indices 1 \leq idx(1)<idx(2)<\cdots<idx(k) \leq N such that A_{idx(i)}=s_i (1 \leq i \leq k), where s=(s_1,s_2,\cdots,s_k).

Constraints

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

Sample Input 1

3
1 2 1

Sample Output 1

5

The following five subsequences satisfy the condition.

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

The subsequence (1) does not satisfy the condition since there are two ways to extract it.

Sample Input 2

4
4 2 1 3

Sample Output 2

15

Sample Input 3

12
1 2 3 6 9 2 3 3 9 6 1 6

Sample Output 3

1178

Problem Statement

There are N kinds of snacks numbered 1 through N. We have A_i pieces of Snack i.

There are M children numbered 1 through M. We will distribute the pieces of snacks to these children. Here, all of the following conditions must be satisfied.

• For every kind of snack, Child i gets at most B_i pieces of that kind.

• Child i gets at most C_i pieces of snacks in total.

Find the maximum total number of pieces of snacks that can be distributed to the children under these conditions.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i \leq 10^{12}
• 1 \leq B_i \leq 10^7
• 1 \leq C_i \leq 10^{12}
• All values in input are integers.

Sample Input 1

3 3
2 5 5
1 2 2
5 3 5

Sample Output 1

11

The optimal distribution of snacks is as follows.

• Child 1 gets 1, 1, 1 piece of Snacks 1, 2, 3, respectively.

• Child 2 gets 0, 2, 1 piece(s) of Snacks 1, 2, 3, respectively.

• Child 3 gets 1, 2, 2 piece(s) of Snacks 1, 2, 3, respectively.

Sample Input 2

10 6
3 54 62 64 25 89 1 47 77 4
1 17 10 29 95 17
32 40 90 27 50 9

Sample Output 2

211

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex A_i and Vertex B_i.

Find the number of pairs of integers (x,y) that satisfy the following conditions.

• 0 \leq x \leq N.

• There is a way to choose exactly x vertices from the tree so that the sum of their degrees equals y.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• All values in input are integers.

Sample Input 1

3
1 2
2 3

Sample Output 1

6

The following six pairs (x,y) satisfy the conditions.

• x=0,y=0
• x=1,y=1
• x=1,y=2
• x=2,y=2
• x=2,y=3
• x=3,y=4

x=2,y=3, for example, satisfies the condition because choosing Vertex 1 and Vertex 2 achieves the total degree of 3.

Sample Input 2

5
1 2
2 3
2 4
4 5

Sample Output 2

16

Sample Input 3

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

Sample Output 3

65