Problem Statement

We have a rectangular parallelepiped of size A×B×C, built with blocks of size 1×1×1. Snuke will paint each of the A×B×C blocks either red or blue, so that:

• There is at least one red block and at least one blue block.
• The union of all red blocks forms a rectangular parallelepiped.
• The union of all blue blocks forms a rectangular parallelepiped.

Snuke wants to minimize the difference between the number of red blocks and the number of blue blocks. Find the minimum possible difference.

Constraints

• 2≤A,B,C≤10^9

Sample Input 1

3 3 3

Sample Output 1

9

For example, Snuke can paint the blocks as shown in the diagram below. There are 9 red blocks and 18 blue blocks, thus the difference is 9.

Sample Input 2

2 2 4

Sample Output 2

0

For example, Snuke can paint the blocks as shown in the diagram below. There are 8 red blocks and 8 blue blocks, thus the difference is 0.

Sample Input 3

5 3 5

Sample Output 3

15

For example, Snuke can paint the blocks as shown in the diagram below. There are 45 red blocks and 30 blue blocks, thus the difference is 9.

Problem Statement

Snuke lives in another world, where slimes are real creatures and kept by some people. Slimes come in N colors. Those colors are conveniently numbered 1 through N. Snuke currently has no slime. His objective is to have slimes of all the colors together.

Snuke can perform the following two actions:

• Select a color i (1≤i≤N), such that he does not currently have a slime in color i, and catch a slime in color i. This action takes him a_i seconds.

• Cast a spell, which changes the color of all the slimes that he currently has. The color of a slime in color i (1≤i≤N-1) will become color i+1, and the color of a slime in color N will become color 1. This action takes him x seconds.

Find the minimum time that Snuke needs to have slimes in all N colors.

Constraints

• 2≤N≤2,000
• a_i are integers.
• 1≤a_i≤10^9
• x is an integer.
• 1≤x≤10^9

Sample Input 1

2 10
1 100

Sample Output 1

12

Snuke can act as follows:

• Catch a slime in color 1. This takes 1 second.
• Cast the spell. The color of the slime changes: 1 → 2. This takes 10 seconds.
• Catch a slime in color 1. This takes 1 second.

Sample Input 2

3 10
100 1 100

Sample Output 2

23

Snuke can act as follows:

• Catch a slime in color 2. This takes 1 second.
• Cast the spell. The color of the slime changes: 2 → 3. This takes 10 seconds.
• Catch a slime in color 2. This takes 1 second.
• Cast the soell. The color of each slime changes: 3 → 1, 2 → 3. This takes 10 seconds.
• Catch a slime in color 2. This takes 1 second.

Sample Input 3

4 10
1 2 3 4

Sample Output 3

10

Snuke can act as follows:

• Catch a slime in color 1. This takes 1 second.
• Catch a slime in color 2. This takes 2 seconds.
• Catch a slime in color 3. This takes 3 seconds.
• Catch a slime in color 4. This takes 4 seconds.

Problem Statement

Snuke and Ciel went to a strange stationery store. Each of them got a transparent graph paper with H rows and W columns.

Snuke painted some of the cells red in his paper. Here, the cells painted red were 4-connected, that is, it was possible to traverse from any red cell to any other red cell, by moving to vertically or horizontally adjacent red cells only.

Ciel painted some of the cells blue in her paper. Here, the cells painted blue were 4-connected.

Afterwards, they precisely overlaid the two sheets in the same direction. Then, the intersection of the red cells and the blue cells appeared purple.

You are given a matrix of letters a_{ij} (1≤i≤H, 1≤j≤W) that describes the positions of the purple cells. If the cell at the i-th row and j-th column is purple, then a_{ij} is #, otherwise a_{ij} is .. Here, it is guaranteed that no outermost cell is purple. That is, if i=1, H or j = 1, W, then a_{ij} is ..

Find a pair of the set of the positions of the red cells and the blue cells that is consistent with the situation described. It can be shown that a solution always exists.

Constraints

• 3≤H,W≤500
• a_{ij} is # or ..
• If i=1,H or j=1,W, then a_{ij} is ..
• At least one of a_{ij} is #.

Sample Input 1

5 5
.....
.#.#.
.....
.#.#.
.....

Sample Output 1

.....
#####
#....
#####
.....

