Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

You are given N as input. Print Yes if N is a 321-like Number, and No otherwise.

Constraints

• All input values are integers.
• 1 \le N \le 99999

Sample Input 1

321

Sample Output 1

Yes

For N=321, the following holds:

• The first digit from the top, 3, is greater than the second digit from the top, 2.
• The second digit from the top, 2, is greater than the third digit from the top, 1.

Thus, 321 is a 321-like Number.

Sample Input 2

123

Sample Output 2

No

For N=123, the following holds:

• The first digit from the top, 1, is not greater than the second digit from the top, 2.

Thus, 123 is not a 321-like Number.

Sample Input 3

1

Sample Output 3

Yes

Sample Input 4

86411

Sample Output 4

No

Problem Statement

There is an exam structured as follows.

• The exam consists of N rounds called round 1 to N.
• In each round, you are given an integer score between 0 and 100, inclusive.
• Your final grade is the sum of the N-2 of the scores earned in the rounds excluding the highest and lowest.
  • Formally, let S=(S_1,S_2,\dots,S_N) be the sequence of the scores earned in the rounds sorted in ascending order, then the final grade is S_2+S_3+\dots+S_{N-1}.

Now, N-1 rounds of the exam have ended, and your score in round i was A_i.
Print the minimum score you must earn in round N for a final grade of X or higher.
If your final grade will never be X or higher no matter what score you earn in round N, print -1 instead.
Note that your score in round N can only be an integer between 0 and 100.

Constraints

• All input values are integers.
• 3 \le N \le 100
• 0 \le X \le 100 \times (N-2)
• 0 \le A_i \le 100

Sample Input 1

5 180
40 60 80 50

Sample Output 1

70

Your scores in the first four rounds were 40, 60, 80, and 50.
If you earn a score of 70 in round 5, the sequence of the scores sorted in ascending order will be S=(40,50,60,70,80), for a final grade of 50+60+70=180.
It can be shown that 70 is the minimum score you must earn for a final grade of 180 or higher.

Sample Input 2

3 100
100 100

Sample Output 2

0

Your scores in the first two rounds were 100 and 100.
If you earn a score of 0 in round 3, the sequence of the scores sorted in ascending order will be S=(0,100,100), for a final grade of 100.
Note that the highest score, 100, is earned multiple times, and only one of them is excluded. (The same goes for the lowest score.)
It can be shown that 0 is the minimum score you must earn for a final grade of 100 or higher.

Sample Input 3

5 200
0 0 99 99

Sample Output 3

-1

Your scores in the first four rounds were 0, 0, 99, and 99.
It can be shown that your final grade will never be 200 or higher no matter what score you earn in round 5.

Sample Input 4

10 480
59 98 88 54 70 24 8 94 46

Sample Output 4

45

Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition. This definition is the same as the one in Problem A.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

Find the K-th smallest 321-like Number.

Constraints

• All input values are integers.
• 1 \le K
• At least K 321-like Numbers exist.

Sample Input 1

15

Sample Output 1

32

The 321-like Numbers are (1,2,3,4,5,6,7,8,9,10,20,21,30,31,32,40,\dots) from smallest to largest.
The 15-th smallest of them is 32.

Sample Input 2

321

Sample Output 2

9610

Sample Input 3

777

Sample Output 3

983210

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

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

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24

• If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
• If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
• If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
• If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

Sample Output 3

2115597124

Problem Statement

There is a tree with N vertices numbered 1 to N. For each i\ (2 \leq i \leq N), there is an edge connecting vertex i and vertex \lfloor \frac{i}{2} \rfloor. There are no other edges.

In this tree, find the number of vertices whose distance from vertex X is K. Here, the distance between two vertices u and v is defined as the number of edges in the simple path connecting vertices u and v.

You have T test cases to solve.

Constraints

• 1\leq T \leq 10^5
• 1\leq N \leq 10^{18}
• 1\leq X \leq N
• 0\leq K \leq N-1
• All input values are integers.

Sample Input 1

5
10 2 0
10 2 1
10 2 2
10 2 3
10 2 4

