Problem Statement

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

Output the string obtained by replacing every character in S other than A with ..

Constraints

• S is a string of length between 1 and 100 (inclusive) consisting of uppercase English letters.

Sample Input 1

ATCODER

Sample Output 1

A......

Since the first character is the only occurrence of A in S, output the string obtained by changing the second through seventh characters of S to ..

Sample Input 2

BANANA

Sample Output 2

.A.A.A

S may contain two or more occurrences of A.

Sample Input 3

CORRECT

Sample Output 3

.......

S may contain no occurrence of A.

Problem Statement

There is one stick. This stick has N-1 notches, which divide it into N parts.

The lengths of the parts are L_1,L_2,\dots,L_N in order from one end.

When choosing one notch and breaking the stick there to obtain two sticks, find the minimum possible absolute value of the difference between the lengths of the two resulting sticks.

Here, the width of a notch can be ignored, and the length of each resulting stick is the sum of the lengths of the parts it contains.

Constraints

• 2 \leq N \leq 100
• 1 \leq L_i \leq 10^5
• All input values are integers.

Sample Input 1

4
5 2 3 8

Sample Output 1

2

Breaking the stick at each notch results in the following:

• Breaking at the first notch from the end results in two sticks of lengths 5 and 13, with an absolute difference of 8.
• Breaking at the second notch from the end results in two sticks of lengths 7 and 11, with an absolute difference of 4.
• Breaking at the third notch from the end results in two sticks of lengths 10 and 8, with an absolute difference of 2.

Sample Input 2

7
31 41 59 26 53 58 97

Sample Output 2

51

Sample Input 3

10
67011 35764 33042 24098 63738 98760 17199 68579 21812 45408

Sample Output 3

28105

Problem Statement

Takahashi is staying at his parents' house for an N-day homecoming trip.

At his parents' house, a snack is prepared every day, and the calorie count of the snack on day i is A_i.

To manage his health, he repeats the following: he eats the snack on a given day if and only if the total calorie count of the snacks he has eaten in the most recent M days does not exceed K.

Specifically, in the order i=1,2,\dots,N, he decides whether to eat the snack on day i according to the following rule:

• Assuming that he eats the snack on day i, if the total calorie count of the snacks eaten from day \max(i-M+1,1) through day i is at most K, then he actually eats the snack on day i. Otherwise, he does not eat the snack on day i.

For each i=1,2,\dots,N, determine whether Takahashi eats the snack on day i.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{15}
• 1 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

5 3 83
48 73 59 90 21

Sample Output 1

Yes
No
No
No
Yes

For each day, assuming that he eats the snack, the total calorie count of the snacks eaten in the most recent three days is as follows:

• Day 1: 48
• Day 2: 48+73=121
• Day 3: 48+59=107
• Day 4: 90
• Day 5: 21

Sample Input 2

7 4 728
187 816 349 609 255 308 175

Sample Output 2

Yes
No
Yes
No
Yes
No
Yes

Sample Input 3

10 3 1368290936
216519459 804733999 297250023 775422599 287963235 999315644 354987425 974810607 653940822 117157941

Sample Output 3

Yes
Yes
Yes
No
Yes
Yes
No
No
Yes
Yes

Problem Statement

There is a grid with H rows and W columns. Each cell is an empty cell or a bomb cell. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. The grid is given by H length-W strings S_1, S_2 , \dots ,S_H: if the j-th character of S_i is ., (i,j) is an empty cell, and if the j-th character of S_i is #, (i,j) is a bomb cell.

For an empty cell (i,j), if there is no bomb cell in the i-th row nor in the j-th column, that cell is called a safe empty cell.

In one move, you can move from the current cell to an adjacent empty cell in the up, down, left, or right direction (you cannot move to a bomb cell). Find the number of empty cells (i, j) satisfying the following condition:

• A safe empty cell can be reached from (i,j) in at most K moves.

Constraints

• 1 \le H,W \le 5\times 10^5
• H\times W \le 5\times 10^5
• 0 \le K \le H\times W-1
• S_i is a string of length W consisting of . and #.
• H, W, and K are integers.

Sample Input 1

3 3 1
#..
...
..#

Sample Output 1

5

The only safe empty cell is (2,2). There are five empty cells from which you can reach (2,2) in at most one move: (1,2),(2,1),(2,2),(2,3),(3,2), so the answer is 5.

Sample Input 2

2 3 0
...
...

Sample Output 2

6

Since there is no bomb cell, all six cells are safe empty cells. Therefore, every empty cell satisfies the condition with zero moves.

Sample Input 3

5 7 2
..#....
..#....
.......
...#...
...#...

Sample Output 3

29

Problem Statement

You are given a simple connected undirected graph with N vertices numbered 1 through N and M edges. The i-th edge connects vertices a_i and b_i.

Determine whether there exists a cycle consisting of an odd number of vertices, and if one exists, find one such cycle.

