Problem Statement

You are given three digits A,B,C between 1 and 9, inclusive.

Find the maximum value among all 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them.

Constraints

• A,B,C are digits between 1 and 9, inclusive.

Sample Input 1

3 2 4

Sample Output 1

432

There are six 3-digit integers that can be formed by arranging A,B,C in any order and concatenating them: 324, 342, 234, 243, 432, 423; the maximum value among them is 432.

Sample Input 2

7 7 7

Sample Output 2

777

Only 777 can be formed.

Sample Input 3

9 1 9

Sample Output 3

991

Problem Statement

You are given a positive integer X.

Find the minimum value among all positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X (without leading zeros) such that there is no leading zero.

Constraints

• 1\leq X < 10^5
• X is an integer.

Sample Input 1

903

Sample Output 1

309

There are four positive integers that can be obtained by rearranging the digits appearing in the decimal representation of X such that there is no leading zero: 903, 930, 309, 390; the minimum value among them is 309.

Sample Input 2

432

Sample Output 2

234

Sample Input 3

100

Sample Output 3

100

Problem Statement

You have an unlimited supply of two types of candies: small candies and large candies. The weight of a small candy is X grams, and the weight of a large candy is Y grams. Large candies are heavier than small candies (that is, X < Y).

There are N children, numbered 1 to N.

You have decided to distribute candies so that the following conditions are satisfied:

• For i=1,\dots,N, child i receives exactly A_i candies in total of the two types.
• The total weights of candies distributed to the N children are all equal.

Determine whether there exists a distribution method that satisfies the conditions. If it exists, find the maximum possible value for the number of large candies distributed.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq X < Y \leq 10^9
• All input values are integers.

Sample Input 1

3 6 8
11 10 13

Sample Output 1

18

You can distribute candies as follows so that the total weights of candies distributed to the children are all equal.

• Child 1 receives 4 small candies and 7 large candies. The total weight is 6 \times 4 + 8 \times 7 = 80 grams.
• Child 2 receives 0 small candies and 10 large candies. The total weight is 6 \times 0 + 8 \times 10 = 80 grams.
• Child 3 receives 12 small candies and 1 large candy. The total weight is 6 \times 12 + 8 \times 1 = 80 grams.

In this distribution method, a total of 18 large candies are distributed.

There is no distribution method that satisfies the conditions and distributes more than 18 large candies. Therefore, the answer is 18.

Sample Input 2

2 3 4
3 5

Sample Output 2

-1

There is no distribution method that satisfies the conditions.

Sample Input 3

8 4 32
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

8000000000

The answer may not fit in a 32-bit integer.

Problem Statement

There is an infinitely large two-dimensional grid. The color of cell (x,y) is black if 0 \leq x \leq X-1 and 0 \leq y \leq Y-1, and white otherwise.

N great storms occur in order on this grid. The i-th great storm updates the color of each cell on the grid according to a rule represented by a character C_i and integers A_i, B_i.

In the i-th great storm, the color of cell (x, y) after the great storm is:

• In case C_i is X,
  • if x < A_i, it becomes the color of cell (x, y + B_i) before the great storm;
  • if x \geq A_i, it becomes the color of cell (x, y - B_i) before the great storm.
• In case C_i is Y,
  • if y < A_i, it becomes the color of cell (x + B_i, y) before the great storm;
  • if y \geq A_i, it becomes the color of cell (x - B_i, y) before the great storm.

Two black cells (x_1, y_1), (x_2, y_2) are adjacent if and only if |x_1 - x_2| + |y_1 - y_2| = 1. Also, two black cells c_1, c_2 are connected if and only if one can move from cell c_1 to cell c_2 by repeatedly moving to adjacent black cells.

A non-empty set S of black cells is a connected component if and only if S satisfies the following conditions:

• Any two cells in S are connected.
• Every black cell not in S is not connected to any cell in S.

For the grid after all N great storms have occurred, find the number of connected components and output the number of cells in each connected component in ascending order.

Constraints

• N, X, Y are integers.
• 1 \leq N \leq 14
• 1 \leq X,Y \leq 10^8
• C_i is X or Y.
• A_i, B_i are integers.
• -10^8 \leq A_i, B_i \leq 10^8

Sample Input 1

2 3 5
X 2 2
Y -1 1

Sample Output 1

2
2 13

The grid changes as shown in the following image due to the great storms (the rightward direction is the positive direction of the x-axis, and the upward direction is the positive direction of the y-axis).

In the final grid, the following two connected components exist:

