Problem Statement

You are given a real number X.Y, where Y is a single digit.

Print the following: (quotes for clarity)

• X-, if 0 \leq Y \leq 2;
• X, if 3 \leq Y \leq 6;
• X+, if 7 \leq Y \leq 9.

Constraints

• 1 \leq X \leq 15
• 0 \leq Y \leq 9
• X and Y are integers.

Sample Input 1

15.8

Sample Output 1

15+

Here, printing 15 + will not be accepted: do not print a space between X and +, or between X and -.

Sample Input 2

1.0

Sample Output 2

1-

You will not get inputs such as 1.00 and 1.

Sample Input 3

12.5

Sample Output 3

12

Problem Statement

You are given positive integers A and B.
Print the value A^B+B^A.

Constraints

• 2 \leq A \leq B \leq 9
• All input values are integers.

Sample Input 1

2 8

Sample Output 1

320

For A = 2, B = 8, we have A^B = 256, B^A = 64, so A^B + B^A = 320.

Sample Input 2

9 9

Sample Output 2

774840978

Sample Input 3

5 6

Sample Output 3

23401

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

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

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

Sample Output 3

-1

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

• 1 \leq N \leq 10^4
• 1 \leq M \leq 7
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.

Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.

Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes

Problem Statement

There is a tree T with N vertices. The i-th edge (1\leq i\leq N-1) connects vertex U_i and vertex V_i.

You are given two different vertices X and Y in T. List all vertices along the simple path from vertex X to vertex Y in order, including endpoints.

It can be proved that, for any two different vertices a and b in a tree, there is a unique simple path from a to b.

Constraints

• 1\leq N\leq 2\times 10^5
• 1\leq X,Y\leq N
• X\neq Y
• 1\leq U_i,V_i\leq N
• All values in the input are integers.
• The given graph is a tree.

Sample Input 1

5 2 5
1 2
1 3
3 4
3 5

Sample Output 1

2 1 3 5

The tree T is shown below. The simple path from vertex 2 to vertex 5 is 2 \to 1 \to 3 \to 5.
Thus, 2,1,3,5 should be printed in this order, with spaces in between.

Sample Input 2

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

Sample Output 2

1 2

The tree T is shown below.

Problem Statement

There is a H \times W-square grid with H horizontal rows and W vertical columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.
Each square is described by a character C_{i, j}, where C_{i, j} = . means (i, j) is an empty square, and C_{i, j} = # means (i, j) is a wall.

Takahashi is about to start walking in this grid. When he is on (i, j), he can go to (i, j + 1) or (i + 1, j). However, he cannot exit the grid or enter a wall square. He will stop when there is no more square to go to.

When starting on (1, 1), at most how many squares can Takahashi visit before he stops?

Constraints

• 1 \leq H, W \leq 100
• H and W are integers.
• C_{i, j} = . or C_{i, j} = #. (1 \leq i \leq H, 1 \leq j \leq W)
• C_{1, 1} = .

Sample Input 1

3 4
.#..
..#.
..##

Sample Output 1

4

For example, by going (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2), he can visit 4 squares.

He cannot visit 5 or more squares, so we should print 4.

Sample Input 2

1 1
.

Sample Output 2

1

Sample Input 3

5 5
.....
.....
.....
.....
.....

Sample Output 3

9

Problem Statement

Given is a string S consisting of K, E, Y.

How many strings are there that can be obtained with at most K swaps of two adjacent characters in S?

Constraints

• 2 \leq |S| \leq 30
• 0 \leq K \leq 10^9
• S consists of K, E, Y.

Sample Input 1

KEY
1

Sample Output 1

3

With at most one swap, there are three strings that can be obtained: KEY, EKY, KYE.

Sample Input 2

KKEE
2

Sample Output 2

4

With at most two swaps, there are four strings that can be obtained: KKEE, KEKE, EKKE, KEEK.

Sample Input 3

KKEEYY
1000000000

Sample Output 3

90

Problem Statement

You are given a string S of length N consisting of 0 and 1. Let S_i denote the i-th character of S.

Process Q queries in the order they are given.
Each query is represented by a tuple of three integers (c, L, R), where c represents the type of the query.

• When c=1: For each integer i such that L \leq i \leq R, if S_i is 1, change it to 0; if it is 0, change it to 1.
• When c=2: Let T be the string obtained by extracting the L-th through R-th characters of S. Print the maximum number of consecutive 1s in T.

Constraints

• 1 \leq N \leq 5 \times 10^5
• 1 \leq Q \leq 10^5
• S is a string of length N consisting of 0 and 1.
• c \in \lbrace 1, 2 \rbrace
• 1 \leq L \leq R \leq N
• N, Q, c, L, and R are all integers.

Sample Input 1

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

Sample Output 1

3
1
0
7

The queries are processed as follows.

• Initially, S= 1101110.
• For the first query, T = 1101110. The longest sequence of consecutive 1s in T is 111 from the 4-th character to 6-th character, so the answer is 3.
• For the second query, T = 101. The longest sequence of consecutive 1s in T is 1 at the 1-st or 3-rd character, so the answer is 1.
• For the third query, the operation changes S to 1110000.
• For the fourth query, T = 00. T does not contain 1, so the answer is 0.
• For the fifth query, the operation changes S to 1111111.
• For the sixth query, T = 1111111. The longest sequence of consecutive 1s in T is 1111111 from the 1-st to 7-th characters, so the answer is 7.