Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\dots,A_N), and an integer C.
Find the maximum possible sum of the elements in A after performing the following operation at most once:

• Specify integers l and r such that 1 \le l \le r \le N, and multiply each of A_l,A_{l+1},\dots,A_r by C.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• -10^6 \le C \le 10^6
• -10^6 \le A_i \le 10^6

Sample Input 1

5 2
-10 10 20 30 -20

Sample Output 1

90

In this input, A=(-10,10,20,30,-20), C=2.
After performing the operation once specifying l=2 and r=4, A will be (-10,20,40,60,-20).
Here, the sum of the elements in A is 90, which is the maximum value achievable.

Sample Input 2

5 1000000
-1 -2 -3 -4 -5

Sample Output 2

-15

In this input, A=(-1,-2,-3,-4,-5), C=1000000.
Without performing the operation, the sum of the elements in A is -15, which is the maximum value achievable.

Sample Input 3

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

Sample Output 3

13

Problem Statement

Solve the following problem for T test cases.

On the gourmet review site EatCocoder, you can review restaurants with an integer number of stars from 1 to 5.
Initially, the restaurant managed by Chef B has A_i reviews with i stars. (1 \le i \le 5)
The chef can pay a bribe of P_i yen to the EatCocoder administration to have one additional i-star review. (1 \le i \le 5)

After adding a total of k reviews by bribery, there will be A_1+A_2+A_3+A_4+A_5+k reviews in total.
Chef B wants the average rating of these reviews to be at least 3 stars. Determine the minimum total amount of bribery required to achieve this.

Constraints

• All input values are integers.
• 1 \le T \le 10^4
• 0 \le A_i \le 10^8
• 1 \le A_1+A_2+A_3+A_4+A_5
• 1 \le P_i \le 10^8

Sample Input 1

6
1 0 1 0 0
1 2 3 4 5
0 2 2 0 0
1 1 1 1 5
0 1 2 0 0
1 1 1 5 3
1 1 1 0 0
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
100000000 100000000 100000000 0 0
100000000 100000000 100000000 100000000 100000000

Sample Output 1

5
2
3
2
0
15000000000000000

This input contains six test cases.

• For the first test case, you can, for example, do the following to have an average rating of at least 3 stars with a bribe of 5 yen, which is the minimum possible amount.
  • Initially, there are 1,0,1,0,0 reviews with 1,2,3,4,5 stars, respectively.
  • Pay a bribe of P_5 = 5 yen to add one 5-star review.
  • As a result, there are 1,0,1,0,1 reviews with 1,2,3,4,5 stars, respectively, averaging 3 stars.
• For the second test case, you can, for example, do the following to have an average rating of at least 3 stars with a bribe of 2 yen, which is the minimum possible amount.
  • Initially, there are 0,2,2,0,0 reviews with 1,2,3,4,5 stars, respectively.
  • Pay a bribe of P_4 \times 2 = 2 yen to add two 4-star reviews.
  • As a result, there are 0,2,2,2,0 reviews of with 1,2,3,4,5 stars, respectively, averaging 3 stars.
• For the third test case, you can, for example, do the following to have an average rating of at least 3 stars with a bribe of 3 yen, which is the minimum possible amount.
  • Initially, there are 0,1,2,0,0 reviews with 1,2,3,4,5 stars, respectively.
  • Pay a bribe of P_5 = 3 yen to add one 5-star review.
  • As a result, there are 0,1,2,0,1 reviews with 1,2,3,4,5 stars, respectively, averaging 3.25 stars.
• For the fourth test case, you can, for example, do the following to have an average rating of at least 3 stars with a bribe of 2 yen, which is the minimum possible amount.
  • Initially, there are 1,1,1,0,0 reviews with 1,2,3,4,5 stars, respectively.
  • Pay a bribe of P_4 = 1 yen to add one 4-star review.
  • Pay a bribe of P_5 = 1 yen to add one 5-star review.
  • As a result, there are 1,1,1,1,1 reviews with 1,2,3,4,5 stars, respectively, averaging 3 stars.
• For the fifth test case, you can, for example, do the following to have an average rating of at least 3 stars with a bribe of 0 yen, which is the minimum possible amount.
  • Initially, there are 0,0,0,0,1 reviews with 1,2,3,4,5 stars, respectively.
  • Since the average is already 5, which is not less than 3, give no bribe.
• For the sixth test case, note that the answer may not fit into a 32-bit signed integer.

Problem Statement

There is a roulette that produces an integer from 1,2,\dots,N with equal probability.
Two players use it to play the following game:

• The players take turns spinning the roulette.
  • If the produced integer has not appeared before, nothing happens.
  • Otherwise, the player who spun the roulette pays a fine of 1 yen.
• The game immediately ends when all of the N integers have appeared at least once.

For each of the first and second players, find the expected value of the amount of the fine paid before the game ends, modulo 998244353.

Constraints

• N is an integer such that 1 \le N \le 10^6.

Sample Input 1

1

Sample Output 1

0 0

In this input, N=1.
When the first player spins the roulette, it always produces 1, ending the game immediately.
Thus, the expected values of the amounts of the fines paid by the first and second players are both 0.

Sample Input 2

2

Sample Output 2

332748118 665496236

In this input, N=2. Here is a possible progression of the game:

