Problem Statement

We have two bottles for holding water.

Bottle 1 can hold up to A milliliters of water, and now it contains B milliliters of water.

Bottle 2 contains C milliliters of water.

We will transfer water from Bottle 2 to Bottle 1 as much as possible.

How much amount of water will remain in Bottle 2?

Constraints

• All values in input are integers.
• 1 \leq B \leq A \leq 20
• 1 \leq C \leq 20

Sample Input 1

6 4 3

Sample Output 1

1

We will transfer two milliliters of water from Bottle 2 to Bottle 1, and one milliliter of water will remain in Bottle 2.

Sample Input 2

8 3 9

Sample Output 2

4

Sample Input 3

12 3 7

Sample Output 3

0

Problem Statement

Given is an integer N. Find the number of positive integers less than or equal to N that have an odd number of digits (in base ten without leading zeros).

Constraints

• 1 \leq N \leq 10^5

Sample Input 1

11

Sample Output 1

9

Among the positive integers less than or equal to 11, nine integers have an odd number of digits: 1, 2, \ldots, 9.

Sample Input 2

136

Sample Output 2

46

In addition to 1, 2, \ldots, 9, another 37 integers also have an odd number of digits: 100, 101, \ldots, 136.

Sample Input 3

100000

Sample Output 3

90909

Problem Statement

There are N squares arranged in a row from left to right. The height of the i-th square from the left is H_i.

For each square, you will perform either of the following operations once:

• Decrease the height of the square by 1.
• Do nothing.

Determine if it is possible to perform the operations so that the heights of the squares are non-decreasing from left to right.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^5
• 1 \leq H_i \leq 10^9

Sample Input 1

5
1 2 1 1 3

Sample Output 1

Yes

You can achieve the objective by decreasing the height of only the second square from the left by 1.

Sample Input 2

4
1 3 2 1

Sample Output 2

No

Sample Input 3

5
1 2 3 4 5

Sample Output 3

Yes

Sample Input 4

1
1000000000

Sample Output 4

Yes

Problem Statement

Given is a string S consisting of L and R.

Let N be the length of S. There are N squares arranged from left to right, and the i-th character of S from the left is written on the i-th square from the left.

The character written on the leftmost square is always R, and the character written on the rightmost square is always L.

Initially, one child is standing on each square.

Each child will perform the move below 10^{100} times:

• Move one square in the direction specified by the character written in the square on which the child is standing. L denotes left, and R denotes right.

Find the number of children standing on each square after the children performed the moves.

Constraints

• S is a string of length between 2 and 10^5 (inclusive).
• Each character of S is L or R.
• The first and last characters of S are R and L, respectively.

Sample Input 1

RRLRL

Sample Output 1

0 1 2 1 1

• After each child performed one move, the number of children standing on each square is 0, 2, 1, 1, 1 from left to right.
• After each child performed two moves, the number of children standing on each square is 0, 1, 2, 1, 1 from left to right.
• After each child performed 10^{100} moves, the number of children standing on each square is 0, 1, 2, 1, 1 from left to right.

Sample Input 2

RRLLLLRLRRLL

Sample Output 2

0 3 3 0 0 0 1 1 0 2 2 0

Sample Input 3

RRRLLRLLRRRLLLLL

Sample Output 3

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

Problem Statement

We have a sequence of N integers: A_1, A_2, \cdots, A_N.

You can perform the following operation between 0 and K times (inclusive):

• Choose two integers i and j such that i \neq j, each between 1 and N (inclusive). Add 1 to A_i and -1 to A_j, possibly producing a negative element.

Compute the maximum possible positive integer that divides every element of A after the operations. Here a positive integer x divides an integer y if and only if there exists an integer z such that y = xz.

Constraints

• 2 \leq N \leq 500
• 1 \leq A_i \leq 10^6
• 0 \leq K \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
8 20

Sample Output 1

7

7 will divide every element of A if, for example, we perform the following operation:

• Choose i = 2, j = 1. A becomes (7, 21).

We cannot reach the situation where 8 or greater integer divides every element of A.

Sample Input 2

2 10
3 5

Sample Output 2

8

Consider performing the following five operations:

• Choose i = 2, j = 1. A becomes (2, 6).
• Choose i = 2, j = 1. A becomes (1, 7).
• Choose i = 2, j = 1. A becomes (0, 8).
• Choose i = 2, j = 1. A becomes (-1, 9).
• Choose i = 1, j = 2. A becomes (0, 8).

Then, 0 = 8 \times 0 and 8 = 8 \times 1, so 8 divides every element of A. We cannot reach the situation where 9 or greater integer divides every element of A.

Sample Input 3

4 5
10 1 2 22

Sample Output 3

7

Sample Input 4

8 7
1 7 5 6 8 2 6 5

Sample Output 4

5

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

• f(T) := (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq x_i, y_i \leq 10^9
• x_i \neq x_j (i \neq j)
• y_i \neq y_j (i \neq j)
• All values in input are integers.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

• f(\{P_1\}) = 1
• f(\{P_2\}) = 1
• f(\{P_3\}) = 1
• f(\{P_1, P_2\}) = 2
• f(\{P_2, P_3\}) = 2
• f(\{P_3, P_1\}) = 3
• f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.