Problem Statement

You are given an integer N. If N is between -2^{31} and 2^{31}-1 (inclusive), print Yes; otherwise, print No.

Constraints

• -2^{63} \leq N < 2^{63}
• N is an integer.

Sample Input 1

10

Sample Output 1

Yes

10 is between -2^{31} and 2^{31}-1, so Yes should be printed.

Sample Input 2

-9876543210

Sample Output 2

No

-9876543210 is less than -2^{31}, so No should be printed.

Sample Input 3

483597848400000

Sample Output 3

No

483597848400000 is greater than 2^{31}-1, so No should be printed.

Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

Takahashi is trying to create a game inspired by baseball, but he is having difficulty writing the code.
Write a program for Takahashi that solves the following problem.

There are 4 squares called Square 0, Square 1, Square 2, and Square 3. Initially, all squares are empty.
There is also an integer P; initially, P = 0.
Given a sequence of positive integers A = (A_1, A_2, \dots, A_N), perform the following operations for i = 1, 2, \dots, N in this order:

1. Put a piece on Square 0.
2. Advance every piece on the squares A_i squares ahead. In other words, if Square x has a piece, move the piece to Square (x + A_i).
   If, however, the destination square does not exist (i.e. x + A_i is greater than or equal to 4) for a piece, remove it. Add to P the number of pieces that have been removed.

Print the value of P after all the operations have been performed.

Constraints

• 1 \leq N \leq 100
• 1 \leq A_i \leq 4
• All values in input are integers.

Sample Input 1

4
1 1 3 2

Sample Output 1

3

The operations are described below. After all the operations have been performed, P equals 3.

• The operations for i=1:
  1. Put a piece on Square 0. Now, Square 0 has a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Square 1 has a piece.
• The operations for i=2:
  1. Put a piece on Square 0. Now, Squares 0 and 1 have a piece.
  2. Advance every piece on the squares 1 square ahead. After these moves, Squares 1 and 2 have a piece.
• The operations for i=3:
  1. Put a piece on Square 0. Now, Squares 0, 1, and 2 have a piece.
  2. Advance every piece on the squares 3 squares ahead.
     Here, for the pieces on Squares 1 and 2, the destination squares do not exist (since 1+3=4 and 2+3=5), so remove these pieces and add 2 to P. P now equals 2. After these moves, Square 3 has a piece.
• The operations for i=4:
  1. Put a piece on Square 0. Now, Squares 0 and 3 have a piece.
  2. Advance every piece on the squares 2 squares ahead.
     Here, for the piece on Square 3, the destination square does not exist (since 3+2=5), so remove this piece and add 1 to P. P now equals 3.
     After these moves, Square 2 has a piece.

Sample Input 2

3
1 1 1

Sample Output 2

0

The value of P may not be updated by the operations.

Sample Input 3

10
2 2 4 1 1 1 4 2 2 1

Sample Output 3

8

Problem Statement

You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.

Constraints

• All inputs are integers.
• 1 \le K < N \le 2 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

5 2
3 1 5 4 9

Sample Output 1

2

Consider removing exactly two elements from A=(3,1,5,4,9).

• For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
  • In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.

Sample Input 2

6 5
1 1 1 1 1 1

Sample Output 2

0

Sample Input 3

8 3
31 43 26 6 18 36 22 13

Sample Output 3

18

Problem Statement

There are N + 1 rooms arranged in a line, numbered 0, 1, \ldots, N in order.

Between the rooms, there are N doors numbered 1, 2, \ldots, N. Door i is between rooms i - 1 and i.

For each door, a value L_i representing the lock state is given. When L_i = 0, door i is unlocked, and when L_i = 1, door i is locked.

Takahashi is initially in room R, and can move between rooms i - 1 and i only when door i is unlocked. Also, he can perform a switching operation on door i only when he is in room i - 1 or room i. When a switching operation is performed on door i, if the door is unlocked, it becomes locked, and if it is locked, it becomes unlocked.

Find the minimum number of switching operations needed to make all doors locked.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq R \leq N
• L_i \in \lbrace 0, 1 \rbrace
• All input values are integers.

Sample Input 1

6 3
1 0 0 1 0 0

Sample Output 1

6

Takahashi can make all doors locked with six switching operations by acting as follows:

