Problem Statement

You are given an integer sequence A of length N and integers K and X.
Print the integer sequence B obtained by inserting the integer X immediately after the K-th element of the sequence A.

Constraints

• All input values are integers.
• 1 \le K \le N \le 100
• 1 \le A_i, X \le 100

Sample Input 1

4 3 7
2 3 5 11

Sample Output 1

2 3 5 7 11

For K=3, X=7, and A=(2,3,5,11), we get B=(2,3,5,7,11).

Sample Input 2

1 1 100
100

Sample Output 2

100 100

Sample Input 3

8 8 3
9 9 8 2 4 4 3 5

Sample Output 3

9 9 8 2 4 4 3 5 3

Problem Statement

You are trying to implement collision detection in a 3D game.

In a 3-dimensional space, let C(a,b,c,d,e,f) denote the cuboid with a diagonal connecting (a,b,c) and (d,e,f), and with all faces parallel to the xy-plane, yz-plane, or zx-plane.
(This definition uniquely determines C(a,b,c,d,e,f).)

Given two cuboids C(a,b,c,d,e,f) and C(g,h,i,j,k,l), determine whether their intersection has a positive volume.

Constraints

• 0 \leq a < d \leq 1000
• 0 \leq b < e \leq 1000
• 0 \leq c < f \leq 1000
• 0 \leq g < j \leq 1000
• 0 \leq h < k \leq 1000
• 0 \leq i < l \leq 1000
• All input values are integers.

Sample Input 1

0 0 0 4 5 6
2 3 4 5 6 7

Sample Output 1

Yes

The positional relationship of the two cuboids is shown in the figure below, and their intersection has a volume of 8.

Sample Input 2

0 0 0 2 2 2
0 0 2 2 2 4

Sample Output 2

No

The two cuboids touch at a face, where the volume of the intersection is 0.

Sample Input 3

0 0 0 1000 1000 1000
10 10 10 100 100 100

Sample Output 3

Yes

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+2 cells arranged in a row. Let cell i denote the i-th cell from the left.

There is one stone placed in each of the cells from cell 1 to cell N.
For each 1 \leq i \leq N, the stone in cell i is white if S_i is W, and black if S_i is B.
Cells N+1 and N+2 are empty.

You can perform the following operation any number of times (possibly zero):

• Choose a pair of adjacent cells that both contain stones, and move these two stones to the empty two cells while preserving their order.
  More precisely, choose an integer x such that 1 \leq x \leq N+1 and both cells x and x+1 contain stones. Let k and k+1 be the empty two cells. Move the stones from cells x and x+1 to cells k and k+1, respectively.

Determine if it is possible to achieve the following state, and if so, find the minimum number of operations required:

• Each of the cells from cell 1 to cell N contains one stone, and for each 1 \leq i \leq N, the stone in cell i is white if T_i is W, and black if T_i is B.

Constraints

• 2 \leq N \leq 14
• N is an integer.
• Each of S and T is a string of length N consisting of B and W.

Sample Input 1

6
BWBWBW
WWWBBB

Sample Output 1

4

Using . to represent an empty cell, the desired state can be achieved in four operations as follows, which is the minimum:

• BWBWBW..
• BW..BWBW
• BWWBB..W
• ..WBBBWW
• WWWBBB..

Sample Input 2

6
BBBBBB
WWWWWW

Sample Output 2

-1

Sample Input 3

14
BBBWBWWWBBWWBW
WBWWBBWWWBWBBB

Sample Output 3

7

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N and N-1 roads numbered 1 to N-1.

Road i connects cities A_i and B_i bidirectionally, and its length is C_i. Any pair of cities can be reached from each other by traveling through some roads.

Find the minimum travel distance required to start from a city and visit all cities at least once using the roads.

Constraints

• 2 \leq N \leq 2\times 10^5
• 1 \leq A_i, B_i \leq N
• 1 \leq C_i \leq 10^9
• All input values are integers.
• Any pair of cities can be reached from each other by traveling through some roads.

Sample Input 1

4
1 2 2
1 3 3
1 4 4

Sample Output 1

11

If you travel as 4 \to 1 \to 2 \to 1 \to 3, the total travel distance is 11, which is the minimum.

Note that you do not need to return to the starting city.

Sample Input 2

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

Sample Output 2

9000000000

Beware overflow.

Problem Statement

How many integers x between 1 and N, inclusive, can be expressed as x = a^b using some positive integer a and a positive integer b not less than 2?

Constraints

• All input values are integers.
• 1 \le N \le 10^{18}

Sample Input 1

99

Sample Output 1

12

The integers that satisfy the conditions in the problem statement are 1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81: there are 12.

Sample Input 2

1000000000000000000

Sample Output 2

1001003332

Problem Statement

There are N stones placed on a 2-dimensional plane. The i-th stone is located at coordinates (X_i, Y_i). All stones are located at lattice points in the first quadrant (including the axes).

Count the number of lattice points (x, y) where no stone is placed and it is impossible to reach (-1, -1) from (x, y) by repeatedly moving up, down, left, or right by 1 without passing through coordinates where a stone is placed.

More precisely, count the number of lattice points (x, y) where no stone is placed, and there does not exist a finite sequence of integer pairs (x_0, y_0), \ldots, (x_k, y_k) that satisfies all of the following four conditions:

• (x_0, y_0) = (x, y).
• (x_k, y_k) = (-1, -1).
• |x_i - x_{i+1}| + |y_i - y_{i+1}| = 1 for all 0 \leq i < k.
• There is no stone at (x_i, y_i) for all 0 \leq i \leq k.

Constraints

• 0 \leq N \leq 2 \times 10^5
• 0 \leq X_i, Y_i \leq 2 \times 10^5
• The pairs (X_i, Y_i) are distinct.
• All input values are integers.

Sample Input 1

5
1 0
0 1
2 3
1 2
2 1

Sample Output 1

1

It is impossible to reach (-1, -1) from (1, 1).

Sample Input 2

0

Sample Output 2

0

There may be cases where no stones are placed.

Sample Input 3

22
0 1
0 2
0 3
1 0
1 4
2 0
2 2
2 4
3 0
3 1
3 2
3 4
5 1
5 2
5 3
6 0
6 4
7 0
7 4
8 1
8 2
8 3

Sample Output 3

6

There are six such points: (6, 1), (6, 2), (6, 3), (7, 1), (7, 2), (7, 3).