Problem Statement

Takahashi's clock is X minutes ahead of the actual time. Here, X<0 implies it is |X| minutes behind.

When his clock shows twelve o'clock, what is the actual time?

Constraints

• X is an integer between -10 and 10, inclusive.

Sample Input 1

5

Sample Output 1

11:55

Takahashi's clock is five minutes ahead of the actual time. Thus, the actual time is 11:55.

Sample Input 2

0

Sample Output 2

12:00

Takahashi's clock shows the actual time.

Sample Input 3

-3

Sample Output 3

12:03

Takahashi's clock is three minutes behind the actual time.

Problem Statement

You are given a string S consisting of uppercase and lowercase English letters.
Here, S is guaranteed to have at least one uppercase and one lowercase letter.

Print the string obtained by extracting the uppercase characters in S, and the string obtained by extracting the lowercase characters in S, preserving the order.

Constraints

• S is a string of length between 2 and 100, inclusive, consisting of uppercase and lowercase English letters.
• S contains at least one uppercase character, and at least one lowercase character.

Sample Input 1

aFGdbcE

Sample Output 1

FGE
adbc

The uppercase letters extracted from S= aFGdbcE form the string FGE when joined in order, and the lowercase letters form adbc.
Thus, the first line should contain FGE, and the second should contain adbc.

Sample Input 2

zZyZz

Sample Output 2

ZZ
zyz

Problem Statement

There are N cherry blossom trees. Tree i blooms at time S_i, but sheds its blossoms (if any) at time T_i.

It rains each time that is a multiple of K, causing all blossoms blooming at that time to shed. For each i=1,2,\dots,N, find the duration for which tree i blooms.

Constraints

• 1 \leq N \leq 100
• 1 \leq S_i < T_i \leq 10^9
• 2 \leq K \leq 10^9
• S_i is not a multiple of K.
• All input values are integers.

Sample Input 1

3 5
1 3
2 5
4 10

Sample Output 1

2 3 1

• Tree 1: blooms at time 1 and sheds its blossoms at time 3. The answer is 2.
• Tree 2: blooms at time 2 and sheds its blossoms at time 5. The answer is 3.
• Tree 3: blooms at time 4 and sheds its blossoms at time 5 because of the rain. The answer is 1.

Problem Statement

You are given a string S consisting of lowercase English letters.

Find the string obtained by removing the characters that occur multiple times in S and joining the remaining ones in order.

Constraints

• S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Sample Input 1

takahashi

Sample Output 1

tksi

The characters that occur multiple times in S are a and h. By removing a and h from S and joining the remaining characters in order, we obtain tksi.

Sample Input 2

abba

Sample Output 2

The string to print may be empty.

Sample Input 3

atcoder

Sample Output 3

atcoder

Problem Statement

You acquired a malfunctioning computer. This computer is capable of computing addition, but always reports a wrong sum for specific N pairs. Specifically, for all i\ (1\leq i\leq N), it evaluates A_i+B_i and B_i+A_i to C_i. Conversely, it finds correct sums for any other pairs of numbers.

You found a program that computes the sum of several numbers. When M numbers x_1,x_2,\dots and x_M are input to this program, this computer finds their sum by the following procedure.

1. Initialize a variable s with x_1.
2. For each i=2,3,\dots,M in order:
   • evaluate s+x_i, and assign the result to s.
3. Print the final value of s.

Find what will be printed when M numbers X_1,X_2,\dots, and X_M are input to this program.

Constraints

• 1\leq N \leq 2\times 10^5
• 2\leq M \leq 2\times 10^5
• 0\leq A_i,B_i,C_i,X_i \leq 10^9
• A_i \leq B_i
• If i\neq j, then (A_i,B_i)\neq (A_j,B_j).
• A_i+B_i \neq C_i
• All input values are integers.

Sample Input 1

3 4
4 9 0
1 3 2
2 6 5
1 3 4 2

Sample Output 1

5

This computer finds the sum of 1,3,4, and 2 as follows.

1. Initialize a variable s with 1.
2. Evaluate 1+3\ (=A_2+B_2) wrongly to 2\ (=C_2), and assign it to s.
3. Evaluate 2+4 correctly to 6, and assign it to s.
4. Evaluate 6+2\ (=B_3+A_3) wrongly to 5\ (=C_3), and assign it to s.
5. Print the final value of s, that is, 5.

Sample Input 2

1 3
1 1 1
1 2 3

Sample Output 2

6

While this computer always wrongly evaluates 1+1, this is never evaluated when finding the sum of 1,2, and 3, so it prints the correct sum.

Sample Input 3

