Problem Statement

You are given a string S. Here, the first character of S is an uppercase English letter, and the second and subsequent characters are lowercase English letters.

Print the string formed by concatenating the first character of S and UPC in this order.

Constraints

• S is a string of length between 1 and 100, inclusive.
• The first character of S is an uppercase English letter.
• The second and subsequent characters of S are lowercase English letters.

Sample Input 1

Kyoto

Sample Output 1

KUPC

The first character of Kyoto is K, so concatenate K and UPC, and print KUPC.

Sample Input 2

Tohoku

Sample Output 2

TUPC

Problem Statement

You are given a string S consisting of digits.

Remove all characters from S except for 2, and then concatenate the remaining characters in their original order to form a new string.

Constraints

• S is a string consisting of digits with length between 1 and 100, inclusive.
• S contains at least one 2.

Sample Input 1

20250222

Sample Output 1

22222

By removing 0, 5, and 0 from 20250222 and then concatenating the remaining characters in their original order, the string 22222 is obtained.

Sample Input 2

2

Sample Output 2

2

Sample Input 3

22222000111222222

Sample Output 3

22222222222

Problem Statement

Takahashi is at the origin of a number line. He wants to reach a goal at coordinate X.

There is a wall at coordinate Y, which Takahashi cannot go beyond at first.
However, after picking up a hammer at coordinate Z, he can destroy that wall and pass through.

Determine whether Takahashi can reach the goal. If he can, find the minimum total distance he needs to travel to do so.

Constraints

• -1000 \leq X,Y,Z \leq 1000
• X, Y, and Z are distinct, and none of them is 0.
• All values in the input are integers.

Sample Input 1

10 -10 1

Sample Output 1

10

Takahashi can go straight to the goal.

Sample Input 2

20 10 -10

Sample Output 2

40

The goal is beyond the wall. He can get there by first picking up the hammer and then destroying the wall.

Sample Input 3

100 1 1000

Sample Output 3

-1

Problem Statement

You are given an integer N.
Print an approximation of N according to the following instructions.

• If N is less than or equal to 10^3-1, print N as it is.
• If N is between 10^3 and 10^4-1, inclusive, truncate the ones digit of N and print the result.
• If N is between 10^4 and 10^5-1, inclusive, truncate the tens digit and all digits below it of N and print the result.
• If N is between 10^5 and 10^6-1, inclusive, truncate the hundreds digit and all digits below it of N and print the result.
• If N is between 10^6 and 10^7-1, inclusive, truncate the thousands digit and all digits below it of N and print the result.
• If N is between 10^7 and 10^8-1, inclusive, truncate the ten-thousands digit and all digits below it of N and print the result.
• If N is between 10^8 and 10^9-1, inclusive, truncate the hundred-thousands digit and all digits below it of N and print the result.

Constraints

• N is an integer between 0 and 10^9-1, inclusive.

Sample Input 1

20230603

Sample Output 1

20200000

20230603 is between 10^7 and 10^8-1 (inclusive).
Therefore, truncate the ten-thousands digit and all digits below it, and print 20200000.

Sample Input 2

0

Sample Output 2

0

Sample Input 3

304

Sample Output 3

304

Sample Input 4

500600

Sample Output 4

500000

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

• First, choose one real number x.
• Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le M \le 10^9
• 0 \le A_i \le 10^9

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

4

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

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

Sample Output 2

2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

7

Problem Statement

We have a sequence of length N: A=(a_1,\ldots,a_N). Additionally, you are given an integer K.

You can perform the following operation zero or more times.

• Choose an integer i such that 1 \leq i \leq N-K, then swap the values of a_i and a_{i+K}.

Determine whether it is possible to sort A in ascending order.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N-1
• 1 \leq a_i \leq 10^9
• All values in input are integers.

Sample Input 1

5 2
3 4 1 3 4

Sample Output 1

Yes

The following sequence of operations sorts A in ascending order.

• Choose i=1 to swap the values of a_1 and a_3. A is now (1,4,3,3,4).
• Choose i=2 to swap the values of a_2 and a_4. A is now (1,3,3,4,4).

Sample Input 2

5 3
3 4 1 3 4

Sample Output 2

No

Sample Input 3

7 5
1 2 3 4 5 5 10

Sample Output 3

Yes

No operations may be needed.

Problem Statement

There is a grid of H rows and W columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H of length W. If the j-th character of S_i is #, it indicates that there is a magnet in the cell at the i-th row from the top and j-th column from the left; if it is ., it indicates that the cell is empty.

