Problem Statement

There was an exam consisting of three problems worth 1, 2, and 4 points.

Takahashi, Aoki, and Snuke took this exam. Takahashi scored A points, and Aoki scored B points.

Snuke solved all of the problems solved by at least one of Takahashi and Aoki, and failed to solve any of the problems solved by neither of them.

Find Snuke's score.

It can be proved that Snuke's score is uniquely determined under the Constraints of this problem.

Constraints

• 0\leq A,B \leq 7
• A and B are integers.

Sample Input 1

1 2

Sample Output 1

3

Since Takahashi scored 1 point, we see that he solved only the 1-point problem and failed to solve the other two.
Similarly, since Aoki scored 2 points, we see that he solved only the 2-point problem and failed to solve the other two.

Therefore, Snuke must have solved the 1- and 2-point problems, but not the 4-point one, which Takahashi and Aoki both failed to solve, for a score of 3 points. Thus, 3 should be printed.

Sample Input 2

5 3

Sample Output 2

7

Since Takahashi scored 5 points, we see that he solved the 1- and 4-point problems but not the 2-point one.
Similarly, since Aoki scored 3 points, we see that he solved the 1- and 2-point problems but not the 4-point one.

Therefore, each of the three problems is solved by at least one of Takahashi and Aoki, so we see that Snuke solved all of the problems, for a score of 7 points. Thus, 7 should be printed.

Sample Input 3

0 0

Sample Output 3

0

Both Takahashi and Aoki solved none of the problems. Therefore, so did Snuke. Thus, 0 should be printed.

Problem Statement

We have the following 3 \times 3 board with integers from 1 through 9 written on it.

You are given two integers A and B between 1 and 9, where A < B.

Determine if the two squares with A and B written on them are adjacent horizontally.

Constraints

• 1 \le A < B \le 9
• A and B are integers.

Sample Input 1

7 8

Sample Output 1

Yes

The two squares with 7 and 8 written on them are adjacent horizontally, so print Yes.

Sample Input 2

1 9

Sample Output 2

No

Sample Input 3

3 4

Sample Output 3

No

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

• 3 \leq N \leq 10^5
• 1 \leq a_i \lt b_i \leq N
• The given graph is a tree.

Sample Input 1

5
1 4
2 4
3 4
4 5

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

4
2 4
1 4
2 3

Sample Output 2

No

The given graph is not a star.

Sample Input 3

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

Sample Output 3

Yes

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 is on a two-dimensional plane. Starting from the origin, he made N moves.

The N moves are represented by a string of length N as described below:

• Takahashi's coordinates after the i-th move are:

  • (x+1,y) if the i-th character of S is R;
  • (x-1,y) if the i-th character of S is L;
  • (x,y+1) if the i-th character of S is U; and
  • (x,y-1) if the i-th character of S is D,

  where (x,y) is his coordinates before the move.

Determine if Takahashi visited the same coordinates multiple times in the course of the N moves (including the starting and ending points).

Constraints

• 1 \leq N \leq 2\times 10^5
• N is an integer.
• S is a string of length N consisting of R, L, U, and D.

Sample Input 1

5
RLURU

Sample Output 1

Yes

Takahashi's coordinates change as follows: (0,0)\to (1,0)\to (0,0)\to (0,1)\to (1,1)\to (1,2).

Sample Input 2

20
URDDLLUUURRRDDDDLLLL

Sample Output 2

No

Problem Statement

The coordinate plane is covered with 2\times1 tiles. The tiles are laid out according to the following rules:

