Problem Statement

We have a grid with 2 horizontal rows and 2 vertical columns.
Each of the squares is black or white, and there are at least 2 black squares.
The colors of the squares are given to you as strings S_1 and S_2, as follows.

• If the j-th character of S_i is #, the square at the i-th row from the top and j-th column from the left is black.
• If the j-th character of S_i is ., the square at the i-th row from the top and j-th column from the left is white.

You can travel between two different black squares if and only if they share a side.
Determine whether it is possible to travel from every black square to every black square (directly or indirectly) by only passing black squares.

Constraints

• Each of S_1 and S_2 is a string with two characters consisting of # and ..
• S_1 and S_2 have two or more #s in total.

Sample Input 1

##
.#

Sample Output 1

Yes

It is possible to directly travel between the top-left and top-right black squares and between top-right and bottom-right squares.
These two moves enable us to travel from every black square to every black square, so the answer is Yes.

Sample Input 2

.#
#.

Sample Output 2

No

It is impossible to travel between the top-right and bottom-left black squares, so the answer is No.

Problem Statement

You are given positive integers A and B.
Let us calculate A+B (in decimal). If it does not involve a carry, print Easy; if it does, print Hard.

Constraints

• A and B are integers.
• 1 \le A,B \le 10^{18}

Sample Input 1

229 390

Sample Output 1

Hard

When calculating 229+390, we have a carry from the tens digit to the hundreds digit, so the answer is Hard.

Sample Input 2

123456789 9876543210

Sample Output 2

Easy

We do not have a carry here; the answer is Easy.
Note that the input may not fit into a 32-bit integer.

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is A_i per gram, and B_i grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le W \le 3 \times 10^8
• 1 \le A_i \le 10^9
• 1 \le B_i \le 1000

Sample Input 1

3 5
3 1
4 2
2 3

Sample Output 1

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

Sample Input 2

4 100
6 2
1 5
3 9
8 7

Sample Output 2

100

There may be less than W grams of cheese in total.

Sample Input 3

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3

2357689932073

Problem Statement

Given is a string S consisting of X and ..

You can do the following operation on S between 0 and K times (inclusive).

• Replace a . with an X.

What is the maximum possible number of consecutive Xs in S after the operations?

Constraints

• 1 \leq |S| \leq 2 \times 10^5
• Each character of S is X or ..
• 0 \leq K \leq 2 \times 10^5
• K is an integer.

Sample Input 1

XX...X.X.X.
2

Sample Output 1

5

After replacing the Xs at the 7-th and 9-th positions with X, we have XX...XXXXX., which has five consecutive Xs at 6-th through 10-th positions.
We cannot have six or more consecutive Xs, so the answer is 5.

Sample Input 2

XXXX
200000

Sample Output 2

4

It is allowed to do zero operations.

Problem Statement

Given is an undirected graph with N vertices and M edges.
Edge i connects Vertices A_i and B_i.

We will erase Vertices 1, 2, \ldots, N one by one.
Here, erasing Vertex i means deleting Vertex i and all edges incident to Vertex i from the graph.

For each i=1, 2, \ldots, N, how many connected components does the graph have when vertices up to Vertex i are deleted?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )
• 1 \leq A_i \lt B_i \leq N
• (A_i,B_i) \neq (A_j,B_j) if i \neq j.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1
2
3
2
1
0

The figure above shows the transition of the graph.

Sample Input 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

Sample Output 2

3
2
2
1
1
1
1
0

The graph may be disconnected from the beginning.

Problem Statement

Given is an undirected graph with N+1 vertices.
The vertices are called Vertex 0, Vertex 1, \ldots, Vertex N.

For each i=1,2,\ldots,N, the graph has an undirected edge with a weight of A_i connecting Vertex 0 and Vertex i.

Additionally, for each i=1,2,\ldots,N, the graph has an undirected edge with a weight of B_i connecting Vertex i and Vertex i+1. (Here, Vertex N+1 stands for Vertex 1.)

The graph has no edge other than these 2N edges above.

Let us delete some of the edges from this graph so that the graph will be bipartite.
What is the minimum total weight of the edges that have to be deleted?

Constraints

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

Sample Input 1

5
31 4 159 2 65
5 5 5 5 10

Sample Output 1

16

Deleting the edge connecting Vertices 0,2 (weight: 4), the edge connecting Vertices 0,4 (weight: 2), and the edge connecting Vertices 1,5 (weight: 10) makes the graph bipartite.

Sample Input 2

4
100 100 100 1000000000
1 2 3 4

Sample Output 2

10

Problem Statement

Given is a string S consisting of Y and ..

You can do the following operation on S between 0 and K times (inclusive).

• Swap two adjacent characters in S.

What is the maximum possible number of consecutive Ys in S after the operations?

Constraints

• 2 \leq |S| \leq 2 \times 10^5
• Each character of S is Y or ..
• 0 \leq K \leq 10^{12}
• K is an integer.

Sample Input 1

YY...Y.Y.Y.
2

Sample Output 1

3

After swapping the 6-th, 7-th characters, and 9-th, 10-th characters, we have YY....YYY.., which has three consecutive Ys at 7-th through 9-th positions.
We cannot have four or more consecutive Ys, so the answer is 3.

Sample Input 2

YYYY....YYY
3

Sample Output 2

4

Problem Statement

There is a grid with N rows and N columns, where each square has one white piece, one black piece, or nothing on it.
The square at the i-th row from the top and j-th column from the left is described by S_{i,j}. If S_{i,j} is W, the square has a white piece; if S_{i,j} is B, it has a black piece; if S_{i,j} is ., it is empty.

Takahashi and Snuke will play a game, where the players take alternate turns, with Takahashi going first.

In Takahashi's turn, he does one of the following operations.

• Choose a white piece that can move one square up to an empty square, and move it one square up (see below).
• Eat a black piece of his choice.

In Snuke's turn, he does one of the following operations.

• Choose a black piece that can move one square up to an empty square, and move it one square up.
• Eat a white piece of his choice.

The player who becomes unable to do the operation loses the game. Which player will win when both players play optimally?

Here, moving a piece one square up means moving a piece at the i-th row and j-th column to the (i-1)-th row and j-th column.
Note that this is the same for both players; they see the board from the same direction.

Constraints

• 1 \leq N \leq 8
• N is an integer.
• S_{i,j} is W, B, or ..

Sample Input 1

3
BB.
.B.
...

Sample Output 1

Takahashi

If Takahashi eats the black piece at the 1-st row and 1-st columns, the board will become:

.B.
.B.
...

Then, Snuke cannot do an operation, making Takahashi win.
Note that it is forbidden to move a piece out of the board or to a square occupied by another piece.

Sample Input 2

2
..
WW

Sample Output 2

Snuke

Sample Input 3

4
WWBW
WWWW
BWB.
BBBB

Sample Output 3

Snuke