Problem Statement

X and A are integers between 0 and 9 (inclusive).

If X is less than A, print 0; if X is not less than A, print 10.

Constraints

• 0 \leq X, A \leq 9
• All values in input are integers.

Sample Input 1

3 5

Sample Output 1

0

3 is less than 5, so we should print 0.

Sample Input 2

7 5

Sample Output 2

10

7 is not less than 5, so we should print 10.

Sample Input 3

6 6

Sample Output 3

10

6 is not less than 6, so we should print 10.

Problem Statement

A ball will bounce along a number line, making N + 1 bounces. It will make the first bounce at coordinate D_1 = 0, and the i-th bounce (2 \leq i \leq N+1) at coordinate D_i = D_{i-1} + L_{i-1}.

How many times will the ball make a bounce where the coordinate is at most X?

Constraints

• 1 \leq N \leq 100
• 1 \leq L_i \leq 100
• 1 \leq X \leq 10000
• All values in input are integers.

Sample Input 1

3 6
3 4 5

Sample Output 1

2

The ball will make a bounce at the coordinates 0, 3, 7 and 12, among which two are less than or equal to 6.

Sample Input 2

4 9
3 3 3 3

Sample Output 2

4

The ball will make a bounce at the coordinates 0, 3, 6, 9 and 12, among which four are less than or equal to 9.

Problem Statement

There is a rectangle in a coordinate plane. The coordinates of the four vertices are (0,0), (W,0), (W,H), and (0,H). You are given a point (x,y) which is within the rectangle or on its border. We will draw a straight line passing through (x,y) to cut the rectangle into two parts. Find the maximum possible area of the part whose area is not larger than that of the other. Additionally, determine if there are multiple ways to cut the rectangle and achieve that maximum.

Constraints

• 1 \leq W,H \leq 10^9
• 0\leq x\leq W
• 0\leq y\leq H
• All values in input are integers.

Sample Input 1

2 3 1 2

Sample Output 1

3.000000 0

The line x=1 gives the optimal cut, and no other line does.

Sample Input 2

2 2 1 1

Sample Output 2

2.000000 1

Problem Statement

You are given a sequence of positive integers of length N, A=a_1,a_2,…,a_{N}, and an integer K. How many contiguous subsequences of A satisfy the following condition?

• (Condition) The sum of the elements in the contiguous subsequence is at least K.

We consider two contiguous subsequences different if they derive from different positions in A, even if they are the same in content.

Note that the answer may not fit into a 32-bit integer type.

Constraints

• 1 \leq a_i \leq 10^5
• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^{10}

Sample Input 1

4 10
6 1 2 7

Sample Output 1

2

The following two contiguous subsequences satisfy the condition:

• A[1..4]=a_1,a_2,a_3,a_4, with the sum of 16
• A[2..4]=a_2,a_3,a_4, with the sum of 10

Sample Input 2

3 5
3 3 3

Sample Output 2

3

Note again that we consider two contiguous subsequences different if they derive from different positions, even if they are the same in content.

Sample Input 3

10 53462
103 35322 232 342 21099 90000 18843 9010 35221 19352

Sample Output 3

36

Problem Statement

You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).

In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?

Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.

For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.

Since the answer can be tremendous, print the number modulo 10^9+7.

Constraints

• 1 \leq N, M \leq 2 \times 10^3
• The length of S is N.
• The length of T is M.
• 1 \leq S_i, T_i \leq 10^5
• All values in input are integers.

Sample Input 1

2 2
1 3
3 1

Sample Output 1

3

S has four subsequences: (), (1), (3), (1, 3).

T has four subsequences: (), (3), (1), (3, 1).

There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.

Sample Input 2

2 2
1 1
1 1

Sample Output 2

6

S has four subsequences: (), (1), (1), (1, 1).

T has four subsequences: (), (1), (1), (1, 1).

There are 1 \times 1 pair of subsequences in which the subsequences are both (), 2 \times 2 pairs of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (1,1), for a total of six pairs. Note again that we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.

Sample Input 3

4 4
3 4 5 6
3 4 5 6

Sample Output 3

16

Sample Input 4

10 9
9 6 5 7 5 9 8 5 6 7
8 6 8 5 5 7 9 9 7

Sample Output 4

191

Sample Input 5

20 20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 5

846527861

Be sure to print the number modulo 10^9+7.

Problem Statement

There are N points in a two-dimensional plane. The initial coordinates of the i-th point are (x_i, y_i). Now, each point starts moving at a speed of 1 per second, in a direction parallel to the x- or y- axis. You are given a character d_i that represents the specific direction in which the i-th point moves, as follows:

• If d_i = R, the i-th point moves in the positive x direction;
• If d_i = L, the i-th point moves in the negative x direction;
• If d_i = U, the i-th point moves in the positive y direction;
• If d_i = D, the i-th point moves in the negative y direction.

You can stop all the points at some moment of your choice after they start moving (including the moment they start moving). Then, let x_{max} and x_{min} be the maximum and minimum among the x-coordinates of the N points, respectively. Similarly, let y_{max} and y_{min} be the maximum and minimum among the y-coordinates of the N points, respectively.

Find the minimum possible value of (x_{max} - x_{min}) \times (y_{max} - y_{min}) and print it.

Constraints

• 1 \leq N \leq 10^5
• -10^8 \leq x_i,\ y_i \leq 10^8
• x_i and y_i are integers.
• d_i is R, L, U, or D.

Sample Input 1

2
0 3 D
3 0 L

Sample Output 1

0

After three seconds, the two points will meet at the origin. The value in question will be 0 at that moment.

Sample Input 2

5
-7 -10 U
7 -6 U
-8 7 D
-3 3 D
0 -6 R

Sample Output 2

97.5

The answer may not be an integer.

Sample Input 3

20
6 -10 R
-4 -9 U
9 6 D
-3 -2 R
0 7 D
4 5 D
10 -10 U
-1 -8 U
10 -6 D
8 -5 U
6 4 D
0 3 D
7 9 R
9 -4 R
3 10 D
1 9 U
1 -6 U
9 -8 R
6 7 D
7 -3 D

Sample Output 3

273