Problem Statement

You are given a real number X, which is representable using at most three decimal digits, with three decimal digits.
Round X to the nearest integer and print the result.

Constraints

• 0 \leq X < 100
• X is representable using at most three decimal digits.
• X has three decimal digits in input.

Sample Input 1

3.456

Sample Output 1

3

The digit in the first decimal place of 3.456 is 4, so we should round it down to 3.

Sample Input 2

99.500

Sample Output 2

100

Sample Input 3

0.000

Sample Output 3

0

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

Let us call a string consisting of uppercase and lowercase English alphabets a wonderful string if all of the following conditions are satisfied:

• The string contains an uppercase English alphabet.
• The string contains a lowercase English alphabet.
• All characters in the string are pairwise distinct.

For example, AtCoder and Aa are wonderful strings, while atcoder and Perfect are not.

Given a string S, determine if S is a wonderful string.

Constraints

• 1 \le |S| \le 100
• S is a string consisting of uppercase and lowercase English alphabets.

Sample Input 1

AtCoder

Sample Output 1

Yes

AtCoder is a wonderful string because it contains an uppercase English alphabet, a lowercase English alphabet, and all characters in the string are pairwise distinct.

Sample Input 2

Aa

Sample Output 2

Yes

Note that A and a are different characters. This string is a wonderful string.

Sample Input 3

atcoder

Sample Output 3

No

It is not a wonderful string because it does not contain an uppercase English alphabet.

Sample Input 4

Perfect

Sample Output 4

No

It is not a wonderful string because the 2-nd and the 5-th characters are the same.

Problem Statement

You are given a 4-digit PIN: X_1X_2X_3X_4, which may begin with a 0. The PIN is said to be weak when it satisfies one of the following conditions:

• All of the four digits are the same.
• For each integer i such that 1\leq i\leq 3, X_{i+1} follows X_i. Here, j+1 follows j for each 0\leq j\leq 8, and 0 follows 9.

If the given PIN is weak, print Weak; otherwise, print Strong.

Constraints

• 0 \leq X_1, X_2, X_3, X_4 \leq 9
• X_1, X_2, X_3, and X_4 are integers.

Sample Input 1

7777

Sample Output 1

Weak

All four digits are 7, satisfying the first condition, so this PIN is weak.

Sample Input 2

0112

Sample Output 2

Strong

The first and second digits differ, and the third digit does not follow the second digit, so neither condition is satisfied.

Sample Input 3

9012

Sample Output 3

Weak

Note that 0 follows 9.

Problem Statement

You are given a permutation P = (P_1, \dots, P_N) of (1, \dots, N), where (P_1, \dots, P_N) \neq (1, \dots, N).

Assume that P is the K-th lexicographically smallest among all permutations of (1 \dots, N). Find the (K-1)-th lexicographically smallest permutation.

Constraints

• 2 \leq N \leq 100
• 1 \leq P_i \leq N \, (1 \leq i \leq N)
• P_i \neq P_j \, (i \neq j)
• (P_1, \dots, P_N) \neq (1, \dots, N)
• All values in the input are integers.

Sample Input 1

3
3 1 2

Sample Output 1

2 3 1

Here are the permutations of (1, 2, 3) in ascending lexicographical order.

• (1, 2, 3)
• (1, 3, 2)
• (2, 1, 3)
• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Therefore, P = (3, 1, 2) is the fifth smallest, so the sought permutation, which is the fourth smallest (5 - 1 = 4), is (2, 3, 1).

Sample Input 2

10
9 8 6 5 10 3 1 2 4 7

Sample Output 2

9 8 6 5 10 2 7 4 3 1

Problem Statement

Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.

The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.

Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.

1. Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
2. Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.

Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.

• The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
• The cut-out sheet coincides sheet X without rotating or flipping.

Constraints

• 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
• H_A, W_A, H_B, W_B, H_X, W_X are integers.
• A_i is a string of length W_A consisting of . and #.
• B_i is a string of length W_B consisting of . and #.
• X_i is a string of length W_X consisting of . and #.
• Sheets A, B, and X each contain at least one black square.

