Problem Statement

There are N cards, numbered 1 to N.

Card i has a positive integer A_i written on it.

You can choose three of these cards and concatenate the integers written on them in any order you like to make a new integer. For example, if you choose cards with 1, 23, and 4 written on them, you can make integers such as 1234 and 4231.

Find the maximum integer you can make.

Constraints

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

Sample Input 1

5
1 4 3 5 8

Sample Output 1

854

If you choose cards with 4, 5, and 8 written on them, you can make 458, 485, 548, 584, 845, or 854.

You can make nothing greater than 854, so the answer is 854.

Sample Input 2

8
813 921 481 282 120 900 555 409

Sample Output 2

921900813

Problem Statement

You are given a sequence of N non-negative integers: A=(A_1,A_2,\dots,A_N). You may perform the following operation at most M times (possibly zero):

• choose an integer i such that 1 \le i \le N and add 1 to A_i.

Then, you will choose K of the elements of A.

Find the maximum possible value of the bitwise \mathrm{AND} of the elements you choose.

​

Constraints

• 1 \le K \le N \le 2 \times 10^5
• 0 \le M < 2^{30}
• 0 \le A_i < 2^{30}
• All values in input are integers.

Sample Input 1

4 8 2
1 2 4 8

Sample Output 1

10

If you do the following, the bitwise \mathrm{AND} of the elements you choose will be 10.

• Perform the operation on A_3 six times. Now, A_3 = 10.
• Perform the operation on A_4 twice. Now, A_4 = 10.
• Choose A_3 and A_4, whose bitwise \mathrm{AND} is 10.

There is no way to choose two elements whose bitwise \mathrm{AND} is greater than 10, so the answer is 10.

Sample Input 2

5 345 3
111 192 421 390 229

Sample Output 2

461

Problem Statement

How many sets S consisting of non-negative integers between 0 and 2^N-1 (inclusive) satisfy the following condition? Print the count modulo 998244353.

• Every non-empty subset T of S satisfies at least one of the following:
  • The number of elements in T is odd.
  • The \mathrm{XOR} of the elements in T is not zero.

Constraints

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

Sample Input 1

2

Sample Output 1

15

Sets such as \lbrace 0,2,3 \rbrace, \lbrace 1 \rbrace, and \lbrace \rbrace satisfy the condition.

On the other hand, \lbrace 0,1,2,3 \rbrace does not.

This is because the subset \lbrace 0,1,2,3 \rbrace of \lbrace 0,1,2,3 \rbrace has an even number of elements, whose bitwise \mathrm{XOR} is 0.

Sample Input 2

146

Sample Output 2

743874490

Problem Statement

A fantastic IS is an integer sequence of length N whose every element is between 1 and M (inclusive) that satisfies the following condition.

• For every integer i such that 1 \le i \le K, one of the following holds.
  • A_{P_i} < X_i and A_{Q_i} < Y_i;
  • A_{P_i} = X_i and A_{Q_i} = Y_i;
  • A_{P_i} > X_i and A_{Q_i} > Y_i.

Determine whether a fantastic IS exists. If it does, find the minimum possible sum of the elements in a fantastic IS.

Constraints

• 1 \le N,M,K \le 2 \times 10^5
• 1 \le P_i,Q_i \le N
• 1 \le X_i,Y_i \le M
• P_i \neq Q_i
• All values in input are integers.

Sample Input 1

3 4 3
3 1 1 2
1 1 2 2
3 4 1 4

Sample Output 1

6

A=(2,3,1) fully satisfies the condition and thus is a fantastic IS, whose sum of the elements is 6.

There is no fantastic IS whose sum of the elements is less than 6, so the answer is 6.

Sample Input 2

2 2 2
1 1 2 2
2 1 1 2

Sample Output 2

-1

There is no fantastic IS, so -1 should be printed.

Sample Input 3

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

Sample Output 3

12

Problem Statement

You are given a sequence of N positive integers: A=(A_1,A_2,\dots,A_N).

How many integer sequences B consisting of integers between 1 and N (inclusive) satisfy all of the following conditions? Print the count modulo 998244353.

• For each integer i such that 1 \le i \le N, there are exactly A_i occurrences of i in B.
• For each integer i such that 1 \le i \le |B|-1, it holds that |B_i - B_{i+1}|=1.

Constraints

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

Sample Input 1

3
2 3 1

Sample Output 1

6

B can be the following six sequences.

• (1,2,1,2,3,2)
• (1,2,3,2,1,2)
• (2,1,2,1,2,3)
• (2,1,2,3,2,1)
• (2,3,2,1,2,1)
• (3,2,1,2,1,2)

Thus, the answer is 6.

Sample Input 2

1
200000

Sample Output 2

0

There may be no sequence that satisfies the conditions.

Sample Input 3

6
12100 31602 41387 41498 31863 12250

Sample Output 3

750337372

Problem Statement

The following process is carried out on a permutation P of (1,2,\dots,N).

We have N cards, numbered 1 to N. Card i has the integer P_i written on it.

There are an integer X=1 and a boy called PCT, who initially has nothing. PCT does the following procedure for each i=1,2,\dots,N in this order.

• Get Card i. Then, repeat the following action as long as he has a card with X written on it:
• eat the card with X written on it, and then add 1 to X.
• If PCT currently has M or more cards, throw away all cards he has and terminate the process, without performing any more procedures.

Here, let us define the score of the permutation P as follows:

• if the process is terminated by throwing away cards, the score of P is 0;
• if the process is carried out through the end without throwing away cards, the score of P is \prod_{i=1}^{N-1} ( the number of cards PCT has at the end of the i-th procedure ).

There are N! permutations P of (1,2,\dots,N). Find the sum of the scores of all those permutations, modulo 998244353.

Constraints

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

Sample Input 1

3 2

Sample Output 1

1

For P=(3,1,2), the process goes as follows.

• The first procedure:
  • PCT gets Card 1.
  • PCT currently has 1 card, so he goes on.
• The second procedure:
  • PCT gets Card 2.
  • PCT eats Card 2 and make X = 2.
  • PCT currently has 1 card, so he goes on.
• The third procedure:
  • PCT gets Card 3.
  • PCT eats Cards 1,3 and make X = 4.
  • PCT currently has 0 cards, so he goes on.

The process is carried out through the end, so the score of (3,1,2) is 1 \times 1 = 1.

Other than (3,1,2), there is no permutation with a score of 1 or greater, so the answer is 1.

Sample Input 2

3 3

Sample Output 2

5

Sample Input 3

146146 146

Sample Output 3

103537573