Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N, and another integer sequence P=(P_2,\cdots,P_N) of length N-1. Note that the index of P starts at 2. It is guaranteed that 1 \leq P_i < i for each i.

You will now repeat the following operation 10^{100} times.

• For each i=2,\cdots,N, in this order, replace the value of A_{P_i} with A_{P_i}+A_{i}.

Determine whether A_1 will be positive, negative, or zero when all operations are completed.

Constraints

• 2 \leq N \leq 250000
• -10^9 \leq A_i \leq 10^9
• 1 \leq P_i < i
• All input values are integers.

Sample Input 1

4
1 -2 3 -4
1 2 3

Sample Output 1

-

Shown below are the results of the first few operations.

• After the first operation:
  • Before the operation: A=(1,-2,3,-4).
  • Processing for i=2: Replace the value of A_1 with A_1+A_2=1+(-2)=-1.
  • Processing for i=3: Replace the value of A_2 with A_2+A_3=-2+3=1.
  • Processing for i=4: Replace the value of A_3 with A_3+A_4=3+(-4)=-1.
  • After the operation: A=(-1,1,-1,-4).
• After the second operation, A=(0,0,-5,-4).
• After the third operation, A=(0,-5,-9,-4).
• After the fourth operation, A=(-5,-14,-13,-4).
• \vdots

After 10^{100} operations, A_1 will be negative. Thus, you should print -.

Sample Input 2

3
0 1 -1
1 1

Sample Output 2

0

Sample Input 3

5
1 -1 1 -1 1
1 1 2 2

Sample Output 3

+

Sample Input 4

20
568273618 939017124 -32990462 -906026662 403558381 -811698210 56805591 0 436005733 -303345804 96409976 179069924 0 0 0 -626752087 569946496 0 0 0
1 1 1 4 4 6 7 2 2 3 3 8 13 14 9 9 15 18 19

Sample Output 4

+

Problem Statement

You are given a positive integer S. For a sequence of positive integers x, we define f(x) as follows:

• Consider decomposing x into several contiguous subsequences. For each contiguous subsequence, the sum of its elements must be at most S. The minimum number of contiguous subsequences in such a decomposition is the value of f(x).

It can be proved that the value of f is always definable under the constraints of this problem.

You are given a sequence of positive integers A=(A_1,A_2,\cdots,A_N). Find the value of \sum_{1 \leq l \leq r \leq N} f((A_l,A_{l+1},\cdots,A_r)).

Constraints

• 1 \leq N \leq 250000
• 1 \leq S \leq 10^{15}
• 1 \leq A_i \leq \min(S,10^9)
• All input values are integers.

Sample Input 1

3 3
1 2 3

Sample Output 1

8

For example, consider x=(1,2,3). The decomposition (1,2),(3) satisfies the condition, and no decomposition into fewer than two contiguous subsequences satisfies the condition, so f((1,2,3))=2.

Shown below are the possible l,r and the corresponding values of f:

• (l,r)=(1,1): f((1))=1
• (l,r)=(1,2): f((1,2))=1
• (l,r)=(1,3): f((1,2,3))=2
• (l,r)=(2,2): f((2))=1
• (l,r)=(2,3): f((2,3))=2
• (l,r)=(3,3): f((3))=1

Thus, the answer is 1+1+2+1+2+1=8.

Sample Input 2

5 1
1 1 1 1 1

Sample Output 2

35

Sample Input 3

5 15
5 4 3 2 1

Sample Output 3

15

Sample Input 4

20 1625597454
786820955 250480341 710671229 946667801 19271059 404902145 251317818 22712439 520643153 344670307 274195604 561032101 140039457 543856068 521915711 857077284 499774361 419370025 744280520 249168130

Sample Output 4

588

Problem Statement

You are given an integer N. An integer sequence x=(x_1,x_2,\cdots,x_N) of length N is called a good sequence if and only if the following conditions are satisfied:

• Each element of x is an integer between 1 and N, inclusive.
• For each integer i (1 \leq i \leq N), there is no position in x where i appears i+1 or more times in a row.

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Each element of A is -1 or an integer between 1 and N. Find the number, modulo 998244353, of good sequences that can be obtained by replacing each -1 in A with an integer between 1 and N.

Constraints

• 1 \leq N \leq 5000
• A_i=-1 or 1 \leq A_i \leq N.
• All input values are integers.

Sample Input 1

2
-1 -1

Sample Output 1

3

You can obtain four sequences by replacing each -1 with an integer between 1 and 2.

A=(1,1) is not a good sequence because 1 appears twice in a row.

The other sequences A=(1,2),(2,1),(2,2) are good.

Thus, the answer is 3.

Sample Input 2

3
2 -1 2

Sample Output 2

2

Sample Input 3

4
-1 1 1 -1

Sample Output 3

0

Sample Input 4

20
9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1

Sample Output 4

128282166

Problem Statement

You are given an integer sequence A=(A_1,A_2,\cdots,A_N) of length N. Each element of A is an integer between 0 and N-1, inclusive.

You can perform the following operation zero or more times:

• Choose exactly M elements from A. Then, increase the value of each chosen element by 1. Now, if some elements have the values of N, change those values to 0.

