Problem Statement

There was a contest with N problems. The i-th (1\leq i\leq N) problem was worth A_i points.

Snuke took part in this contest and solved M problems: the B_1-th, B_2-th, \ldots, and B_M-th ones. Find his total score.

Here, the total score is defined as the sum of the points for the problems he solved.

Constraints

• 1\leq M \leq N \leq 100
• 1\leq A_i \leq 100
• 1\leq B_1 < B_2 < \ldots < B_M \leq N
• All values in the input are integers.

Sample Input 1

3 2
10 20 30
1 3

Sample Output 1

40

Snuke solved the 1-st and 3-rd problems, which are worth 10 and 30 points, respectively. Thus, the total score is 10+30=40 points.

Sample Input 2

4 1
1 1 1 100
4

Sample Output 2

100

Sample Input 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

Sample Output 3

202

Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

• Every integer i such that 0 \le i < m is contained in X.
• m is not contained in X.

Constraints

• All values in the input are integers.
• 1 \le K \le N \le 3 \times 10^5
• 0 \le A_i \le 10^9

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

• If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
• If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
• If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
• If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.

Problem Statement

There are N squares indexed 0 through (N-1) arranged in a line. Snuke is going to mark every square by the following procedure.

1. Mark square 0.
2. Repeat the following steps i - iii (N-1) times.
   1. Initialize a variable x with (A+D) \bmod N, where A is the index of the square marked last time.
   2. While square x is marked, repeat replacing x with (x+1) \bmod N.
   3. Mark square x.

Find the index of the square that Snuke marks for the K-th time.

Given T test cases, find the answer for each of them.

Constraints

• 1\leq T \leq 10^5
• 1\leq K\leq N \leq 10^9
• 1\leq D \leq 10^9
• All values in the input are integers.

Sample Input 1

9
4 2 1
4 2 2
4 2 3
4 2 4
5 8 1
5 8 2
5 8 3
5 8 4
5 8 5

Sample Output 1

0
2
1
3
0
3
1
4
2

If N=4 and D=2, Snuke marks the squares as follows.

1. Mark square 0.
2. (1-st iteration) Let x=(0+2)\bmod 4=2. Since square 2 is not marked, mark it.
   (2-nd iteration) Let x=(2+2)\bmod 4=0. Since square 0 is marked, let x=(0+1)\bmod 4=1. Since square 1 is not marked, mark it.
   (3-rd iteration) Let x=(1+2)\bmod 4=3. Since square 3 is not marked, mark it.

Problem Statement

For a sequence X, let f(X) = (the minimum number of elements one must modify to make X a palindrome).

Given a sequence A of length N, find the sum of f(X) over all contiguous subarrays of A.

Here, a sequence X of length m is said to be a palindrome if and only if the i-th and the (m+1-i)-th elements of X are equal for all 1 \le i \le m.

Constraints

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

Sample Input 1

5
5 2 1 2 2

Sample Output 1

9

• f(5) = 0
• f(2) = 0
• f(1) = 0
• f(2) = 0
• f(2) = 0
• f(5,2) = 1
• f(2,1) = 1
• f(1,2) = 1
• f(2,2) = 0
• f(5,2,1) = 1
• f(2,1,2) = 0
• f(1,2,2) = 1
• f(5,2,1,2) = 2
• f(2,1,2,2) = 1
• f(5,2,1,2,2) = 1

Therefore, the sought answer is 9.

Problem Statement

For a sequence X=(X_1,X_2\ldots,X_N) of length N consisting of positive integers, we define f(X) as follows:

• A tree with N vertices is said to be good if and only if the degree of the i-th (1 \leq i \leq N) vertex is X_i. If a good tree exists, f(X) is the maximum diameter of a good tree; if it doesn't, f(X)=0.

Here, the distance between two vertices is the minimum number of edges that must be traversed to travel from one vertex to the other, and the diameter of a tree is the maximum distance between two vertices.

Find the sum, modulo 998244353, of f(X) over all possible sequences X of length N consisting of positive integers. We can prove that the sum of f(X) is a finite value.

Given T test cases, find the answer for each of them.

Constraints

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

Sample Input 1

10
2
3
5
8
13
21
34
55
89
144

Sample Output 1

1
6
110
8052
9758476
421903645
377386885
881422708
120024839
351256142

If N=3,

for example,

• when X=(1,1,1), there is no tree with three vertices whose degrees are 1,1, and 1, so f(X)=0.
• When X=(2,1,1), the only possible tree is illustrated below. The diameter of this tree is 2, so f(X)=2.

For X=(2,1,1),(1,2,1),(1,1,2), we have f(X)=2; for other X, we have f(X)=0. Thus, the answer is 6.

Problem Statement

Solve the following problem for T test cases.

We have a perfect K-ary tree of depth D (with 1+K+K^2+\dots+K^D vertices).
Your objective is to cut some of the edges to obtain a connected component with exactly X vertices.
At least how many edges must be cut to achieve the objective?

Constraints

• All values in the input are integers.
• 1 \le T \le 100
• 1 \le D
• 2 \le K
• \displaystyle 1 \le X \le \sum_{i=0}^{D} K^i \le 10^{18}

Sample Input 1

11
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
1 999999999999999999 1
1 999999999999999999 2
1 999999999999999999 999999999999999999
1 999999999999999999 1000000000000000000

Sample Output 1

1
2
1
1
2
1
0
1
999999999999999998
1
0

Problem Statement

There are N dogs numbered 1 through N and M cats numbered 1 through M. You will arrange the (N+M) animals in a line from left to right. An arrangement causes each animal's frustration as follows:

• The frustration of dog i is A_i\times|x-y|, where x and y are the numbers of cats to the left and right of that dog, respectively.
• The frustration of cat i is B_i\times|x-y|, where x and y are the numbers of dogs to the left and right of that cat, respectively.

Find the minimum possible sum of the frustrations.

Constraints

• 1\leq N,M \leq 300
• 1\leq A_i,B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

2 2
1 3
2 4

Sample Output 1

6

Consider the following arrangement: dog 1, cat 2, dog 2, cat 1, from left to right. Then,

• dog 1's frustration is 1\times|0-2|=2;
• dog 2's frustration is 3\times|1-1|=0;
• cat 1's frustration is 2\times|2-0|=4; and
• cat 2's frustration is 4\times|1-1|=0,

so the sum of the frustrations is 6. Rearranging the animals does not make the sum less than 6, so the answer is 6.

Sample Input 2

1 2
100
100 290

Sample Output 2

390

Sample Input 3

5 7
522 575 426 445 772
81 447 629 497 202 775 325

Sample Output 3

13354