Formally, determine whether there exists an integer sequence (v_1,v_2,\ldots,v_K) satisfying all of the following conditions, and if one exists, find one such sequence.

• K is an odd number at least 3.
• v_1,v_2,\ldots,v_K are all distinct.
• For every integer i with 1\le i \le K, there is an edge between vertices v_i and v_{i+1}, where v_{K+1} = v_1.

You are given T test cases; solve each of them.

Constraints

• 1 \le T \le 2\times10^5
• 1 \le N, M \le 2\times10^5
• The sum of N over all test cases is at most 2\times10^5.
• The sum of M over all test cases is at most 2\times10^5.
• 1 \le a_i,b_i \le N
• a_i\ne b_i
• The given graph is a simple connected undirected graph.
• All input values are integers.

Sample Input 1

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

Sample Output 1

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

In the first test case, the sequence (2,1,3) satisfies the conditions: the edges (2, 1), (1, 3), (3, 2) all exist. Outputs such as v = (2, 3, 1) are also accepted.

In the second test case, there is no cycle with an odd number of vertices, so no sequence satisfies the conditions.

Problem Statement

There is a convex N-gon P on the xy-plane. The vertices of P are numbered 1,2,\dots,N counterclockwise, and the coordinates of vertex i are (x_i,y_i).

Answer Q questions.

The j-th question gives two distinct vertices u_j and v_j. Here, the vertices u_j and v_j are not adjacent on the boundary of P.

The segment connecting vertices u_j and v_j divides P into two polygons; let P' be the one lying to the right of the directed line from vertex u_j to vertex v_j. Find the coordinates of the geometric center of P' (the centroid obtained by regarding the interior of the polygon as a thin plate of uniform density).

Constraints

• 4 \leq N \leq 3 \times 10^4
• 1 \leq Q \leq 2 \times 10^5
• |x_i|,|y_i| \leq 5 \times 10^5
• (x_1,y_1),(x_2,y_2),\dots,(x_N,y_N) form a convex polygon in counterclockwise order.
• All interior angles of P are less than 180 degrees.
• 1 \leq u_j,v_j \leq N
• u_j \neq v_j
• Vertices u_j and v_j are not adjacent on the boundary of P.
• All input values are integers.

Sample Input 1

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

Sample Output 1

-1.000000000000000 1.000000000000000
0.864197530864198 1.209876543209877
0.198198198198198 0.828828828828829
1.391304347826087 0.434782608695652

For the first question, P' is the triangle with vertices (1,3),(-3,2),(-1,-2), and its geometric center is (-1,1).

For the second question, P' is the quadrilateral with vertices (2,-1),(4,1),(1,3),(-3,2), and its geometric center is \left(\frac{70}{81},\frac{98}{81}\right).

Sample Input 2

10 10
480451 142016
404696 274257
7097 390813
-134582 195390
-167108 143104
-359470 -180367
-406293 -273476
74335 -494832
486873 -391664
493159 -292349
5 8
8 6
5 2
5 1
10 3
1 7
3 5
2 5
4 9
1 8

Sample Output 2

-167917.431926206833203 -207268.968943785114349
126221.026579795702381 -68771.715180365014040
111801.954824466955586 -124063.178438661167072
99590.935535112756283 -153792.378227918737825
321662.353363423237819 113722.100435559268610
43574.061369374611386 102411.022160871806300
-98197.666666666666667 243102.333333333333333
79984.488622522356481 269160.678085376751920
-3267.792578363696043 -210454.379232334372417
46257.363593155145794 -38546.483790939251583

Problem Statement

There is a grid with H rows and W columns. Each cell has one of the characters +, -, # written on it. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left. The grid is given by H length-W strings S_1, S_2 , \dots ,S_H: the j-th character of S_i is written on (i,j).

You can perform the following operation zero or more times:

• Choose one cell that is not #. Change to # all cells that are "reachable from the chosen cell only by moving to an adjacent cell in the left, right, or down direction without passing through a cell that is #." Here, the chosen cell itself is included among the reachable cells.

Find the maximum possible value of the following value in the grid after the operations: the number of + cells minus the number of - cells.

Constraints

• 1 \le H,W \le 30
• S_i is a string of length W consisting of +, -, #.
• H and W are integers.

Sample Input 1

2 3
+-+
--+

Sample Output 1

1

If you choose (2,1), all cells in row 2 change to # (note that you cannot move upward). The remaining row 1 has two cells of + and one cell of -, so the value is 2-1=1, and this is the maximum.

Sample Input 2

3 3
+--
-#-
#+#

Sample Output 2

1

If you choose (1,1), all cells except (3, 2) become #. Note that the chosen cell (1, 1) itself is included among the reachable cells, and that you cannot pass through a cell that is #.

Sample Input 3

5 7
++#--++
-+---+#
##++-++
--#-++-
+---#++

Sample Output 3

5