• Move to room 2.
• Perform a switching operation on door 2 to lock door 2.
• Move to room 3.
• Perform a switching operation on door 4 to unlock door 4.
• Perform a switching operation on door 3 to lock door 3.
• Move to room 4.
• Perform a switching operation on door 4 to lock door 4.
• Move to room 5.
• Perform a switching operation on door 5 to lock door 5.
• Perform a switching operation on door 6 to lock door 6.

Sample Input 2

2 1
0 0

Sample Output 2

2

Sample Input 3

8 2
0 1 0 0 1 0 1 1

Sample Output 3

8

Problem Statement

There is a grid of H rows and W columns, each cell having a side length of 1, and we have N tiles.
The i-th tile (1\leq i\leq N) is a rectangle of size A_i\times B_i.
Determine whether it is possible to place the tiles on the grid so that all of the following conditions are satisfied:

• Every cell is covered by exactly one tile.
• It is fine to have unused tiles.
• The tiles may be rotated or flipped when placed. However, each tile must be aligned with the edges of the cells without extending outside the grid.

Constraints

• 1\leq N\leq 7
• 1 \leq H,W \leq 10
• 1\leq A_i,B_i\leq 10
• All input values are integers.

Sample Input 1

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

Sample Output 1

Yes

Placing the 2-nd, 4-th, and 5-th tiles as shown below covers every cell of the grid by exactly one tile.

Hence, print Yes.

Sample Input 2

1 1 2
2 3

Sample Output 2

No

It is impossible to place the tile without letting it extend outside the grid.
Hence, print No.

Sample Input 3

1 2 2
1 1

Sample Output 3

No

It is impossible to cover all cells with the tile.
Hence, print No.

Sample Input 4

5 3 3
1 1
2 2
2 2
2 2
2 2

Sample Output 4

No

Note that each cell must be covered by exactly one tile.

Problem Statement

You are given two strings: S, which consists of uppercase English letters and has length N, and T, which also consists of uppercase English letters and has length M\ (\leq N).

There is a string X of length N consisting only of the character #. Determine whether it is possible to make X match S by performing the following operation any number of times:

• Choose M consecutive characters in X and replace them with T.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq M \leq \min(N, 5)
• S is a string consisting of uppercase English letters with length N.
• T is a string consisting of uppercase English letters with length M.

Sample Input 1

7 3
ABCBABC
ABC

Sample Output 1

Yes

Below, let X[l:r] denote the part from the l-th through the r-th character of X.

You can make X match S by operating as follows.

1. Replace X[3:5] with T. X becomes ##ABC##.
2. Replace X[1:3] with T. X becomes ABCBC##.
3. Replace X[5:7] with T. X becomes ABCBABC.

Sample Input 2

7 3
ABBCABC
ABC

Sample Output 2

No

No matter how you operate, it is impossible to make X match S.

Sample Input 3

12 2
XYXXYXXYYYXY
XY

Sample Output 3

Yes

Problem Statement

There are N buildings, building 1, building 2, \ldots, building N, arranged in this order in a straight line from west to east. Building 1 is the westernmost, and building N is the easternmost. The height of building i\ (1\leq i\leq N) is H_i.

For a pair of integers (i,j)\ (1\leq i\lt j\leq N), building j can be seen from building i if the following condition is satisfied.

• There is no building taller than building j between buildings i and j. In other words, there is no integer k\ (i\lt k\lt j) such that H_k > H_j.

You are given Q queries. In the i-th query, given a pair of integers (l_i,r_i)\ (l_i\lt r_i), find the number of buildings to the east of building r_i (that is, buildings r_i + 1, r_i + 2, \ldots, N) that can be seen from both buildings l_i and r_i.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq H_i \leq N
• H_i\neq H_j\ (i\neq j)
• 1 \leq l_i < r_i \leq N
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
0
1

• For the first query, among the buildings to the east of building 2, buildings 3 and 5 can be seen from both buildings 1 and 2, so the answer is 2.
• For the second query, there are no buildings to the east of building 5.
• For the third query, among the buildings to the east of building 4, building 5 can be seen from both buildings 1 and 4, so the answer is 1.

Sample Input 2

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

Sample Output 2

1
3
1
2
1
0
1
1
0
0