Problem Statement

N people labeled 1,2,\dots,N took an exam, and person i scored A_i points.
Only those who scored at least L points pass this exam.
Determine how many people out of the N have passed the exam.

Constraints

• All input values are integers.
• 1 \le N \le 100
• 1 \le L \le 1000
• 0 \le A_i \le 1000

Sample Input 1

5 60
60 20 100 90 40

Sample Output 1

3

Five people took the exam. You need to score at least 60 points to pass.

• Person 1 scored 60 points, so they passed.
• Person 2 scored 20 points, so they did not pass.
• Person 3 scored 100 points, so they passed.
• Person 4 scored 90 points, so they passed.
• Person 5 scored 40 points, so they did not pass.

From the above, we can see that three people have passed.

Sample Input 2

4 80
79 78 77 76

Sample Output 2

0

There may be cases no one has passed.

Sample Input 3

10 50
31 41 59 26 53 58 97 93 23 84

Sample Output 3

6

Problem Statement

There are N buildings aligned in a row. The i-th building from the left has a height of H_i.

Determine if there is a building taller than the first one from the left. If such a building exists, find the position of the leftmost such building from the left.

Constraints

• 1 \leq N \leq 100
• 1 \leq H_i \leq 100
• All input values are integers.

Sample Input 1

4
3 2 5 2

Sample Output 1

3

The building taller than the first one from the left is the third one from the left.

Sample Input 2

3
4 3 2

Sample Output 2

-1

No building is taller than the first one from the left.

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

6

The buildings taller than the first one from the left are the sixth and seventh ones. Among them, the leftmost is the sixth one.

Problem Statement

There is a grid with H rows and W columns. Takahashi is going to paint each cell of this grid black or white.

He paints all cells on the border of the grid black, and all other cells white. Output the grid after he has painted it.

Constraints

• 3\le H\le10
• 3\le W\le10
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

#####
#...#
#...#
#####

For example, cell (1,1) is on the border. This is because there are only two cells edge-adjacent to cell (1,1): cells (1,2) and (2,1). Thus, cell (1,1) is painted black, so the first character of the first line should be #.

Conversely, for example, cell (3,4) is not on the border. This is because there are four cells edge-adjacent to cell (3,4): cells (2,4), (3,3), (3,5), and (4,4). Thus, cell (3,4) is painted white, so the fourth character of the third line should be ..

Sample Input 2

5 6

Sample Output 2

######
#....#
#....#
#....#
######

Problem Statement

A string S is said to be a substring of a string T when there is a pair of integers i and j (1 \leq i \leq j \leq |T|) that satisfy the following condition.

• The extraction of the i-th through j-th characters of T without changing the order equals S.

Let T be the concatenation of 10^5 copies of oxx.
Given a string S, print Yes if S is a substring of T, and No otherwise.

Constraints

• S is a string consisting of o and x.
• The length of S is between 1 and 10 (inclusive).

Sample Input 1

xoxxoxxo

Sample Output 1

Yes

T begins like this: oxxoxxoxxoxx... Since the extraction of 3-rd through 10-th characters of T equals S, S is a substring of T, so Yes should be printed.

Sample Input 2

xxoxxoxo

Sample Output 2

No

Since there is no way to extract from T a string that equals S, S is not a substring of T, so No should be printed.

Sample Input 3

ox

Sample Output 3

Yes

Problem Statement

There is a grid with 10^9 rows and 10^9 columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

There are N people on the grid. Initially, the i-th person is at square (R_i, C_i).

The time starts at 0. Each person can do the following move at times 1, 2, 3, 4, \ldots.

• Stay at the current position, or move to an 8-adjacent square. It is forbidden to leave the grid. Formally, let square (i, j) be the current square, and move to one of the squares (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) that exists. Assume that the move takes no time.

Find the minimum possible time when the N people are at the same square.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_i, C_i \leq 10^9
• All input values are integers.

Sample Input 1

3
2 3
5 1
8 1

Sample Output 1

3

All people will be at square (5, 4) at time 3 if each person moves as follows.

