Problem Statement

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

Uppercase each character of S and print the resulting string T.

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

abc

Sample Output 1

ABC

Uppercase each character of abc, and you have ABC.

Sample Input 2

a

Sample Output 2

A

Sample Input 3

abcdefghjiklnmoqprstvuwxyz

Sample Output 3

ABCDEFGHJIKLNMOQPRSTVUWXYZ

Problem Statement

You are given integers A and B between 0 and 255 (inclusive). Find a non-negative integer C such that A \text{ xor }C=B.

It can be proved that there uniquely exists such C, and it will be between 0 and 255 (inclusive).

Constraints

• 0\leq A,B \leq 255
• All values in input are integers.

Sample Input 1

3 6

Sample Output 1

5

When written in binary, 3 will be 11, and 5 will be 101. Thus, their \text{xor} will be 110 in binary, or 6 in decimal.

In short, 3 \text{ xor } 5 = 6, so the answer is 5.

Sample Input 2

10 12

Sample Output 2

6

Problem Statement

N players played a round-robin tournament.

You are given an N-by-N table A containing the results of the matches. Let A_{i,j} denote the element at the i-th row and j-th column of A.
A_{i,j} is - if i=j, and W, L, or D otherwise.
A_{i,j} is W if Player i beat Player j, L if Player i lost to Player j, and D if Player i drew with Player j.

Determine whether the given table is contradictory.

The table is said to be contradictory when some of the following holds:

• There is a pair (i,j) such that Player i beat Player j, but Player j did not lose to Player i;
• There is a pair (i,j) such that Player i lost to Player j, but Player j did not beat Player i;
• There is a pair (i,j) such that Player i drew with Player j, but Player j did not draw with Player i.

Constraints

• 2 \leq N \leq 1000
• A_{i,i} is -.
• A_{i,j} is W, L, or D, for i\neq j.

Sample Input 1

4
-WWW
L-DD
LD-W
LDW-

Sample Output 1

incorrect

Player 3 beat Player 4, while Player 4 also beat Player 3, which is contradictory.

Sample Input 2

2
-D
D-

Sample Output 2

correct

There is no contradiction.

Problem Statement

I begin with T and end with T, and I am full of T. What am I?

For a string t, define the filling rate as follows:

• If the first and last characters of t are both t and |t| \geq 3: Let x be the number of t in t. Then the filling rate of t is \displaystyle\frac{x-2}{|t|-2}, where |t| denotes the length of t.
• Otherwise: the filling rate of t is 0.

You are given a string S. Find the maximum possible filling rate of a substring of S.

Constraints

• 1 \leq |S| \leq 100
• S is a string consisting of lowercase English letters.

Sample Input 1

attitude

Sample Output 1

0.50000000000000000

ttit is a substring of S, and its filling rate is \displaystyle\frac{3-2}{4-2} = \frac{1}{2}.

There is no substring with a filling rate greater than \frac{1}{2}, so the answer is \frac{1}{2}.

Sample Input 2

ottottott

Sample Output 2

0.66666666666666667

ttottott is a substring of S, and its filling rate is \displaystyle\frac{6-2}{8-2} = \frac{2}{3}.

There is no substring with a filling rate greater than \frac{2}{3}, so the answer is \frac{2}{3}.

Sample Input 3

coffeecup

Sample Output 3

0.00000000000000000

ff is a substring of S, and its filling rate is 0.

There is no substring with a filling rate greater than 0, so the answer is 0.

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1, 2, \dots, N, and the edges are numbered 1, 2, \dots, M.
Edge i \, (i = 1, 2, \dots, M) connects vertices u_i and v_i.

Determine if this graph is a path graph.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 0 \leq M \leq 2 \times 10^5
• 1 \leq u_i, v_i \leq N \, (i = 1, 2, \dots, M)
• All values in the input are integers.
• The graph given in the input is simple.

Sample Input 1

4 3
1 3
4 2
3 2

Sample Output 1

Yes

Illustrated below is the given graph, which is a path graph.

Sample Input 2

2 0

Sample Output 2

No

Illustrated below is the given graph, which is not a path graph.

Sample Input 3

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

Sample Output 3

No

Illustrated below is the given graph, which is not a path graph.

Problem Statement

There is an N \times N grid, where the cell at the i-th row from the top and the j-th column from the left contains the integer N \times (i-1) + j.

Over T turns, integers will be announced. On Turn i, the integer A_i is announced, and the cell containing A_i is marked. Determine the turn on which Bingo is achieved for the first time. If Bingo is not achieved within T turns, print -1.

Here, achieving Bingo means satisfying at least one of the following conditions:

• There exists a row in which all N cells are marked.
• There exists a column in which all N cells are marked.
• There exists a diagonal line (from top-left to bottom-right or from top-right to bottom-left) in which all N cells are marked.

Constraints

• 2 \leq N \leq 2 \times 10^3
• 1 \leq T \leq \min(N^2, 2 \times 10^5)
• 1 \leq A_i \leq N^2
• A_i \neq A_j if i \neq j.
• All input values are integers.

Sample Input 1

3 5
5 1 8 9 7

Sample Output 1

4

The state of the grid changes as follows. Bingo is achieved for the first time on Turn 4.

Sample Input 2

3 5
4 2 9 7 5

Sample Output 2

-1