• A connected component consisting of cells (-1,-2), (0,-2).
• A connected component consisting of cells (1,-1), (1,0), (1,1), (1,2), (2,-1), (2,0), (2,1), (2,2), (3,2), (3,3), (3,4), (3,5), (3,6).

Note that the number of cells in each connected component must be output in ascending order.

Sample Input 2

14 68875272 94216928
X 1630731 32914676
X 17164413 -33684569
X 26798060 5418308
X 34094469 -45675954
X 43889566 34125482
X 56836569 -22217058
X 64045210 27857939
Y -54561094 11587606
Y 93548188 32214521
Y -77361096 25750481
Y 27724899 1810420
Y 80945185 -7871305
Y 14782822 -2565089
Y 54687684 -22884393

Sample Output 2

8
21105046168287 22050167303226 33624667752182 223328231190194 441936776830492 1141371400772596 1141702254882183 3464097998105256

The output value may not fit in a 32-bit integer.

Problem Statement

You are given an integer sequence A=(A_1, A_2, \dots, A_N) of length N.

You are given Q queries, which you should process in order. Each query is in one of the following formats:

• 1 x y : Change the value of A_x to y.
• 2 l r : Find the value of \displaystyle \sum_{1\leq i\leq N} \max(l, \min(r, A_i)).

Constraints

• 1\leq N \leq 5\times 10^5
• 1\leq Q \leq 2\times 10^5
• 0\leq A_i \leq 5\times 10^5
• For queries of the first type,
  • 1\leq x\leq N
  • 0\leq y \leq 5\times 10^5
• For queries of the second type,
  • 0\leq l,r \leq 5\times 10^5
• All inputs are integers.

Sample Input 1

3 4
4 3 2
1 1 7
2 3 5
1 2 0
2 4 2

Sample Output 1

11
12

Initially, A=(4,3,2).

• First query: Change the value of A_1 to 7. A becomes (7,3,2).
• Second query: Output \max(3, \min(5, 7))+\max(3, \min(5, 3))+\max(3, \min(5, 2))=5+3+3=11.
• Third query: Change the value of A_2 to 0. A becomes (7,0,2).
• Fourth query: Output \max(4, \min(2, 7))+\max(4, \min(2, 0))+\max(4, \min(2, 2))=4+4+4=12.

Sample Input 2

8 10
320 578 244 604 145 839 156 857
2 400 556
1 5 168
2 254 62
2 145 301
1 1 23
1 3 0
2 413 758
2 297 613
1 8 451
2 598 692

Sample Output 2

3824
2032
2073
4350
3596
4884

Problem Statement

There are N children, numbered 1 to N.

Child i has A_i candies.

Your goal is to execute the following operation as few times as possible so that eventually all N children have the same number of candies.

• Choose two distinct children x,y, and choose a positive integer z not exceeding the number of candies child x has. Take z candies from child x and give them to child y.

Determine whether there exists a sequence of operations such that eventually all N children have the same number of candies. If it exists, find one such sequence with the minimum number of operations.

Constraints

• 2 \leq N \leq 20
• 1 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

4
1 7 4 8

Sample Output 1

3
2 3 1
2 4 1
4 1 4

In this sample output, the operations are executed as follows:

1. Take 1 candy from child 2 and give it to child 3. Immediately after this, the number of candies each child has is 1,6,5,8.
2. Take 1 candy from child 2 and give it to child 4. Immediately after this, the number of candies each child has is 1,5,5,9.
3. Take 4 candies from child 4 and give them to child 1. Immediately after this, the number of candies each child has is 5,5,5,5.

Eventually, all N children have exactly five candies each.

Sample Input 2

2
100 3

Sample Output 2

-1

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a sequence of positive integers B=(B_1,B_2,\dots,B_M) of length M.

Find the value of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} \binom{A_i}{B_j}, modulo 998244353.

Here, \displaystyle \binom{x}{y} represents the number of ways to choose y objects from x objects (binomial coefficient), and particularly, it is 0 if x < y.

Constraints

• 1\leq N,M \leq 5\times 10^5
• 1\leq A_i,B_j \leq 5\times 10^5
• All input values are integers.

Sample Input 1

3 2
2 5 4
1 3

Sample Output 1

25

The answer is \displaystyle \binom{2}{1}+\binom{2}{3}+\binom{5}{1}+\binom{5}{3}+\binom{4}{1}+\binom{4}{3}=2+0+5+10+4+4=25.

Sample Input 2

4 4
2 5 1 5
2 1 2 4

Sample Output 2

65

Sample Input 3

6 8
203497 47202 407775 394325 463982 304784
468417 302156 131932 235902 395728 78537 223857 330739

Sample Output 3

602855848