Problem Statement

There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.

For each j=1,2,\ldots,Q, answer the following question.

• How many of the N students have a height of at least x_j?

Constraints

• 1 \leq N,Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq x_j \leq 10^9
• All values in input are integers.

Sample Input 1

3 1
100 160 130
120

Sample Output 1

2

The students with a height of at least 120 are the 2-nd and 3-rd ones.

Sample Input 2

5 5
1 2 3 4 5
6
5
4
3
2

Sample Output 2

0
1
2
3
4

Sample Input 3

5 5
804289384 846930887 681692778 714636916 957747794
424238336
719885387
649760493
596516650
189641422

Sample Output 3

5
3
5
5
5

Problem Statement

Your refrigerator has N kinds of ingredients. Let us call them ingredient 1, \dots, ingredient N. You have Q_i grams of ingredient i.

You can make two types of dishes. To make one serving of dish A, you need A_i grams of each ingredient i (1 \leq i \leq N). To make one serving of dish B, you need B_i grams of each ingredient i. You can only make an integer number of servings of each type of dish.

Using only the ingredients in the refrigerator, what is the maximum total number of servings of dishes you can make?

Constraints

• 1 \leq N \leq 10
• 1 \leq Q_i \leq 10^6
• 0 \leq A_i \leq 10^6
• There is an i such that A_i \geq 1.
• 0 \leq B_i \leq 10^6
• There is an i such that B_i \geq 1.
• All input values are integers.

Sample Input 1

2
800 300
100 100
200 10

Sample Output 1

5

This refrigerator has 800 grams of ingredient 1 and 300 grams of ingredient 2.

You can make one serving of dish A with 100 grams of ingredient 1 and 100 grams of ingredient 2, and one serving of dish B with 200 grams of ingredient 1 and 10 grams of ingredient 2.

To make two servings of dish A and three servings of dish B, you need 100 \times 2 + 200 \times 3 = 800 grams of ingredient 1, and 100 \times 2 + 10 \times 3 = 230 grams of ingredient 2, neither of which exceeds the amount available in the refrigerator. In this way, you can make a total of five servings of dishes, but there is no way to make six, so the answer is 5.

Sample Input 2

2
800 300
100 0
0 10

Sample Output 2

38

You can make 8 servings of dish A with 800 grams of ingredient 1, and 30 servings of dish B with 300 grams of ingredient 2, for a total of 38 servings.

Sample Input 3

2
800 300
801 300
800 301

Sample Output 3

0

You cannot make any dishes.

Sample Input 4

10
1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000 1000000
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

Sample Output 4

222222

Problem Statement

We have an infinite hexagonal grid shown below. Initially, all squares are white.

A hexagonal cell is represented as (i,j) with two integers i and j.
Cell (i,j) is adjacent to the following six cells:

• (i-1,j-1)
• (i-1,j)
• (i,j-1)
• (i,j+1)
• (i+1,j)
• (i+1,j+1)

Takahashi has painted N cells (X_1,Y_1),(X_2,Y_2),\dots,(X_N,Y_N) black.
Find the number of connected components formed by the black cells.
Two black cells belong to the same connected component when one can travel between those two black cells by repeatedly moving to an adjacent black cell.

Constraints

• All values in the input are integers.
• 1 \le N \le 1000
• |X_i|,|Y_i| \le 1000
• The pairs (X_i,Y_i) are distinct.

Sample Input 1

6
-1 -1
0 1
0 2
1 0
1 2
2 0

Sample Output 1

3

After Takahashi paints cells black, the grid looks as shown below.

The black squares form the following three connected components:

• (-1,-1)
• (1,0),(2,0)
• (0,1),(0,2),(1,2)

Sample Input 2

4
5 0
4 1
-3 -4
-2 -5

Sample Output 2

4

Sample Input 3

5
2 1
2 -1
1 0
3 1
1 -1

Sample Output 3

1

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

The grid has a rook, initially on (x_1, y_1). Takahashi will do the following operation K times.

• Move the rook to a square that shares the row or column with the square currently occupied by the rook. Here, it must move to a square different from the current one.

How many ways are there to do the K operations so that the rook will be on (x_2, y_2) in the end? Since the answer can be enormous, find it modulo 998244353.

Constraints

• 2 \leq H, W \leq 10^9
• 1 \leq K \leq 10^6
• 1 \leq x_1, x_2 \leq H
• 1 \leq y_1, y_2 \leq W

Sample Input 1

2 2 2
1 2 2 1

Sample Output 1

2

We have the following two ways.

• First, move the rook from (1, 2) to (1, 1). Second, move it from (1, 1) to (2, 1).
• First, move the rook from (1, 2) to (2, 2). Second, move it from (2, 2) to (2, 1).

Sample Input 2

1000000000 1000000000 1000000
1000000000 1000000000 1000000000 1000000000

Sample Output 2

24922282

Be sure to find the count modulo 998244353.

Sample Input 3

3 3 3
1 3 3 3

Sample Output 3

9

Problem Statement

There is an octopus-shaped robot and N treasures on a number line. The i-th treasure (1\leq i\leq N) is located at coordinate X_i.
The robot has one head and N legs, and the i-th leg (1\leq i\leq N) has a length of L_i.

Find the number of integers k such that the robot can grab all N treasures as follows.

• Place the head at coordinate k.
• Repeat the following for i=1,2,\ldots,N in this order: if there is a treasure that has not been grabbed yet within a distance of L_i from the head, that is, at a coordinate x satisfying k-L_i\leq x\leq k+L_i, choose one such treasure and grab it.

Constraints

• 1 \leq N\leq 200
• -10^{18} \leq X_1<X_2<\cdots<X_N\leq 10^{18}
• 1\leq L_1\leq L_2\leq\cdots\leq L_N\leq 10^{18}
• All input values are integers.

Sample Input 1

3
-6 0 7
3 5 10

Sample Output 1

6

k=-3,-2,-1,2,3,4 satisfy the condition. For example, when k=-3, the robot can grab all three treasures as follows.

• The first leg can grab treasures at coordinates x satisfying -6\leq x\leq 0. Among them, grab the first treasure at coordinate -6.
• The second leg can grab treasures at coordinates x satisfying -8\leq x\leq 2. Among them, grab the second treasure at coordinate 0.
• The third leg can grab treasures at coordinates x satisfying -13\leq x\leq 7. Among them, grab the third treasure at coordinate 7.

Sample Input 2

1
0
1000000000000000000

Sample Output 2

2000000000000000001

All integers k from -10^{18} to 10^{18} satisfy the condition.

Sample Input 3

2
-100 100
1 1

Sample Output 3

0

No k satisfies the conditions.