Problem Statement

Snuke has 1 gram of gold and 0 grams of silver now. He will do trading of gold and silver for the following N days. On each day, he has two choices: do nothing, or make a trade. If he trades on Day i (1 \leq i \leq N), the following will happen.

• If he has x grams of gold before the trade, exchange all of it for x \times A_i grams of silver. On the other hand, if he has x grams of silver, exchange all of it for x / A_i grams of gold.

Snuke's objective is to maximize the amount of gold he has in the end. Find one way to achieve his objective.

Constraints

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

Sample Input 1

3
3 5 2

Sample Output 1

0 1 1

The optimal sequence of actions is as follows.

• Day 1: Do nothing.

• Day 2: Exchange 1 gram of gold for 5 grams of silver.

• Day 3: Exchange 5 grams of silver for 2.5 grams of gold.

Sample Input 2

4
1 1 1 1

Sample Output 2

0 0 0 0

(v_1,v_2,v_3,v_4)=(1,1,1,1), for example, is also considered correct.

Sample Input 3

10
426877385 186049196 624834740 836880476 19698398 709113743 436942115 436942115 436942115 503843678

Sample Output 3

1 1 0 1 1 1 1 0 0 0

Problem Statement

We have R red balls, G green balls, and B blue balls. You can do the following operation any number of times:

• choose two balls of different colors and turn them into two balls of the remaining color.

For example, you can choose a red ball and a blue ball and turn them into two green balls.

Your objective is to make all balls have the same color. Determine whether this objective is achievable. If it is, find the minimum number of operations required to achieve it.

For each input file, solve T test cases.

Constraints

• 1 \leq T \leq 100
• 1 \leq R,G,B \leq 10^8
• All values in input are integers.

Sample Input 1

3
1 2 2
1 2 3
1 2 4

Sample Output 1

2
-1
4

For example, in case_3, one optimal sequence of operations is:

• choose a green ball and blue ball, turning them into two red balls;
• choose a red ball and blue ball, turning them into two green balls;
• choose a red ball and blue ball, turning them into two green balls;
• choose a red ball and blue ball, turning them into two green balls.

Problem Statement

Given are integers N, M, S, and a sequence of N integers A=(A_1,A_2,\cdots,A_N).

Consider making a sequence of N non-negative real numbers x=(x_1,x_2,\cdots,x_N) satisfying all of the following conditions:

• 0 \leq x_1 \leq x_2 \leq \cdots \leq x_N \leq M,
• \sum_{1 \leq i \leq N} x_i=S.

Now, let us define the score of x as \sum_{1 \leq i \leq N} A_i \times x_i. Find the maximum possible score of x.

Constraints

• 1 \leq N \leq 5000
• 1 \leq M \leq 10^6
• 1 \leq S \leq \min(N \times M,10^6)
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

3 2 3
1 2 3

Sample Output 1

8.00000000000000000000

The optimal choice is x=(0,1,2).

Sample Input 2

3 3 2
5 1 1

Sample Output 2

4.66666666666666666667

The optimal choice is x=(2/3,2/3,2/3).

Sample Input 3

10 234567 1000000
353239 53676 45485 617014 886590 423581 172670 928532 312338 981241

Sample Output 3

676780145098.25000000000000000000

Problem Statement

We have N balls arranged in a row, numbered 1 to N from left to right. Ball i has an integer A_i written on it.

You can do the following operation any number of times.

• Choose three consecutive balls x, y, z (1 \leq x < y < z \leq N). Here, A_x \neq A_y and A_y \neq A_z must hold. Then, eat Ball y. After this operation, Balls x and z are considered adjacent.

Find the number of possible sets of balls remaining in the end, modulo 998244353.

Constraints

• 2 \leq N \leq 200000
• 1 \leq A_i \leq N
• All values in input are integers.

Sample Input 1

4
1 2 1 2

Sample Output 1

3

There are three possible sets of balls remaining in the end: \{1,2,3,4\},\{1,2,4\},\{1,3,4\}.

Sample Input 2

5
5 4 3 2 1

Sample Output 2

8

Different sequences of operations are not distinguished if they result in the same set of balls.

Sample Input 3

5
1 2 3 2 1

Sample Output 3

8

Different sets of remaining balls are distinguished even if they have the same sequence of integers written on them.

Sample Input 4

9
1 4 2 2 9 6 9 6 6

Sample Output 4

14

Problem Statement

Given are a sequence of N integers A=(A_1,A_2,\cdots,A_N) and an integer K.

Consider making a sequence of integers x that satisfies both of the following conditions.

• For each integer i (1 \leq i \leq N), x contains exactly A_i occurrences of i. x does not contain other integers.
• For every way of choosing K consecutive elements from x, their values are all distinct.

Determine whether it is possible to make x that satisfies the conditions. If it is possible, find the lexicographically smallest such x.

Constraints

• 2 \leq K \leq N \leq 500
• 1 \leq A_i
• \sum_{1 \leq i \leq N} A_i \leq 200000
• All values in input are integers.

Sample Input 1

3 3
2 2 1

Sample Output 1

1 2 3 1 2

Two sequences x=(1,2,3,1,2),(2,1,3,2,1) satisfy the conditions. The lexicographically smaller one, (1,2,3,1,2), is the answer.

Sample Input 2

3 2
2 1 2

Sample Output 2

1 2 3 1 3

Sample Input 3

3 3
1 3 3

Sample Output 3

-1

Problem Statement

There are N cards numbered 1 to N. Card i has an integer A_i written on it. Here, N is even.

Snuke and Robot will play a game, which will go as follows.

• The game master announces a permutation (p_1,p_2,\cdots,p_N) of (1,2,\cdots,N), to both Snuke and Robot.
• Then, Snuke and Robot alternately take turns, with Snuke going first. Each turn goes as follows.
  • Snuke's turn: choose a remaining card of his choice and eat it.
  • Robot's turn: choose Card i with the largest p_i and burn it.
• The game ends when there is no more card.

The final score of the game is the sum of integers written on the cards eaten by Snuke. Snuke will play optimally to maximize the score.

There are N! permutations p of (1,2,\cdots,N). Find the sum, modulo 998244353, of the final scores for all of these permutations.

Constraints

• 1 \leq N \leq 10^6
• N is even.
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

2
1 2

Sample Output 1

4

Regardless of the permutation p, Snuke will eat Card 2.

Sample Input 2

4
1 100 10000 1000000

Sample Output 2

24200400

For example, when p=(3,1,4,2), the game will go as follows.

• Snuke eats Card 3.
• Robot burns Card 1.
• Snuke eats Card 4.
• Robot burns Card 2.

The score of the game here is 1010000.

Sample Input 3

10
866111664 178537096 844917655 218662351 383133839 231371336 353498483 865935868 472381277 579910117

Sample Output 3

710984634