Problem Statement

A positive integer x is called a 321-like Number when it satisfies the following condition.

• The digits of x are strictly decreasing from top to bottom.
• In other words, if x has d digits, it satisfies the following for every integer i such that 1 \le i < d:
  • (the i-th digit from the top of x) > (the (i+1)-th digit from the top of x).

Note that all one-digit positive integers are 321-like Numbers.

For example, 321, 96410, and 1 are 321-like Numbers, but 123, 2109, and 86411 are not.

You are given N as input. Print Yes if N is a 321-like Number, and No otherwise.

Constraints

• All input values are integers.
• 1 \le N \le 99999

Sample Input 1

321

Sample Output 1

Yes

For N=321, the following holds:

• The first digit from the top, 3, is greater than the second digit from the top, 2.
• The second digit from the top, 2, is greater than the third digit from the top, 1.

Thus, 321 is a 321-like Number.

Sample Input 2

123

Sample Output 2

No

For N=123, the following holds:

• The first digit from the top, 1, is not greater than the second digit from the top, 2.

Thus, 123 is not a 321-like Number.

Sample Input 3

1

Sample Output 3

Yes

Sample Input 4

86411

Sample Output 4

No

Problem Statement

You are given an integer N between 0 and 9999 (inclusive).

Print it as a four-digit string after appending to it the necessary number of leading zeros.

Constraints

• 0 \leq N \leq 9999
• N is an integer.

Sample Input 1

321

Sample Output 1

0321

321 has three digits, so we need to add one leading zero to it to make it have four digits.

Sample Input 2

7777

Sample Output 2

7777

Sample Input 3

1

Sample Output 3

0001

Problem Statement

You are given a sequence of M integers A = (A_1, A_2, \dots, A_M).
Each element of A is an integer between 1 and N, inclusive, and all elements are distinct.

List all integers between 1 and N that do not appear in A in ascending order.

Constraints

• All input values are integers.
• 1 \le M \le N \le 1000
• 1 \le A_i \le N
• The elements of A are distinct.

Sample Input 1

10 3
3 9 2

Sample Output 1

7
1 4 5 6 7 8 10

Here, A=(3,9,2).
The integers between 1 and 10 that do not appear in A, listed in ascending order, are 1,4,5,6,7,8,10.

Sample Input 2

6 6
1 3 5 2 4 6

Sample Output 2

0

No integer between 1 and 6 is missing from A.
In this case, print 0 on the first line and leave the second line empty.

Sample Input 3

9 1
9

Sample Output 3

8
1 2 3 4 5 6 7 8

Problem Statement

There are N squares, indexed Square 1, Square 2, …, Square N, arranged in a row from left to right.
Also, there are K pieces. The i-th piece from the left is initially placed on Square A_i.
Now, we will perform Q operations against them. The i-th operation is as follows:

• If the L_i-th piece from the left is on its rightmost square, do nothing.
• Otherwise, move the L_i-th piece from the left one square right if there is no piece on the next square on the right; if there is, do nothing.

Print the index of the square on which the i-th piece from the left is after the Q operations have ended, for each i=1,2,\ldots,K.

Constraints

• 1\leq K\leq N\leq 200
• 1\leq A_1<A_2<\cdots<A_K\leq N
• 1\leq Q\leq 1000
• 1\leq L_i\leq K
• All values in input are integers.

Sample Input 1

5 3 5
1 3 4
3 3 1 1 2

Sample Output 1

2 4 5

At first, the pieces are on Squares 1, 3, and 4. The operations are performed against them as follows:

• The 3-rd piece from the left is on Square 4. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 3-rd piece from the left to Square 5. Now, the pieces are on Squares 1, 3, and 5.
• The 3-rd piece from the left is on Square 5. This is the rightmost square, so do nothing. The pieces are still on Squares 1, 3, and 5.
• The 1-st piece from the left is on Square 1. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 1-st piece from the left to Square 2. Now, the pieces are on Squares 2, 3, and 5.
• The 1-st piece from the left is on Square 2. This is not the rightmost square, but the next square on the right (Square 3) contains a piece, so do nothing. The pieces are still on Squares 2, 3, and 5.
• The 2-nd piece from the left is on Square 3. This is not the rightmost square, and the next square on the right does not contain a piece, so move the 2-nd piece from the left to Square 4; Now, the pieces are still on Squares 2, 4, and 5.

Thus, after the Q operations have ended, the pieces are on Squares 2, 4, and 5, so 2, 4, and 5 should be printed in this order, with spaces in between.

Sample Input 2

2 2 2
1 2
1 2

Sample Output 2

1 2

Sample Input 3

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

Sample Output 3

2 5 6 7 9 10

Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

There is a grid with H rows and W columns.

Each cell of the grid is land or sea, which is represented by H strings S_1, S_2, \ldots, S_H of length W. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left, and (i, j) is land if the j-th character of S_i is ., and (i, j) is sea if the character is #.