8 10
5 27 27
8 72 27
2 27 12
3 32 12
57 60 3
35 57 27
12 41 72
12 64 57
57 60 32 64 0 60 32 64 0 60

Sample Output 3

3

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N.

Find the maximum integer that can be obtained by choosing two distinct elements from A and concatenating them as strings.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^8
• All input values are integers.

Sample Input 1

4
2 12 323 50

Sample Output 1

50323

The maximum value can be obtained by concatenating 50 and 323 in this order: 50323.

Sample Input 2

2
100000000 100000000

Sample Output 2

100000000100000000

Two elements are considered distinct if they are chosen from different positions in the sequence A, even if they have the same value.

Sample Input 3

8
3 14 15 9 26 53 5 89

Sample Output 3

8953

Problem Statement

There are N cars on a number line extending left and right. The positive coordinate direction points to the right.

The i-th car, whose ID is i, is currently at coordinate A_i and moving at a speed of B_i in the positive direction. The coordinates of the cars are pairwise distinct.

Car i is considered safe if and only if:

• every car to the right of car i is distant by at least B_i\times K from car i.

Print the IDs of the cars that are not safe in ascending order.

Constraints

• 2\leq N\leq 2\times 10^5
• 1\leq K\leq 10^9
• 1\leq A_i,B_i\leq 10^9
• A_i\neq A_j\ (i\neq j)
• All input values are integers.

Sample Input 1

4 2
1 1
10 5
3 3
7 2

Sample Output 1

2
3 4

Car 1 is distant by at least 1\times 2=2 from every car to its right, so it is safe.

Meanwhile, car 3 is distant from car 4 to its right by 7-3=4, which is less than 3\times 2=6, so car 3 is not safe.

Likewise, car 4 is not safe either.

Note that car IDs should be printed in ascending order.

Sample Input 2

10 2
25 9
22 10
7 5
5 7
27 10
6 7
21 6
2 1
9 3
24 10

Sample Output 2

7
1 2 3 4 6 7 10

Problem Statement

Takahashi is going to stay at a hotel for N days.
The hotel has a cleaning service, which he is planning to use K times, on day D_1, day D_2, \ldots, and day D_K, during his N-day visit.

However, it turned out that the service is available at most M times within any consecutive L days.
More formally, for all integers i with 1\leq i\leq N-L+1, the service is available at most M times from day i through day (i+L-1).

He has decided to cancel some of his plans of using the service on days D_1, D_2, \ldots, and D_K, to meet these conditions. (He may not need to cancel his plan at all.) At least how many days among the K days does he need to cancel his plan of using it to meet the conditions?

Constraints

• 1\leq L \leq N \leq 10^{18}
• 1\leq M \leq K \leq 2\times 10^5
• 1\leq D_1<D_2<\cdots<D_K\leq N
• All input values are integers.

Sample Input 1

10 6 5 2
1 2 3 6 8 10

Sample Output 1

2

The cleaning service is available at most twice within any five consecutive days.
The conditions can be met by canceling his plan of using it on day 2 and 10, and using it on day 1,3,6, and 8.
Canceling it only once never satisfies the conditions regardless of which of the six to choose, so print 2.

Sample Input 2

10 3 3 1
1 5 10

Sample Output 2

0

He does not need to cancel his plan at all.

Sample Input 3

1000000000000000000 2 1000000000000000000 1
1 1000000000000000000

Sample Output 3

1

Problem Statement

Given a length-N integer sequence A=(A_1,A_2,\dots,A_N) and an integer K, find the number of (consecutive) subarrays of A that are permutations of 1,2,\dots,K. In other words, find the number of integers between 1 and N-K+1, inclusive, such that (A_{i},A_{i+1},\dots,A_{i+K-1}) is a permutation of 1,2,\dots,K.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq K
• All input values are integers.

Sample Input 1

5 3
1 2 1 3 2

Sample Output 1

2

Among the length-3 subarrays of A, these two are permutations of 1,2,3: (A_2,A_3,A_4)=(2,1,3),(A_3,A_4,A_5)=(1,3,2).

Sample Input 2

5 3
3 1 1 2 2

Sample Output 2

0

Sample Input 3

4 2
1 2 1 2

Sample Output 3

3

Sample Input 4

1 1
1

Sample Output 4

1

Problem Statement

There is an N\times N grid. The cell in the i-th row (1\leq i\leq N) from the top and j-th column (1\leq j\leq N) from the left is called cell (i,j).

Each cell is either an empty cell or a wall cell. The state of the grid is represented by N strings S _ 1,S _ 2,\ldots, and S _ N: if the j-th character of S _ i is ., then cell (i,j) is an empty cell; if it is #, it is a wall cell. Here, the outermost cells, namely cells (1,j),(i,1),(N,j),(i,N)\ (1\leq i\leq N,1\leq j\leq N), are guaranteed to be wall cells.