Bingo is not achieved within five turns, so print -1.

Sample Input 3

4 12
13 9 6 5 2 7 16 14 8 3 10 11

Sample Output 3

9

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and M edges, and eight pieces.

The nine vertices of the graph are called Vertex 1, Vertex 2, \ldots, Vertex 9. For each i = 1, 2, \ldots, M, the i-th edge connects Vertex u_i and Vertex v_i.
The eight pieces are called Piece 1, Piece 2, \ldots, Piece 8. For each j = 1, 2, \ldots, 8, Piece j is on Vertex p_j.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

• For each j = 1, 2, \ldots, 8, Piece j is on Vertex j.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

• 0 \leq M \leq 36
• 1 \leq u_i, v_i \leq 9
• The given graph has no multi-edges or self-loops.
• 1 \leq p_j \leq 9
• j \neq j' \Rightarrow p_j \neq p_{j'}
• All values in input are integers.

Sample Input 1

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

Sample Output 1

5

The following procedure completes the puzzle in five operations.

1. Move Piece 2 from Vertex 9 to Vertex 1.
2. Move Piece 3 from Vertex 2 to Vertex 9.
3. Move Piece 2 from Vertex 1 to Vertex 2.
4. Move Piece 1 from Vertex 3 to Vertex 1.
5. Move Piece 3 from Vertex 9 to Vertex 3.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print 5.
Note that the given graph may not be connected.

Sample Input 2

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

Sample Output 2

0

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is 0.

Sample Input 3

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

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print -1.

Sample Input 4

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

Sample Output 4

16

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

• 2 \leq N,M \leq 10^6
• N and M are integers.

Sample Input 1

3 3

Sample Output 1

6

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

Problem Statement

There is a grid with H rows and W columns. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

There are N horizontal bars numbered from 1 to N placed on the grid. Bar i consists of L_i blocks of size 1 \times 1 connected horizontally, and its leftmost block is initially at cell (R_i, C_i). That is, initially, bar i occupies the cells (R_i, C_i), (R_i, C_i + 1), \dots, (R_i, C_i + L_i - 1). It is guaranteed that there is no cell occupied by two different bars.

The current time is t = 0. At every time t = 0.5 + n for some non-negative integer n, the following occurs in order of i = 1, 2, \dots, N:

• If bar i is not on the bottom row (the H-th row), and none of the cells directly below the cells occupied by bar i is occupied by any bar, then bar i moves down by one cell. That is, if at that time bar i occupies the cells (r,C_i),(r,C_i+1),\dots,(r,C_i+L_i-1)\ (r < H), and the cell (r + 1, C_i + j) is not occupied by any bar for all j (0 \leq j \leq L_i - 1), then bar i now occupies (r + 1, C_i), (r + 1, C_i + 1), \dots, (r + 1, C_i + L_i - 1).
• Otherwise, nothing happens.

Let (R'_i, C_i), (R'_i, C_i + 1), \dots, (R'_i, C_i + L_i - 1) be the cells occupied by bar i at time t = 10^{100}. Find R'_1, R'_2, \dots, R'_N.

Constraints

• 1 \leq H, W \leq 2 \times 10^5
• 1 \leq N \leq 2 \times 10^5
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W
• 1 \leq L_i \leq W - C_i + 1
• In the initial state, there is no cell occupied by two different bars.
• All input values are integers.

Sample Input 1

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

Sample Output 1

2
4
3
4

The following three diagrams represent the grid at times t = 0, 1, and 2 from left to right. Colored rectangles represent the bars, and the number inside each rectangle indicates its bar number.

The changes in the grid state are explained as follows:

• At t = 0.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4). Among these, (2,2) is occupied by bar 3 and (2,4) is occupied by bar 4, so nothing happens.
  • i = 2: The cells directly below bar 2 are (4,2),(4,3), which are not occupied by any other bar, so bar 2 moves down by one cell.
  • i = 3: The cells directly below bar 3 are (3,1),(3,2), which are not occupied by any other bar, so bar 3 moves down by one cell.
  • i = 4: The cell directly below bar 4 is (3,4), which is not occupied by any other bar, so bar 4 moves down by one cell.
• At t = 1.5:
  • i = 1: The cells directly below bar 1 are (2,2),(2,3),(2,4), which are not occupied by any other bar, so bar 1 moves down by one cell.
  • i = 2: Bar 2 is on the bottom row, so nothing happens.
  • i = 3: The cells directly below bar 3 are (4,1),(4,2). Among these, (4,2) is occupied by bar 2, so nothing happens.
  • i = 4: The cell directly below bar 4 is (4,4), which is not occupied by any other bar, so bar 4 moves down by one cell.

At times t = 2.5, 3.5, \dots, there is no bar such that the cells directly below it are all unoccupied, so nothing happens. Thus, the grid at time t = 10^{100} is the same as at t = 2 (the rightmost diagram above).

Therefore, R'_1 = 2, R'_2 = 4, R'_3 = 3, R'_4 = 4.

Sample Input 2

382 382 3
3 3 3
8 8 8
2 2 2

Sample Output 2

382
382
381

Sample Input 3

5 10 8
2 2 1
4 3 1
4 8 2
1 2 2
2 5 3
5 4 3
4 5 2
1 5 2

Sample Output 3

5
5
5
4
3
5
4
2