• The first player spins the roulette, and it produces 2. Nothing happens.
• The second player spins the roulette, and it produces 2. The second player pays a fine of 1 yen.
• The first player spins the roulette, and it produces 2. The first player pays a fine of 1 yen.
• The second player spins the roulette, and it produces 1. Nothing happens.
• At this point, both 1 and 2 have appeared at least once, so the game immediately ends.
• In this progression, the amount of the fine paid by the first player is 1 yen, and the amount of the fine paid by the second player is also 1 yen.

It can be shown that the expected value of the amount of the fine paid by the first player is \frac{1}{3} yen, and the expected value of the amount of the fine paid by the second player is \frac{2}{3} yen.

Sample Input 3

3

Sample Output 3

174692763 324429416

Problem Statement

Solve the following problem for T test cases.

Given an integer N, find the number of integers x that satisfy all of the following conditions:

• 1 \le x \le N
• Let y = \lfloor \sqrt{x} \rfloor. When x and y are written in decimal notation (without leading zeros), y is a prefix of x.

Constraints

• T is an integer such that 1 \le T \le 10^5.
• N is an integer such that 1 \le N \le 10^{18}.

Sample Input 1

2
1
174

Sample Output 1

1
22

This input contains two test cases.

• For the first test case, x=1 satisfies the conditions since y = \lfloor \sqrt{1} \rfloor = 1.
• For the second test case, for example, x=100 satisfies the conditions since y = \lfloor \sqrt{100} \rfloor = 10.

Problem Statement

You are given integers N and K. Consider a sequence a=(a_1,a_2,\dots,a_K) of length K that satisfies all of the following conditions:

• a_i is an integer such that 1 \le a_i \le N.
• All elements in a are different.

Let us arrange all possible sequences a in lexicographical order to form a "sequence of sequences" called the dictionary s.

Given a sequence P that exists in the dictionary s, answer the following question for each integer t=1,2,\dots,N:

• Find the number, modulo 998244353, of sequences b that satisfy all of the following conditions:
  • The sequence b exists in the dictionary s.
  • The integer t is contained in the sequence b.
  • The sequence b is lexicographically less than or equal to the sequence P.

Constraints

• All input values are integers.
• 1 \le K \le N \le 3 \times 10^5
• P satisfies the condition in the problem statement.

Sample Input 1

4 2
3 2

Sample Output 1

5
5
4
2

In this input, N=4,K=2.
Here, the dictionary s is ((1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3)).

Among the sequences in the dictionary s that are lexicographically less than or equal to (3,2),

• five sequences contain 1: (1,2),(1,3),(1,4),(2,1),(3,1),
• five sequences contain 2: (1,2),(2,1),(2,3),(2,4),(3,2),
• four sequences contain 3: (1,3),(2,3),(3,1),(3,2),
• two sequences contain 4: (1,4),(2,4).

Sample Input 2

18 13
5 13 11 2 18 1 10 15 17 4 12 7 3

Sample Output 2

925879409
905921009
665544804
665544719
783035803
349952762
349952758
349952757
349952757
349921178
212092637
710350150
378895603
129113201
129111892
129098081
129096772
110181652

Problem Statement

Players Alice and Bob play a game using sequences L and R of length N, as follows.

• The game consists of N turns.
• If i is odd, turn i is played by Alice; if i is even, turn i is played by Bob.
• Initially, there is a pile with some number of stones.
• For i=1,2,\dots,N in this order, they perform the following operation (called turn i):
  • The player who plays turn i takes an integer number of stones between L_i and R_i, inclusive, from the pile.
  • If the player cannot take stones satisfying the above, they lose, and the other player wins.
• If neither player has lost by the end of turn N, the game ends in a draw.

Before the game starts, both players are informed of the sequences L and R and the number of stones in the pile at the start of the game.

It can be proved that the game has exactly one of the following three consequences:

• Alice ... Alice has a winning strategy.
• Bob ... Bob has a winning strategy.
• Draw ... Neither player has a winning strategy.

Answer Q queries about this game. The i-th query is as follows:

• Assume that the pile contains C_i stones at the start of the game. Report the consequence of the game: Alice, Bob, or Draw.

Constraints

• N, L_i, R_i, Q, and C_i are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le L_i \le R_i \le 10^9
• 1 \le Q \le 3 \times 10^5
• 1 \le C_i \le \sum_{i=1}^{N} R_i

Sample Input 1

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

Sample Output 1

Alice
Alice
Alice
Bob
Bob
Alice
Alice
Alice
Draw
Draw
Draw

This input contains 11 queries.

• When C_i \le 3, Alice can take all C_i stones on turn 1, leaving no stones in the pile, so Alice has a winning strategy.
• When 4 \le C_i \le 5, Bob has a winning strategy.
• When 6 \le C_i \le 8, Alice has a winning strategy.
• When C_i \ge 9, neither player has a winning strategy.
  • For example, if C_i=9, the game could proceed as follows:
    • On turn 1, Alice takes 3 stones. 6 stones remain.
    • On turn 2, Bob takes 1 stone. 5 stones remain.
    • On turn 3, Alice takes 4 stones. 1 stone remains.
    • On turn 4, Bob takes 1 stone. No stones remain.
    • Since neither player has lost by the end of turn 4, the game ends in a draw.
  • Various other progressions are possible, but it can be shown that when C_i=9, neither player has a winning strategy (if both players play optimally, the game will end in a draw).