• For an integer pair (i,j), the square A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace is contained in one tile.
• When i+j is even, A _ {i,j} and A _ {i + 1,j} are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point (S _ x+0.5,S _ y+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

• Choose a direction (up, down, left, or right) and a positive integer n. Move n units in that direction.

Each time he enters a tile, he pays a toll of 1.

Find the minimum toll he must pay to reach the point (T _ x+0.5,T _ y+0.5).

Constraints

• 0\leq S _ x\leq2\times10 ^ {16}
• 0\leq S _ y\leq2\times10 ^ {16}
• 0\leq T _ x\leq2\times10 ^ {16}
• 0\leq T _ y\leq2\times10 ^ {16}
• All input values are integers.

Sample Input 1

5 0
2 5

Sample Output 1

5

For example, Takahashi can pay a toll of 5 by moving as follows:

• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.
• Move left by 1. Pay a toll of 0.
• Move up by 3. Pay a toll of 3.
• Move left by 1. Pay a toll of 0.
• Move up by 1. Pay a toll of 1.

It is impossible to reduce the toll to 4 or less, so print 5.

Sample Input 2

3 1
4 1

Sample Output 2

0

There are cases where no toll needs to be paid.

Sample Input 3

2552608206527595 5411232866732612
771856005518028 7206210729152763

Sample Output 3

1794977862420151

Note that the value to be output may exceed the range of a 32-bit integer.

Problem Statement

KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

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

Sample Input 1

3 3
2 3 4

Sample Output 1

2

There can be two projects, each composed of three employees from distinct departments.

Sample Input 2

4 2
1 1 3 4

Sample Output 2

4

Sample Input 3

4 3
1 1 3 4

Sample Output 3

2

Problem Statement

There is a 3 \times 3 grid. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left (1 \leq i, j \leq 3). Cell (i, j) contains an integer A_{i,j}. It is guaranteed that \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd. Additionally, all cells are initially painted white.

Takahashi and Aoki will play a game using this grid. Takahashi goes first, and they take turns performing the following operation:

• Choose a cell (i, j) (1\leq i, j \leq 3) that is still painted white (it can be shown that such a cell always exists at the time of the operation). The player performing the operation scores A_{i,j} points. Then, if the player is Takahashi, he paints the cell (i, j) red; if the player is Aoki, he paints it blue.

After each operation, the following checks are made:

• Check if there are three consecutive cells painted the same color (red or blue) in any row, column, or diagonal. If such a sequence exists, the game ends immediately, and the player whose color forms the sequence wins.
• Check if there are white cells left. If no white cells remain, the game ends, and the player with the higher total score wins.

It can be shown that the game will always end after a finite number of moves, and either Takahashi or Aoki will win. Determine which player wins if both play optimally for victory.

Constraints

• |A_{i,j}| \leq 10^9
• \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd.
• All input values are integers.

Sample Input 1

0 0 0
0 1 0
0 0 0

Sample Output 1

Takahashi

If Takahashi chooses cell (2,2) in his first move, no matter how Aoki plays afterward, Takahashi can always act to prevent three consecutive blue cells. If three consecutive red cells are formed, Takahashi wins. If the game ends without three consecutive red cells, at that point, Takahashi has scored 1 point and Aoki 0 points, so Takahashi wins either way.

Sample Input 2

-1 1 0
-4 -2 -5
-4 -1 -5

Sample Output 2

Aoki

Problem Statement

For a string S of length N and an integer i\ (0\leq i\leq N), let us define the string f_i(S) as the concatenation of:

• the first i characters of S,
• the reversal of S, and
• the last (N-i) characters of S,

in this order. For instance, if S= abc and i=2, we have f_i(S)= abcbac.

You are given a string T of length 2N. Find a pair of a string S of length N and an integer i\ (0\leq i\leq N) such that f_i(S)=T. If no such pair of S and i exists, report that fact.

Constraints

• 1\leq N \leq 10^6
• N is an integer.
• T is a string of length 2N consisting of lowercase English letters.

Sample Input 1

3
abcbac

Sample Output 1

abc
2

As mentioned in the problem statement, if S= abc and i=2, we have f_i(S)= abcbac, which equals T, so you should print abc and 2.

Sample Input 2

4
abababab

Sample Output 2

abab
1

S= abab and i=3 also satisfy the condition.

Sample Input 3

3
agccga

Sample Output 3

cga
0

S= agc and i=3 also satisfy the condition.

Sample Input 4

4
atcodeer

Sample Output 4

-1

If no pair of S and i satisfies the condition, print -1.