Your goal is to make A a permutation of (0,1,\cdots,N-1). Determine if the goal is achievable. If it is, find the minimum number of operations required.

Constraints

• 2 \leq N \leq 250000
• 1 \leq M \leq N-1
• 0 \leq A_i \leq N-1
• All input values are integers.

Sample Input 1

3 2
0 1 1

Sample Output 1

2

You can operate as follows to achieve the goal in two operations:

• Initial state: A=(0,1,1).
• First operation: Choose A_1 and A_2, making A=(1,2,1).
• Second operation: Choose A_2 and A_3, making A=(1,0,2).

You cannot achieve the goal in fewer than two operations, so the answer is 2.

Sample Input 2

5 2
0 4 2 3 1

Sample Output 2

0

Sample Input 3

4 2
0 0 1 2

Sample Output 3

-1

Sample Input 4

20 15
5 14 18 0 8 5 0 10 6 5 11 2 10 10 17 9 8 14 4 4

Sample Output 4

10

Problem Statement

There is a tournament with 2^N participants, numbered 1 to 2^N.

The tournament proceeds as follows:

• First, each participant is given a red or blue hat. You are given the color of the hat for each participant as the string S. Specifically, participant i is given a red hat if the i-th character (1 \leq i \leq 2^N) of S is R, and a blue hat if it is B.

• Then, the following operation is repeated until there is only one participant remaining:

  • Let 2k be the current number of participants. Divide the participants into k pairs. You can freely choose how to pair them. Then, a match is held for each pair; the winner remains, and the loser leaves the tournament. The participants are numbered in descending order of strength, so the participant with the smaller number always wins.

A match between two participants wearing red hats is called a boring match. Your goal is to arrange the pairings so that no boring matches occur during the tournament.

Whether the goal is achievable or not depends on the string S. Hence, you have decided to tamper with S before the start of the tournament. Specifically, you can perform the following operation zero or more times:

• Choose two adjacent characters in S and swap them.

Determine whether it is possible to achieve the goal after operations. If it is, find the minimum number of operations required.

Constraints

• 1 \leq N \leq 18
• S is a string of length 2^N consisting of R and B.
• All input values are integers.

Sample Input 1

2
RRBB

Sample Output 1

1

Without performing any operations, you cannot achieve the goal.

If you swap the second and third characters of S, making S=RBRB, you can achieve the goal as follows:

• Give red, blue, red, and blue hats to participants 1, 2, 3, and 4, respectively.
• Divide the four participants into two pairs (1,4),(2,3). No boring matches occur here. After the matches, participants 1 and 2 remain.
• Divide the two participants into one pair (1,2). No boring matches occur here. After the match, participant 1 remains.

Therefore, the answer is 1.

Sample Input 2

1
RR

Sample Output 2

-1

Sample Input 3

4
RBBRRBRBBRBBBRBR

Sample Output 3

0

Sample Input 4

5
RBRRBRRRBRRRRRRRRRBBBBBBBBBBBBBB

Sample Output 4

11

Problem Statement

You are given integer sequences of length N: A=(A_1,A_2,\cdots,A_N), B=(B_1,B_2,\cdots,B_N), X=(X_1,X_2,\cdots,X_N), and Y=(Y_1,Y_2,\cdots,Y_N). Here, A and B satisfy the following properties:

• A_1=1.
• B_1=2.
• (A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N) is a permutation of (1,2,\cdots,2N).

Define the integers d_{i,j} (1 \leq i,j \leq N) as follows:

• d_{1,1}=0.
• If (i,j) \neq (1,1) and A_i<B_j, then d_{i,j}=d_{i,j-1}+X_i.
• If (i,j) \neq (1,1) and A_i>B_j, then d_{i,j}=d_{i-1,j}+Y_j.

Find \sum_{1 \leq i \leq N}\sum_{1 \leq j \leq N}d_{i,j}, modulo 998244353.

Constraints

• 2 \leq N \leq 250000
• A_1=1
• B_1=2
• (A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N) is a permutation of (1,2,\cdots,2N).
• 1 \leq X_i \leq 10^9
• 1 \leq Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 4
2 3
2 2
1 3

Sample Output 1

8

The values of d_{i,j} are as follows:

• d_{1,1}=0
• d_{1,2}=d_{1,1}+X_1=0+2=2
• d_{2,1}=d_{1,1}+Y_1=0+1=1
• d_{2,2}=d_{1,2}+Y_2=2+3=5

Thus, the answer is 0+2+1+5=8.

Sample Input 2

3
1 3 5
2 6 4
1 10 100
1000 10000 100000

Sample Output 2

108153

Sample Input 3

3
1 6 5
2 4 3
1 10 100
1000 10000 100000

Sample Output 3

333009

Sample Input 4

10
1 17 4 7 16 18 9 3 12 6
2 19 20 14 5 11 13 8 15 10
744280520 249168130 239276621 320064892 910500852 164832983 245532751 198319687 715892722 967824729
769431650 80707350 459924868 257261830 777045524 583882654 950300099 438099970 322288793 532405020

Sample Output 4

746075419