Sample Output 1

1
3
4
2
0

The tree for N=10 is shown in the following figure.

Here,

• There is 1 vertex, 2, whose distance from vertex 2 is 0.
• There are 3 vertices, 1,4,5, whose distance from vertex 2 is 1.
• There are 4 vertices, 3,8,9,10, whose distance from vertex 2 is 2.
• There are 2 vertices, 6,7, whose distance from vertex 2 is 3.
• There are no vertices whose distance from vertex 2 is 4.

Sample Input 2

10
822981260158260522 52 20
760713016476190629 2314654 57
1312150450968417 1132551176249851 7
1000000000000000000 1083770654 79
234122432773361868 170290518806790 23
536187734191890310 61862 14
594688604155374934 53288633578 39
1000000000000000000 120160810 78
89013034180999835 14853481725739 94
463213054346948152 825589 73

Sample Output 2

1556480
140703128616960
8
17732923532771328
65536
24576
2147483640
33776997205278720
7881299347898368
27021597764222976

Problem Statement

We have a box, which is initially empty.
Let us perform a total of Q operations of the following two types in the order they are given in the input.

+ x

Type 1: Put into the box a ball with the integer x written on it.

- x

Type 2: Remove from the box a ball with the integer x written on it.
It is guaranteed that the box contains a ball with the integer x written on it before the operation.

For the box after each operation, solve the following problem.

Find the number, modulo 998244353, to pick up some number of balls from the box so that the integers written on them sum to K.
All balls in the box are distinguishable.

Constraints

• All input values are integers.
• 1 \le Q \le 5000
• 1 \le K \le 5000
• For each type-1 operation, 1 \le x \le 5000.
• All the operations satisfy the condition in the problem statement.

Sample Input 1

15 10
+ 5
+ 2
+ 3
- 2
+ 5
+ 10
- 3
+ 1
+ 3
+ 3
- 5
+ 1
+ 7
+ 4
- 3

Sample Output 1

0
0
1
0
1
2
2
2
2
2
1
3
5
8
5

This input contains 15 operations.

After the last operation, the box contains the balls (5,10,1,3,1,7,4).
There are five ways to pick up balls for a sum of 10:

• 5+1+3+1 (the 1-st, 3-rd, 4-th, 5-th balls)
• 5+1+4 (the 1-st, 3-rd, 7-th balls)
• 5+1+4 (the 1-st, 5-th, 7-th balls)
• 10 (the 2-nd ball)
• 3+7 (the 4-th, 6-th balls)

Problem Statement

You are creating an electrical circuit using N parts numbered 1 to N and M cables. These parts have a total of M red terminals and M blue terminals, with the i-th red terminal attached to part R_i and the i-th blue terminal attached to part B_i. Each cable connects one red terminal and one blue terminal. In particular, it is allowed to connect two terminals attached to the same part. You cannot connect two or more cables to a terminal. Therefore, there are M! ways in total to connect the M cables (the cables are not distinguished from each other).

Let s be the number of connected components when seeing this circuit as a graph with parts as vertices and cables as edges. Find the expected value, modulo 998244353, of s when randomly choosing the way to connect the M cables out of the M! ways.

Constraints

• 1\leq N \leq 17
• 1 \leq M \leq 10^5
• 1 \leq R_i, B_i \leq N
• All input values are integers.

Sample Input 1

3 2
1 2
3 2

Sample Output 1

499122178

Let (i, j) denote the action of connecting the i-th red terminal and the j-th blue terminal with a cable.

• For (1,1), (2,2): There will be two connected components, \lbrace 1,3 \rbrace and \lbrace 2 \rbrace, so s=2.
• For (1,2), (2,1): The whole graph constitutes one connected component, so s=1.

Thus, the expected value of s is \frac{3}{2} \equiv 499122178 \pmod {998244353}.

Sample Input 2

17 5
1 1 1 1 1
1 1 1 1 1

Sample Output 2

17

s=N no matter how you connect the cables.

Sample Input 3

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

Sample Output 3

608849831