Initially located at an empty cell (x,y) facing one of the four directions (up, down, left, and right), Takahashi repeated the following move. During his tour, he visited cell (2,2) at some point (including the initial position):

• If the adjacent cell in his facing direction is an empty cell, then advance to that cell without changing his direction. Otherwise, rotate clockwise by 90 degrees while staying at the same cell.

For example, if he makes the move when he is facing up at cell (3,5), he will advance to cell (2, 5) if cell (2,5) is an empty cell, and turn right if it is a wall cell.

How many cells are there where he can have been initially located?

Constraints

• 3\leq N\leq1000
• N is an integer.
• S _ i is a string of length N consisting of . and # (1\leq i\leq N).
• S _ 1 and S _ N are strings consisting solely of #.
• The 1-st and N-th characters of S _ i both equal # (1\leq i\leq N).
• The 2-nd character of S _ 2 equals ..

Sample Input 1

6
######
#....#
#....#
#.#..#
#...##
######

Sample Output 1

13

The given grid looks like this.

Among the 14 empty cells, if he starts at one of the 13 cells except for cell (4,5), he can always visit cell (2,2) if he initially faces in an appropriate direction.

For example, if he starts at cell (4,4) facing down, he will visit cell (2,2) as follows.

Sample Input 2

4
####
#.##
##.#
####

Sample Output 2

1

Sample Input 3

13
#############
#.....####..#
#....#....#.#
#...#......##
#...#..###.##
#...#.#..#.##
#...#.#..#.##
#...#.#....##
#...#..#.##.#
#....#......#
#.....##.##.#
#...........#
#############

Sample Output 3

85

Problem Statement

You are given length-N integer sequences A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_N),C=(C_1,C_2,\dots,C_N),D=(D_1,D_2,\dots,D_N), and E=(E_1,E_2,\dots,E_N).

For an integer i\ (1\leq i\leq N), let f(i) be the number of indices j\ (1\leq j\leq N) such that \max(A_i, B_j-C_i)=D_j+E_i.

Find f(1),f(2),\dots,f(N).

Constraints

• 1\leq N \leq 2\times 10^5
• -10^9\leq A_i,B_i,C_i,D_i,E_i \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

2 0 1

• For i=1, the indices j that satisfy \max(A_i, B_j-C_i)=D_j+E_i are j=1,3. Indeed, for j=3 we have \max(4, 9-2)=4+3.
• For i=2, no indices j satisfy \max(A_i, B_j-C_i)=D_j+E_i.
• For i=3, the indices j that satisfy \max(A_i, B_j-C_i)=D_j+E_i are j=3.

Therefore, f(1)=2,f(2)=0, and f(3)=1.

Sample Input 2

3
4 6 -10
9 2 6
-5 -5 3
7 0 4
7 7 -1

Sample Output 2

3 3 3

\max(A_i, B_j-C_i)=D_j+E_i holds for all 1\leq i,j\leq 3.

Sample Input 3

8
68 108 176 112 146 156 80 82
-158 -59 72 108 -9 -158 51 95
-69 -192 -177 -61 -38 -157 -112 -83
-60 39 14 97 37 -60 97 97
-29 94 79 15 49 59 66 -15

Sample Output 3

0 1 0 1 3 0 2 0

Problem Statement

There are N cities 1, 2, \ldots, N on a two-dimensional plane. City i is located at coordinates (X_i, Y_i).

Initially, no city has a power plant, and there is no power line between the cities.

You can perform the following operations any number of times:

• Build a power plant at city i for a cost of P_i.
• Build a power line between cities i and j for a cost of \sqrt{(X_i - X_j)^2 + (Y_i - Y_j)^2}, the Euclidean distance between them.

Find the minimum total cost required for all cities to be reachable to a city with a power plant via zero or more power lines.

Constraints

• 1 \leq N \leq 2000
• 0 \leq X_i, Y_i \leq 10^9
• (X_i, Y_i) \neq (X_j, Y_j) (i \neq j)
• 1 \leq P_i \leq 10^9
• All input values are integers.

Sample Input 1

3
0 0
1 0
2 2
1 2 1

Sample Output 1

3.00000000000000000000

By building a power plant at cities 1 and 3, and a power line between cities 1 and 2, the total cost will be 3.

Sample Input 2

4
0 0
1 1
10 10
50 50
10 10 10 10

Sample Output 2

31.41421356237309504833

Sample Input 3

5
0 100000
10000 1000000000
10000 100
1000000000 100000
1000000000 0
400000000 600000000 900000000 200000000 500000000

