Problem Statement

You are given a string S, which represents a weather forecast for the seven days starting tomorrow.
The i-th of those seven days is forecast to be sunny if the i-th character of S is o, and rainy if that character is x.

Tell us whether the N-th day is forecast to be sunny.

Constraints

• N is an integer between 1 and 7 (inclusive).
• S is a string of length 7 consisting of o and x.

Sample Input 1

4
oooxoox

Sample Output 1

No

The forecast for each of the seven days starting tomorrow is as follows: sunny, sunny, sunny, rainy, sunny, sunny, rainy.
In particular, the fourth day is forecast to be rainy.

Sample Input 2

7
ooooooo

Sample Output 2

Yes

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

• For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

• 1 \leq P_i \leq 26
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

2 1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

5 11 12 16 25 17 18 1 7 10 4 23 20 3 2 24 26 19 14 9 6 22 8 13 15 21

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

Problem Statement

We have two figures S and T on a two-dimensional grid with square cells.

S lies within a grid with N rows and N columns, and consists of the cells where S_{i,j} is #.
T lies within the same grid with N rows and N columns, and consists of the cells where T_{i,j} is #.

Determine whether it is possible to exactly match S and T by 90-degree rotations and translations.

Constraints

• 1 \leq N \leq 200
• Each of S and T consists of # and ..
• Each of S and T contains at least one #.

Sample Input 1

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

Sample Output 1

Yes

We can match S to T by rotating it 90-degrees counter-clockwise and translating it.

Sample Input 2

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

Sample Output 2

No

It is impossible to match them by 90-degree rotations and translations.

Sample Input 3

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

Sample Output 3

Yes

Each of S and T may not be connected.

Sample Input 4

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

Sample Output 4

No

Note that it is not allowed to rotate or translate just a part of a figure; it is only allowed to rotate or translate a whole figure.

Problem Statement

We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?

Constraints

• 4 \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)
• All values in input are integers.

Sample Input 1

6
0 0
0 1
1 0
1 1
2 0
2 1

Sample Output 1

3

There are three such rectangles:

the rectangle whose vertices are Points 1, 2, 3, 4,

the rectangle whose vertices are Points 1, 2, 5, 6,

and the rectangle whose vertices are Points 3, 4, 5, 6.

Sample Input 2

4
0 1
1 2
2 3
3 4

Sample Output 2

0

Sample Input 3

7
0 1
1 0
2 0
2 1
2 2
3 0
3 2

Sample Output 3

1

Problem Statement

We have a connected undirected graph with N vertices and M edges.
The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects Vertices A_i and B_i.

Takahashi is going to remove zero or more edges from this graph.

When removing Edge i, a reward of C_i is given if C_i \geq 0, and a fine of |C_i| is incurred if C_i<0.

Find the maximum total reward that Takahashi can get when the graph must be connected after removing edges.

Constraints

• 2 \leq N \leq 2\times 10^5
• N-1 \leq M \leq 2\times 10^5
• 1 \leq A_i,B_i \leq N
• -10^9 \leq C_i \leq 10^9
• The given graph is connected.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

4

Removing Edges 4 and 5 yields a total reward of 4. You cannot get any more, so the answer is 4.

Sample Input 2

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

Sample Output 2

1

There may be edges that give a negative reward when removed.

Sample Input 3

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

Sample Output 3

5

There may be multi-edges and self-loops.

Problem Statement

You are given a directed graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i (1 \leq i \leq M) goes from Vertex s_i to Vertex t_i and has a length of 1.

For each i (1 \leq i \leq M), find the shortest distance from Vertex 1 to Vertex N when all edges except Edge i are passable, or print -1 if Vertex N is unreachable from Vertex 1.

Constraints

• 2 \leq N \leq 400
• 1 \leq M \leq N(N-1)
• 1 \leq s_i,t_i \leq N
• s_i \neq t_i
• (s_i,t_i) \neq (s_j,t_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

1
2
1

Sample Input 2

4 4
1 2
2 3
2 4
3 4

Sample Output 2

-1
2
3
2

Vertex N is unreachable from Vertex 1 when all edges except Edge 1 are passable, so the corresponding line contains -1.

Sample Input 3

5 10
1 2
1 4
1 5
2 1
2 3
3 1
3 2
3 5
4 2
4 3

Sample Output 3

1
1
3
1
1
1
1
1
1
1

Sample Input 4

4 1
1 2

Sample Output 4

-1

Problem Statement

We have a tree with N vertices numbered 1 through N. The i-th edge (1 \leq i \leq N-1) connects Vertex u_i and Vertex v_i, and Vertex i (1 \leq i \leq N) has an even number A_i written on it. Taro and Jiro will play a game using this tree and a piece.

Initially, the piece is on Vertex 1. With Taro going first, the players alternately move the piece to a vertex directly connected to the vertex on which the piece lies. However, the piece must not revisit a vertex it has already visited. The game ends when the piece gets unable to move.

Taro wants to maximize the median of the (multi-)set of numbers written on the vertices visited by the piece before the end of the game (including Vertex 1), and Jiro wants to minimize this value. Find the median of this set when both players play optimally.

Constraints

• 2 \leq N \leq 10^5
• 2 \leq A_i \leq 10^9
• A_i is even.
• 1 \leq u_i < v_i \leq N
• The given graph is a tree.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

7

When both players play optimally, the game goes as follows.

• Taro moves the piece from Vertex 1 to Piece 5.
• Jiro moves the piece from Vertex 5 to Piece 4.
• Taro moves the piece from Vertex 4 to Piece 3.
• Jiro cannot move the piece, so the game ends.

Here, the set of numbers written on the vertices visited by the piece is \{2,10,8,6\}. The median of this set is 7, which should be printed.

Sample Input 2

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

Sample Output 2

8

When both players play optimally, the game goes as follows.

• Taro moves the piece from Vertex 1 to Piece 4.
• Jiro cannot move the piece, so the game ends.

Here, the set of numbers written on the vertices visited by the piece is \{6,10\}. The median of this set is 8, which should be printed.

Sample Input 3

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

Sample Output 3

2

Problem Statement

There are N lamps numbered 1 through N arranged in a row. You are going to light R of them in red and N-R in blue.

For each i=1,\ldots,N-1, a reward of A_i is given if Lamp i and Lamp i+1 light up in different colors.

Find the maximum total reward that can be obtained by efficiently deciding the colors of the lamps.

Constraints

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

Sample Input 1

6 2
3 1 4 1 5

Sample Output 1

11

Lighting up Lamps 3, 5 in red and Lamps 1, 2, 4, 6 in blue yields a total reward of A_2+A_3+A_4+A_5=11.

You cannot get any more, so the answer is 11.

Sample Input 2

7 6
2 7 1 8 2 8

Sample Output 2

10

Lighting up Lamps 1, 2, 3, 4, 5, 7 in red and Lamp 6 in blue yields a total reward of A_5+A_6=10.

Sample Input 3

11 7
12345 678 90123 45678901 234567 89012 3456 78901 23456 7890

Sample Output 3

46207983