Problem Statement

Given a string S of length N consisting of lowercase English alphabets, print the last character of S.

Constraints

• N is an integer.
• 1 ≤ N ≤ 1000
• S is a string of length N consisting of lowercase English alphabets.

Sample Input 1

5
abcde

Sample Output 1

e

The last character of S = {}abcde is e, so e should be printed.

Sample Input 2

1
a

Sample Output 2

a

Problem Statement

You are given a positive integer D.

Find the area of a circle with diameter D.

Constraints

• 1\le D\le 100
• The input value is an integer.

Sample Input 1

2

Sample Output 1

3.141592653589793

The area of a circle with diameter 2 is 3.141592653589793\ldots.

Sample Input 2

7

Sample Output 2

38.48451000647496

Sample Input 3

98

Sample Output 3

7542.9639612690935

Problem Statement

Takahashi has N friends. They have nicknames: Friend 1, Friend 2, \ldots, Friend N.

One day, Takahashi accidentally let one of his friends, Friend X, learn his shameful secret.
For each i = 1, 2, \ldots, N, when Friend i learns the secret, he/she will share it with Friend A_i, if Friend A_i has not already learned it.

How many of Takahashi's friends will learn the secret in the end?

Constraints

• 2 \leq N \leq 10^5
• 1 \leq X \leq N
• 1 \leq A_i \leq N
• A_i \neq i
• All values in input are integers.

Sample Input 1

4 2
3 1 1 2

Sample Output 1

3

Takahashi's secret will be learned by Friend 1, Friend 2, and Friend 3, as follows.

• One day, Takahashi let Friend 2 learn the secret.
• Friend 2 shares it with Friend 1.
• Friend 1 shares it with Friend 3.

In the end, three of his friends learn the secret, so we print 3.

Sample Input 2

20 12
7 11 10 1 7 20 14 2 17 3 2 5 19 20 8 14 18 2 10 10

Sample Output 2

7

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row (1\le i\le H) from the top and the j-th column (1\le j\le W) from the left.

Each cell is painted with one color, white or black. The color painted on the cells is represented by H strings S _ 1,S _ 2,\ldots,S _ H. When the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is ., cell (i,j) is painted white, and when the j-th character (1\le j\le W) of S _ i\ (1\le i\le H) is #, cell (i,j) is painted black.

Determine whether the grid satisfies the following condition:

• For every black cell, the number of horizontally or vertically adjacent cells that are painted black is 2 or 4.

Here, cells (i,j)\ (1\le i\le H,1\le j\le W) and (k,l)\ (1\le k\le H,1\le l\le W) are horizontally or vertically adjacent if and only if |i-k|+|j-l|=1.

Constraints

• 1\le H\le 20
• 1\le W\le 20
• H and W are integers.
• S _ i is a string of length W consisting of . and # (1\le i\le H).

Sample Input 1

8 7
.######
##....#
#.###.#
#.#.#.#
#.#.#.#
#.#####
#...#..
#####..

Sample Output 1

Yes

For example, cell (6,3) is painted black, and among the adjacent cells (5,3),(6,2),(6,4),(7,3), cells (5,3) and (6,4) are painted black, which is 2 cells, so it satisfies the condition.

Every other black cell also satisfies the condition, so output Yes.

Sample Input 2

1 2
##

Sample Output 2

No

Cell (1,1) is painted black, but it has only one adjacent cell, so it does not satisfy the condition.

Therefore, output No.

Sample Input 3

4 3
...
...
...
...

Sample Output 3

Yes

There are no black cells, so the condition is satisfied.

Therefore, output Yes.

Sample Input 4

15 18
##.###..##.##..##.
##.#.##.##.##.####
...##.#.......####
###.###....###.##.
#.##.......#.#....
#..#.##.##.#.#....
#.########.####.##
#.##.##.#....##.##
#......##.........
##.##..#..##..####
.#.#####..#####..#
.#..#...##.#.....#
.#..#.####.#.....#
.##.#.#.#..##..###
..###.###...####..