.###.
.#.#.
.#.#.
.#.#.
.....

One possible pair of the set of the positions of the red cells and the blue cells is as follows:

Sample Input 2

7 13
.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.............

Sample Output 2

.............
.###########.
.###.###.###.
.###.###.###.
.###.###.###.
.###.###.###.
.............

.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#########.
.............

One possible pair of the set of the positions of the red cells and the blue cells is as follows:

Problem Statement

There are N towns in Snuke Kingdom, conveniently numbered 1 through N. Town 1 is the capital.

Each town in the kingdom has a Teleporter, a facility that instantly transports a person to another place. The destination of the Teleporter of town i is town a_i (1≤a_i≤N). It is guaranteed that one can get to the capital from any town by using the Teleporters some number of times.

King Snuke loves the integer K. The selfish king wants to change the destination of the Teleporters so that the following holds:

• Starting from any town, one will be at the capital after using the Teleporters exactly K times in total.

Find the minimum number of the Teleporters whose destinations need to be changed in order to satisfy the king's desire.

Constraints

• 2≤N≤10^5
• 1≤a_i≤N
• One can get to the capital from any town by using the Teleporters some number of times.
• 1≤K≤10^9

Sample Input 1

3 1
2 3 1

Sample Output 1

2

Change the destinations of the Teleporters to a = (1,1,1).

Sample Input 2

4 2
1 1 2 2

Sample Output 2

0

There is no need to change the destinations of the Teleporters, since the king's desire is already satisfied.

Sample Input 3

8 2
4 1 2 3 1 2 3 4

Sample Output 3

3

For example, change the destinations of the Teleporters to a = (1,1,2,1,1,2,2,4).

Problem Statement

We have a grid with H rows and W columns. The state of the cell at the i-th (1≤i≤H) row and j-th (1≤j≤W) column is represented by a letter a_{ij}, as follows:

• . : This cell is empty.
• o : This cell contains a robot.
• E : This cell contains the exit. E occurs exactly once in the whole grid.

Snuke is trying to salvage as many robots as possible, by performing the following operation some number of times:

• Select one of the following directions: up, down, left, right. All remaining robots will move one cell in the selected direction, except when a robot would step outside the grid, in which case the robot will explode and immediately disappear from the grid. If a robot moves to the cell that contains the exit, the robot will be salvaged and immediately removed from the grid.

Find the maximum number of robots that can be salvaged.

Constraints

• 2≤H,W≤100
• a_{ij} is ., o or E.
• E occurs exactly once in the whole grid.

Sample Input 1

3 3
o.o
.Eo
ooo

Sample Output 1

3

For example, select left, up, right.

Sample Input 2

2 2
E.
..

Sample Output 2

0

Sample Input 3

3 4
o...
o...
oooE

Sample Output 3

5

Select right, right, right, down, down.

Sample Input 4

5 11
ooo.ooo.ooo
o.o.o...o..
ooo.oE..o..
o.o.o.o.o..
o.o.ooo.ooo

Sample Output 4

12

Problem Statement

You are given an undirected graph with N vertices and M edges. Here, N-1≤M≤N holds and the graph is connected. There are no self-loops or multiple edges in this graph.

The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices a_i and b_i.

The color of each vertex can be either white or black. Initially, all the vertices are white. Snuke is trying to turn all the vertices black by performing the following operation some number of times:

• Select a pair of adjacent vertices with the same color, and invert the colors of those vertices. That is, if the vertices are both white, then turn them black, and vice versa.

Determine if it is possible to turn all the vertices black. If the answer is positive, find the minimum number of times the operation needs to be performed in order to achieve the objective.

Constraints

• 2≤N≤10^5
• N-1≤M≤N
• 1≤a_i,b_i≤N
• There are no self-loops or multiple edges in the given graph.
• The given graph is connected.

Partial Score

• In the test set worth 1500 points, M=N-1.

Sample Input 1

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

Sample Output 1

5

For example, it is possible to perform the operations as shown in the following diagram:

Sample Input 2

3 2
1 2
2 3

Sample Output 2

-1

It is not possible to turn all the vertices black.

Sample Input 3

4 4
1 2
2 3
3 4
4 1

Sample Output 3

2

This case is not included in the test set for the partial score.

Sample Input 4

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

Sample Output 4

7

This case is not included in the test set for the partial score.