Sample Input 1

3 5
#.#..
.....
.#...
2 2
#.
.#
5 3
...
#.#
.#.
.#.
...

Sample Output 1

Yes

First, paste sheet A onto sheet C, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots.......\cdots
  ..#....  
  .......  
     \vdots

Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.

     \vdots
  .......  
  .#.#...  
\cdots..#....\cdots
  ..#....  
  .......  
     \vdots

Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.

...
#.#
.#.
.#.
...

This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.

Therefore, print Yes.

Sample Input 2

2 2
#.
.#
2 2
#.
.#
2 2
##
##

Sample Output 2

No

Note that sheets A and B may not be rotated or flipped when pasting them.

Sample Input 3

1 1
#
1 2
##
1 1
#

Sample Output 3

No

No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition. Therefore, print No.

Sample Input 4

3 3
###
...
...
3 3
#..
#..
#..
3 3
..#
..#
###

Sample Output 4

Yes

Problem Statement

For positive integers x and y, define f(x, y) as follows:

• Interpret the decimal representations of x and y as strings and concatenate them in this order to obtain a string z. The value of f(x, y) is the value of z when interpreted as a decimal integer.

For example, f(3, 14) = 314 and f(100, 1) = 1001.

You are given a sequence of positive integers A = (A_1, \ldots, A_N) of length N. Find the value of the following expression modulo 998244353:

Constraints

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

Sample Input 1

3
3 14 15

Sample Output 1

2044

• f(A_1, A_2) = 314
• f(A_1, A_3) = 315
• f(A_2, A_3) = 1415

Thus, the answer is f(A_1, A_2) + f(A_1, A_3) + f(A_2, A_3) = 2044.

Sample Input 2

5
1001 5 1000000 1000000000 100000

Sample Output 2

625549048

Be sure to calculate the value modulo 998244353.

Problem Statement

You are given N strings consisting of lowercase English letters. Let S_i be the i-th (i = 1, 2, \dots, N) of them.

For two strings x and y, \mathrm{LCP}(x, y) is defined to be the maximum integer n that satisfies all of the following conditions:

• The lengths of x and y are both at least n.
• For all integers i between 1 and n, inclusive, the i-th character of x and that of y are equal.

Find the following value for all i = 1, 2, \dots, N:

• \displaystyle \max_{i \neq j} \mathrm{LCP}(S_i, S_j)

Constraints

• 2 \leq N \leq 5 \times 10^5
• N is an integer.
• S_i is a string of length at least 1 consisting of lowercase English letters (i = 1, 2, \dots, N).
• The sum of lengths of S_i is at most 5 \times 10^5.

Sample Input 1

3
abc
abb
aac

Sample Output 1

2
2
1

\mathrm{LCP}(S_1, S_2) = 2, \mathrm{LCP}(S_1, S_3) = 1, and \mathrm{LCP}(S_2, S_3) = 1.

Sample Input 2

11
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a

Sample Output 2

4
3
2
1
0
1
0
4
3
2
1

Problem Statement

Given are N distinct points in a two-dimensional plane. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).

Let us define the distance between two points i and j be \mathrm{min} (|x_i-x_j|,|y_i-y_j|): the smaller of the difference in the x-coordinates and the difference in the y-coordinates.

Find the maximum distance between two different points.

Constraints

• 2 \leq N \leq 200000
• 0 \leq x_i,y_i \leq 10^9
• (x_i,y_i) \neq (x_j,y_j) (i \neq j)
• All values in input are integers.

Sample Input 1

3
0 3
3 1
4 10

Sample Output 1

4

The distances between Points 1 and 2, between Points 1 and 3, and between Points 2 and 3 are 2, 4, and 1, respectively, so your output should be 4.

Sample Input 2

4
0 1
0 4
0 10
0 6

Sample Output 2

0

Sample Input 3

8
897 729
802 969
765 184
992 887
1 104
521 641
220 909
380 378

Sample Output 3

801