Sample Output 4

Yes

Problem Statement

There are N cells, cell 1, cell 2,\ldots, cell N, arranged in a line. Cell i has an integer A_i\ (i \le A_i \le N) written on it.

For each of s=1,2,\ldots,N, solve the following problem.

• Initially, place a piece on cell s. After performing the operation "let x be the integer written on the cell where the piece is placed, and then move the piece to cell x" 10^{100} times, output the number of the cell where the piece is placed.

Constraints

• 1 \le N \le 5\times10^5
• i \le A_i \le N\ (1 \le i \le N)
• All input values are integers.

Sample Input 1

7
2 4 7 5 5 6 7

Sample Output 1

5 5 7 5 5 6 7

For s=1, the piece moves as shown in the following figure.

When the piece is placed on cell 5, the operation does not move the piece, so the answer for s=1 is 5.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

1 2 3 4 5

It is possible that the piece never moves.

Sample Input 3

15
11 3 10 7 15 10 10 11 11 13 11 12 14 14 15

Sample Output 3

11 14 14 14 15 14 14 11 11 14 11 12 14 14 15

Problem Statement

Takahashi is at coordinate 0.5 on a number line.

He will make N moves.
In the i-th move, he chooses either the positive direction or the negative direction, and moves L_i in that direction.

What is the maximum number of times he can pass through coordinate 0?
Under the constraints of this problem, no move will end at coordinate 0.

Constraints

• 1 \le N \le 20
• 1 \le L_i \le 10^9
• All input values are integers.

Sample Input 1

5
2 5 2 2 1

Sample Output 1

4

For example, by choosing the directions of movement as follows, he can pass through coordinate 0 four times, which is the maximum.

• In the first move, choose the negative direction and move 2. He moves from coordinate 0.5 to -1.5, passing through coordinate 0.
• In the second move, choose the positive direction and move 5. He moves from coordinate -1.5 to 3.5, passing through coordinate 0.
• In the third move, choose the negative direction and move 2. He moves from coordinate 3.5 to 1.5.
• In the fourth move, choose the negative direction and move 2. He moves from coordinate 1.5 to -0.5, passing through coordinate 0.
• In the fifth move, choose the positive direction and move 1. He moves from coordinate -0.5 to 0.5, passing through coordinate 0.

Sample Input 2

5
100 1 2 3 4

Sample Output 2

1

Sample Input 3

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Sample Output 3

20

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do Q operations, each of which is of one of the following three types.

• Type 1: Write an integer X_i on a blank ball and put it in the bag.
• Type 2: For each ball in the bag, replace the integer written on it with that integer plus X_i.
• Type 3: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each 1\leq i\leq Q, you are given the type P_i of the i-th operation and the value of X_i if the operation is of Type 1 or 2. Print the integers recorded in the operations of Type 3 in order.

Constraints

• 1 \leq Q \leq 2\times 10^5
• 1 \leq P_i \leq 3
• 1 \leq X_i \leq 10^9
• All values in input are integers.
• There is one or more i such that P_i=3.
• If P_i=3, the bag contains at least one ball just before the i-th operation.

Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

• Write 3 on a ball and put it in the bag.
• Write 5 on a ball and put it in the bag.
• The bag now contains a ball with 3 and another with 5. Pick up the ball with the smaller of them, or 3. Record 3 and throw it away.
• The bag now contains just a ball with 5. Replace this integer with 5+2=7.
• The bag now contains just a ball with 7. Pick up this ball, record 7, and throw it away.

Therefore, we should print 3 and 7, in the order they are recorded.

Sample Input 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

Sample Output 2

5000000000

Note that the outputs may not fit into a 32-bit integer.

Problem Statement

You are given a simple directed graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i is a directed edge from vertex u_i to vertex v_i.