Takahashi, wearing an iron armor, can move in the grid as follows:

• If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
• Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
  However, he cannot exit the grid.

For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.

Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W consisting of . and #.
• There is at least one cell without a magnet.

Sample Input 1

3 5
.#...
.....
.#..#

Sample Output 1

9

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. If Takahashi starts at (2,3), possible movements include:

• (2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)
• (2,3) \to (2,4) \to (3,4)
• (2,3) \to (2,2)
• (2,3) \to (1,3)
• (2,3) \to (3,3)

Thus, including the cells he passes through, he can reach at least nine cells from (2,3).
Actually, no other cells can be reached, so the degree of freedom for (2,3) is 9.

This is the maximum degree of freedom among all cells without magnets, so print 9.

Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are 1.
Therefore, print 1.

Problem Statement

You are given a simple connected undirected graph with N vertices and M edges.
Edge i connects Vertex A_i and Vertex B_i, and has a length of C_i.

Let us delete some number of edges while satisfying the conditions below. Find the maximum number of edges that can be deleted.

• The graph is still connected after the deletion.
• For every pair of vertices (s, t), the distance between s and t remains the same before and after the deletion.

Notes

A simple connected undirected graph is a graph that is simple and connected and has undirected edges.
A graph is simple when it has no self-loops and no multi-edges.
A graph is connected when, for every pair of two vertices s and t, t is reachable from s by traversing edges.
The distance between Vertex s and Vertex t is the length of a shortest path between s and t.

Constraints

• 2 \leq N \leq 300
• N-1 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i \lt B_i \leq N
• 1 \leq C_i \leq 10^9
• (A_i, B_i) \neq (A_j, B_j) if i \neq j.
• The given graph is connected.
• All values in input are integers.

Sample Input 1

3 3
1 2 2
2 3 3
1 3 6

Sample Output 1

1

The distance between each pair of vertices before the deletion is as follows.

• The distance between Vertex 1 and Vertex 2 is 2.
• The distance between Vertex 1 and Vertex 3 is 5.
• The distance between Vertex 2 and Vertex 3 is 3.

Deleting Edge 3 does not affect the distance between any pair of vertices. It is impossible to delete two or more edges while satisfying the condition, so the answer is 1.

Sample Input 2

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

Sample Output 2

0

No edge can be deleted.

Sample Input 3

5 10
1 2 71
1 3 9
1 4 82
1 5 64
2 3 22
2 4 99
2 5 1
3 4 24
3 5 18
4 5 10

Sample Output 3

5

Problem Statement

Takahashi plans to participate in N AtCoder contests.

In the i-th contest (1 \leq i \leq N), if his rating is between L_i and R_i (inclusive), his rating increases by 1.

You are given Q queries in the following format:

• An integer X is given. Assuming that Takahashi's initial rating is X, determine his rating after participating in all N contests.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq L_i \leq R_i \leq 5 \times 10^5 (1 \leq i \leq N)
• 1 \leq Q \leq 3 \times 10^5
• For each query, 1 \leq X \leq 5 \times 10^5.
• All input values are integers.

Sample Input 1

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

Sample Output 1

6
6
8

For the 1st query, the rating changes as follows:

• In the 1st contest, the rating is between 1 and 5, so it increases by 1, becoming 4.
• In the 2nd contest, the rating is not between 1 and 3, so it remains 4.
• In the 3rd contest, the rating is between 3 and 6, so it increases by 1, becoming 5.
• In the 4th contest, the rating is not between 2 and 4, so it remains 5.
• In the 5th contest, the rating is between 4 and 7, so it increases by 1, becoming 6.

For the 2nd query, the rating increases in the 1st, 2nd, 3rd, and 5th contests, ending at 6.

For the 3rd query, the rating increases in the 1st, 3rd, and 5th contests, ending at 8.

Sample Input 2

10
1 1999
1 1999
1200 2399
1 1999
1 1999
1 1999
2000 500000
1 1999
1 1999
1600 2799
7
1
1995
2000
2399
500000
2799
1000

Sample Output 2

8
2002
2003
2402
500001
2800
1007

Sample Input 3

15
260522 414575
436426 479445
148772 190081
190629 433447
47202 203497
394325 407775
304784 463982
302156 468417
131932 235902
78537 395728
223857 330739
286918 329211
39679 238506
63340 186568
160016 361868
10
287940
296263
224593
101449
336991
390310
323355
177068
11431
8580

Sample Output 3

287946
296269
224599
101453
336997
390315
323363
177075
11431
8580