Problem Statement

There are N seats in a row, numbered 1, 2, \ldots, N.

The state of the seats is given by a string S of length N consisting of # and .. If the i-th character of S is #, it means seat i is occupied; if it is ., seat i is unoccupied.

Find the number of integers i between 1 and N - 2, inclusive, that satisfy the following condition:

• Seats i and i + 2 are occupied, and seat i + 1 is unoccupied.

Constraints

• N is an integer satisfying 1 \leq N \leq 2 \times 10^5.
• S is a string of length N consisting of # and ..

Sample Input 1

6
#.##.#

Sample Output 1

2

i = 1 and 4 satisfy the condition, so the answer is 2.

Sample Input 2

1
#

Sample Output 2

0

Sample Input 3

9
##.#.#.##

Sample Output 3

3

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq X_i, Y_i \leq 10^9
• All input values are integers.

Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

• Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
• Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
• Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....

Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872

Problem Statement

You are given a grid with N rows and N columns, where N is an even number. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.

Each cell is painted black or white. If A_{i, j} = #, cell (i, j) is black; if A_{i, j} = ., it is white.

Find the color of each cell after performing the following operation for i = 1, 2, \ldots, \frac{N}{2} in this order.

• For all pairs of integers x, y between i and N + 1 - i, inclusive, replace the color of cell (y, N + 1 - x) with the color of cell (x, y). Perform these replacements simultaneously for all such pairs x, y.

Constraints

• N is an even number between 2 and 3000, inclusive.
• Each A_{i, j} is # or ..

Sample Input 1

8
.......#
.......#
.####..#
.####..#
.##....#
.##....#
.#######
.#######

Sample Output 1

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

The operations change the colors of the grid cells as follows:

.......#   ........   ........   ........   ........
.......#   ######..   #######.   #######.   #######.
.####..#   ######..   #....##.   #.....#.   #.....#.
.####..# → ##..##.. → #....##. → #.##..#. → #.###.#.
.##....#   ##..##..   #..####.   #.##..#.   #.#...#.
.##....#   ##......   #..####.   #.#####.   #.#####.
.#######   ##......   #.......   #.......   #.......
.#######   ########   ########   ########   ########

Sample Input 2

6
.#.#.#
##.#..
...###
###...
..#.##
#.#.#.

Sample Output 2

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

Sample Input 3

12
.......#.###
#...#...#..#
###.#..#####
..#.#.#.#...
.#.....#.###
.......#.#..
#...#..#....
#####.......
...#...#.#.#
..###..#..##
#..#.#.#.#.#
.####.......

Sample Output 3

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

Problem Statement

You are given a string S consisting of uppercase English letters.

Find the number of integer triples (i, j, k) satisfying both of the following conditions:

• 1 \leq i < j < k \leq |S|
• The length-3 string formed by concatenating S_i, S_j, and S_k in this order is a palindrome.

Here, |S| denotes the length of S, and S_x denotes the x-th character of S.

Constraints

• S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of uppercase English letters.

Sample Input 1

ABCACC

Sample Output 1

5

The triples satisfying the conditions are (i, j, k) = (1, 2, 4), (1, 3, 4), (3, 4, 5), (3, 4, 6), (3, 5, 6).

Sample Input 2

OOOOOOOO

Sample Output 2

56

Sample Input 3

XYYXYYXYXXX

Sample Output 3

75

Problem Statement

There are N people divided into three teams.

The people are numbered 1, 2, \ldots, N, and the teams are numbered 1, 2, 3. Currently, person i belongs to team A_i.

Each person has a value called strength; person i has a strength of B_i. The strength of a team is defined as the sum of the strengths of its members.

Determine whether it is possible for zero or more people to switch teams so that all teams have equal strength. If it is possible, find the minimum number of people who need to switch teams to achieve this.

You cannot create new teams other than teams 1, 2, 3.

Constraints

• 3 \leq N \leq 100
• A_i \in \lbrace 1, 2, 3 \rbrace
• For each x \in \lbrace 1, 2, 3 \rbrace, there exists some i with A_i = x.
• 1 \leq B_i
• \displaystyle\sum_{i = 1}^{N} B_i \leq 1500
• All input values are integers.

Sample Input 1

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

Sample Output 1

2

If person 1 switches to team 3 and person 4 switches to team 2, all teams will have a strength of 8.

Sample Input 2

4
1 1
1 2
2 3
3 4

Sample Output 2

-1

Sample Input 3

3
1 1
2 1
3 1

Sample Output 3

0

Sample Input 4

12
2 5
1 4
3 3
2 3
3 9
1 2
2 2
3 9
2 6
1 9
1 1
3 1

Sample Output 4

3

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N, and M roads numbered 1 to M.
Road i connects cities A_i and B_i bidirectionally and has a length of C_i.

You are given Q queries to process in order. The queries are of the following two types.

• 1 i: Road i becomes closed.
• 2 x y: Print the shortest distance from city x to city y, using only roads that are not closed. If city y cannot be reached from city x, print -1 instead.

It is guaranteed that each test case contains at most 300 queries of the first type.

Constraints

• 2 \leq N \leq 300
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i < B_i \leq N
• All pairs (A_i, B_i) are distinct.
• 1 \leq C_i \leq 10^9
• 1 \leq Q \leq 2 \times 10^5
• In the queries of the first type, 1 \leq i \leq M.
• The road given in a query of the first type is not already closed at that time.
• The number of queries of the first type is at most 300.
• In the queries of the second type, 1 \leq x < y \leq N.
• All input values are integers.

Sample Input 1

3 3 5
1 2 5
1 3 10
2 3 6
2 1 3
1 2
2 1 3
1 1
2 1 3

Sample Output 1

10
11
-1

• In the first query, print the shortest distance from city 1 to city 3, which is 10.
• In the second query, road 2 becomes closed.
• In the third query, print the shortest distance from city 1 to city 3, which is 11.
• In the fourth query, road 1 becomes closed.
• In the fifth query, city 3 cannot be reached from city 1, so print -1.

Sample Input 2

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

Sample Output 2

-1
-1
-1

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N, and M roads numbered 1 to M.
Road i connects cities A_i and B_i bidirectionally and has a length of C_i.

For each i = 1, \ldots, M, determine whether the following two values are different.

• The shortest distance from city 1 to city N when all roads are passable
• The shortest distance from city 1 to city N when the M - 1 roads other than road i are passable

If city N can be reached from city 1 in one of these cases but not the other, the two values are considered different.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N
• All pairs (A_i, B_i) are distinct.
• 1 \leq C_i \leq 10^9
• City N can be reached from city 1 when all roads are passable.
• All input values are integers.

Sample Input 1

3 3
1 2 5
1 3 10
2 3 6

Sample Output 1

No
Yes
No

When all roads are passable, the shortest distance from city 1 to city 3 is 10.

• When the two roads other than road 1 are passable, the shortest distance is 10.
• When the two roads other than road 2 are passable, the shortest distance is 11.
• When the two roads other than road 3 are passable, the shortest distance is 10.

Sample Input 2

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

Sample Output 2

No
No
No
No
No
Yes

When all roads are passable, the shortest distance from city 1 to city 4 is 1.

When the five roads other than road 6 are passable, the shortest distance is 2.

Sample Input 3

2 1
1 2 1

Sample Output 3

Yes

When the zero roads other than road 1 are passable, city 2 cannot be reached from city 1.