Sample Output 3

1200200399.25298526883125305176

Problem Statement

You are given an integer set S=\{S_1,S_2,\ldots,S_N\} of size N and a sequence D=(D_1,D_2,\ldots,D_{M-1}) of length (M-1).

Among the length-M sequences A consisting of the elements in S, find the maximum number of integers i between 1 and (M-1), inclusive, such that |A_i-A_{i+1}| = D_i.

Constraints

• 1 \leq N \leq 2000
• 2 \leq M \leq 2000
• 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
• 0 \leq D_i \leq 10^9 (1 \leq i \leq M-1)
• S_i \neq S_j (1 \leq i < j \leq N)
• All input values are integers.

Sample Input 1

5 5
1 2 3 4 5
3 1 4 1

Sample Output 1

4

When A=(5,2,1,5,4), there are four integers i with |A_i-A_{i+1}|=D_i. This count can never be 5 or larger, so the answer is 4.

Sample Input 2

10 7
22 75 26 45 72 81 47 29 97 2
0 30 34 0 18 50

Sample Output 2

5

Problem Statement

You are given an integer sequence A = (A_1, A_2, \ldots, A_N) of length N, and an integer K.

Process the given Q queries in the following format in order.

• Given integers i and x, set A_i to x, and find the maximum sum of the values in a length-K (contiguous) subarray of A.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• For each query, 1 \leq i \leq N
• For each query, 1 \leq x \leq 10^9
• All input values are integers.

Sample Input 1

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

Sample Output 1

12
7
11

Initially, A = (2, 3, 1, 1, 7, 4).

• For the 1-st query, first set A_6 to 2, making A = (2, 3, 1, 1, 7, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 3 + 1 + 1 + 7 = 12.
• For the 2-st query, first set A_5 to 2, making A = (2, 3, 1, 1, 2, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 2 + 3 + 1 + 1 = 7.
• For the 3-st query, first set A_4 to 5, making A = (2, 3, 1, 5, 2, 2). Then, the maximum sum of the elements in a length-4 subarray of A is 3 + 1 + 5 + 2 = 11.

Sample Input 2

7 2
1 7 2 6 3 5 4
5
7 7
1 100
3 1000
5 10000
2 100000

Sample Output 2

12
107
1007
10006
101000

Problem Statement

Consider placing N points \{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\} on a two-dimensional plane subject to the following conditions:

• For all i=1,2,\dots,N, the Manhattan distance between point (x_i,y_i) and (a_i,b_i) is at most d_i.
• For all j=1,2,\dots,M, the Manhattan distance between point (x_{u_j},y_{u_j}) and (x_{v_j},y_{v_j}) is at most e_j.

Here, the Manhattan distance between two points (p_1,q_1) and (p_2,q_2) is defined as |p_1-p_2|+|q_1-q_2|. Note that the coordinates x_i and y_i are not necessarily integers.

Determine if there exists such a placement of N (not necessarily distinct) points. If it exists, find the maximum possible Manhattan distance between the origin (0,0) and point (x_P,y_P). Under the constraints of this problem, the answer can be proven an integer, so print the answer as an integer.

Constraints

• 1 \leq N \leq 2000
• 0 \leq M \leq \min\{2000, N(N-1)/2\}
• 1 \leq P \leq N
• |a_i|,|b_i|\leq 10^8
• 0 \leq d_i\leq 10^8
• 1 \leq u_j < v_j\leq N
• If j\neq k, then (u_j,v_j) \neq (u_k,v_k).
• 0 \leq e_j\leq 10^8
• All input values are integers.

Sample Input 1

1 0 1
1 1 2

Sample Output 1

4

The setting of this sample is shown in the figure below. The circle denotes point (a_1,b_1), and the square denotes the region that satisfies |x-a_1|+|y-b_1|\leq d_1. For example, by placing (x_1,y_1) at (2,2) (the star in the figure), the Manhattan distance between (x_1,y_1) and the origin can be 4.

Alternatively, placing (x_1,y_1) at (1.5, 2.5) also satisfies the conditions, resulting in the Manhattan distance of 4.

Sample Input 2

2 1 2
1 1 2
-2 2 3
1 2 1

Sample Output 2

3

For example, by placing (x_1,y_1) at (0,2) and (x_2,y_2) at (-1,2), all the conditions can be satisfied. In this case, the Manhattan distance between (x_2,y_2) and the origin is 3, which is maximum possible.

Sample Input 3

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

Sample Output 3

-1

No matter where you place (x_1,y_1) and (x_2,y_2) in the blue and orange regions, respectively, the Manhattan distance between them can never be 1.