The constraints guarantee that all cells on the perimeter of the grid (that is, the cells (i, j) that satisfy at least one of i = 1, i = H, j = 1, j = W) are sea.

Takahashi's spaceship has crash-landed on a cell in the grid. Afterward, he moved N times on the grid following the instructions represented by a string T of length N consisting of L, R, U, and D. For i = 1, 2, \ldots, N, the i-th character of T describes the i-th move as follows:

• L indicates a move of one cell to the left. That is, if he is at (i, j) before the move, he will be at (i, j-1) after the move.
• R indicates a move of one cell to the right. That is, if he is at (i, j) before the move, he will be at (i, j+1) after the move.
• U indicates a move of one cell up. That is, if he is at (i, j) before the move, he will be at (i-1, j) after the move.
• D indicates a move of one cell down. That is, if he is at (i, j) before the move, he will be at (i+1, j) after the move.

It is known that all cells along his path (including the cell where he crash-landed and the cell he is currently on) are not sea. Print the number of cells that could be his current position.

Constraints

• H, W, and N are integers.
• 3 \leq H, W \leq 500
• 1 \leq N \leq 500
• T is a string of length N consisting of L, R, U, and D.
• S_i is a string of length W consisting of . and #.
• There is at least one cell that could be Takahashi's current position.
• All cells on the perimeter of the grid are sea.

Sample Input 1

6 7 5
LULDR
#######
#...#.#
##...##
#.#...#
#...#.#
#######

Sample Output 1

2

The following two cases are possible, so there are two cells that could be Takahashi's current position: (3, 4) and (4, 5).

• He crash-landed on cell (3, 5) and moved (3, 5) \rightarrow (3, 4) \rightarrow (2, 4) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4).
• He crash-landed on cell (4, 6) and moved (4, 6) \rightarrow (4, 5) \rightarrow (3, 5) \rightarrow (3, 4) \rightarrow (4, 4) \rightarrow (4, 5).

Sample Input 2

13 16 9
ULURDLURD
################
##..##.#..####.#
###.#..#.....#.#
#..##..#####.###
#...#..#......##
###.##.#..#....#
##.#####....##.#
###.###.#.#.#..#
######.....##..#
#...#.#.######.#
##..###..#..#.##
#...#.#.#...#..#
################

Sample Output 2

6

Problem Statement

There is an N \times N grid, where each cell is either empty or contains an obstacle. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are also two players on distinct empty cells of the grid. The information about each cell is given as N strings S_1, S_2, \ldots, S_N of length N, in the following format:

• If the j-th character of S_i is P, then (i, j) is an empty cell with a player on it.

• If the j-th character of S_i is ., then (i, j) is an empty cell without a player.

• If the j-th character of S_i is #, then (i, j) contains an obstacle.

Find the minimum number of moves required to bring the two players to the same cell by repeating the following operation. If it is impossible to bring the two players to the same cell by repeating the operation, print -1.

• Choose one of the four directions: up, down, left, or right. Then, each player attempts to move to the adjacent cell in that direction. Each player moves if the destination cell exists and is empty, and does not move otherwise.

Constraints

• N is an integer between 2 and 60, inclusive.
• S_i is a string of length N consisting of P, ., and #.
• There are exactly two pairs (i, j) where the j-th character of S_i is P.

Sample Input 1

5
....#
#..#.
.P...
..P..
....#

Sample Output 1

3

Let us call the player starting at (3, 2) Player 1 and the player starting at (4, 3) Player 2.

For example, doing the following brings the two players to the same cell in three moves:

• Choose left. Player 1 moves to (3, 1), and Player 2 moves to (4, 2).

• Choose up. Player 1 does not move, and Player 2 moves to (3, 2).

• Choose left. Player 1 does not move, and Player 2 moves to (3, 1).

Sample Input 2

2
P#
#P

Sample Output 2

-1

Sample Input 3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

Sample Output 3

10

Problem Statement

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

Perform the following operation M times:

• For each i\ (1\leq i \leq N), add i to A_i. Then, find the minimum non-negative integer not contained in A.

Constraints

• 1\leq N,M \leq 2\times 10^5
• -10^9\leq A_i\leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
-1 -1 -6

Sample Output 1

2
2
0

The 1-st operation makes the sequence A

(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).

The minimum non-negative integer not contained in A is 2.

The 2-nd operation makes the sequence A

(0 + 1, 1 +2 ,-3+3) = (1,3,0).

The minimum non-negative integer not contained in A is 2.

The 3-rd operation makes the sequence A

(1 + 1, 3 +2 ,0+3) = (2,5,3).

The minimum non-negative integer not contained in A is 0.

Sample Input 2

5 6
-2 -2 -5 -7 -15

Sample Output 2

1
3
2
0
0
0

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• 1 \leq B_i \leq 10^9
• All values in input are integers.

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10