• At time 1, the 1st person moves to square (3, 4), the 2nd person moves to square (6, 2), and the 3rd person moves to square (7, 2).

• At time 2, the 1st person moves to square (4, 4), the 2nd person moves to square (5, 3), and the 3rd person moves to square (6, 3).

• At time 3, the 1st person moves to square (5, 4), the 2nd person moves to square (5, 4), and the 3rd person moves to square (5, 4).

Sample Input 2

5
6 7
6 7
6 7
6 7
6 7

Sample Output 2

0

All people start at the same square.

Sample Input 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

Sample Output 3

44

Problem Statement

There are N people numbered 1, 2, \ldots, N on a two-dimensional plane, and person i is at the point represented by the coordinates (X_i,Y_i).

Person 1 has been infected with a virus. The virus spreads to people within a distance of D from an infected person.

Here, the distance is defined as the Euclidean distance, that is, for two points (a_1, a_2) and (b_1, b_2), the distance between these two points is \sqrt {(a_1-b_1)^2 + (a_2-b_2)^2}.

After a sufficient amount of time has passed, that is, when all people within a distance of D from person i are infected with the virus if person i is infected, determine whether person i is infected with the virus for each i.

Constraints

• 1 \leq N, D \leq 2000
• -1000 \leq X_i, Y_i \leq 1000
• (X_i, Y_i) \neq (X_j, Y_j) if i \neq j.
• All input values are integers.

Sample Input 1

4 5
2 -1
3 1
8 8
0 5

Sample Output 1

Yes
Yes
No
Yes

The distance between person 1 and person 2 is \sqrt 5, so person 2 gets infected with the virus.
Also, the distance between person 2 and person 4 is 5, so person 4 gets infected with the virus.
Person 3 has no one within a distance of 5, so they will not be infected with the virus.

Sample Input 2

3 1
0 0
-1000 -1000
1000 1000

Sample Output 2

Yes
No
No

Sample Input 3

9 4
3 2
6 -1
1 6
6 5
-2 -3
5 3
2 -3
2 1
2 6

Sample Output 3

Yes
No
No
Yes
Yes
Yes
Yes
Yes
No

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

• 1 \le l \le r \le |S|. (|S| is the length of S.)
• The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

• S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9

Problem Statement

Solve the following problem for T test cases.

There are 10^9 boxes numbered 1,2,\dots,10^9 and N balls numbered 1,2,\dots,N.
Each box can contain at most one ball.
Determine whether it is possible to put all N balls in the boxes so that the following condition will be satisfied.

• For each integer i from 1 through N, the ball numbered i is in a box numbered between L_i and R_i (inclusive).

Constraints

• 1 \le T \le 2 \times 10^5
• 1 \le N \le 2 \times 10^5
• 1 \le L_i \le R_i \le 10^9
• The sum of N across the test cases in one input is at most 2 \times 10^5.

Sample Input 1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Sample Output 1

Yes
No

This input contains two test cases.

• In the 1-st test case, the following way to put the three balls would satisfy the condition, so we should print Yes.

  • Put Ball 1 in Box 1.
  • Put Ball 2 in Box 2.
  • Put Ball 3 in Box 3.

• In the 2-nd test case, there is no way to put the five balls to satisfy the condition, so we should print No.

Problem Statement

You are given an integer array A=(a_1,a_2,\ldots,a_N).
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of A, and delete it from the array.

For each x=1,2,\ldots,M, solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of A equal x. If it is impossible to make the sum of elements of A equal x, print -1 instead.

Note that the sum of elements of an empty array is 0.

Constraints

• 1 \leq N,M \leq 3000
• 1 \leq a_i \leq 3000
• All values in the input are integers.

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For x=1, delete a_2,a_3,a_4, and the sum of elements of A becomes x.
• For x=2, delete a_3,a_4, then delete a_1, and the sum of elements of A becomes x.
• For x=3, delete a_3,a_4, and the sum of elements of A becomes x.
• For x=4, delete a_1,a_2,a_3, and the sum of elements of A becomes x.
• For x=5, delete a_2,a_3, and the sum of elements of A becomes x.

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1