You may perform the following operation zero or more times.

• Choose distinct vertices x and y such that there is no directed edge from vertex x to vertex y, and add a directed edge from vertex x to vertex y.

Find the minimum number of times you need to perform the operation to make the graph satisfy the following condition.

• For every triple of distinct vertices a, b, and c, if there are directed edges from vertex a to vertex b and from vertex b to vertex c, there is also a directed edge from vertex a to vertex c.

Constraints

• 3 \leq N \leq 2000
• 0 \leq M \leq 2000
• 1 \leq u_i ,v_i \leq N
• u_i \neq v_i
• (u_i,v_i) \neq (u_j,v_j) if i \neq j.
• All values in the input are integers.

Sample Input 1

4 3
2 4
3 1
4 3

Sample Output 1

3

Initially, the condition is not satisfied because, for instance, for vertices 2, 4, and 3, there are directed edges from vertex 2 to vertex 4 and from vertex 4 to vertex 3, but not from vertex 2 to vertex 3.

You can make the graph satisfy the condition by adding the following three directed edges:

• one from vertex 2 to vertex 3,
• one from vertex 2 to vertex 1, and
• one from vertex 4 to vertex 1.

On the other hand, the condition cannot be satisfied by adding two or fewer edges, so the answer is 3.

Sample Input 2

292 0

Sample Output 2

0

Sample Input 3

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

Sample Output 3

12

Problem Statement

We have a grid with H rows and W columns. Each square is painted either white or black. For each integer pair (i, j) such that 1 \leq i \leq H and 1 \leq j \leq W, the color of the square at the i-th row from the top and j-th column from the left (we simply denote this square by Square (i, j)) is represented by A_{i, j}. Square (i, j) is white if A_{i, j} = 0, and black if A_{i, j} = 1.

You may perform the following operations any number of (possibly 0) times in any order:

• Choose an integer i such that 1 \leq i \leq H, pay R_i yen (the currency in Japan), and invert the color of each square in the i-th row from the top in the grid. (White squares are painted black, and black squares are painted white.)
• Choose an integer j such that 1 \leq j \leq W, pay C_j yen, and invert the color of each square in the j-th column from the left in the grid.

Print the minimum total cost to satisfy the following condition:

• There exists a path from Square (1, 1) to Square (H, W) that can be obtained by repeatedly moving down or to the right, such that all squares in the path (including Square (1, 1) and Square (H, W)) have the same color.

We can prove that it is always possible to satisfy the condition in a finite number of operations under the Constraints of this problem.

Constraints

• 2 \leq H, W \leq 2000
• 1 \leq R_i \leq 10^9
• 1 \leq C_j \leq 10^9
• A_{i, j} \in \lbrace 0, 1\rbrace
• All values in input are integers.

Sample Input 1

3 4
4 3 5
2 6 7 4
0100
1011
1010

Sample Output 1

9

We denote a white square by 0 and a black square by 1. On the initial grid, you can pay R_2 = 3 yen to invert the color of each square in the 2-nd row from the top to make the grid:

0100
0100
1010

Then, you can pay C_2 = 6 yen to invert the color of each square in the 2-nd row from the left to make the grid:

0000
0000
1110

Now, there exists a path from Square (1, 1) to Square (3, 4) such that all squares in the path have the same color (such as the path (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)). The total cost paid is 3+6 = 9 yen, which is the minimum possible.

Sample Input 2

15 20
29 27 79 27 30 4 93 89 44 88 70 75 96 3 78
39 97 12 53 62 32 38 84 49 93 53 26 13 25 2 76 32 42 34 18
01011100110000001111
10101111100010011000
11011000011010001010
00010100011111010100
11111001101010001011
01111001100101011100
10010000001110101110
01001011100100101000
11001000100101011000
01110000111011100101
00111110111110011111
10101111111011101101
11000011000111111001
00011101011110001101
01010000000001000000

Sample Output 2

125