Problem Statement

Takahashi is in a building with 100 floors.

He uses the stairs for moving up two floors or less or moving down three floors or less, and uses the elevator otherwise.

Does he use the stairs to move from floor X to floor Y?

Constraints

• 1 \leq X,Y \leq 100
• X \neq Y
• All input values are integers.

Sample Input 1

1 4

Sample Output 1

No

The move from floor 1 to floor 4 involves going up three floors, so Takahashi uses the elevator.

Sample Input 2

99 96

Sample Output 2

Yes

The move from floor 99 to floor 96 involves going down three floors, so Takahashi uses the stairs.

Sample Input 3

100 1

Sample Output 3

No

Problem Statement

There are N bridges in AtCoder Village. The height of the bridge numbered i is H_i (i is an integer between 1 and N).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

• 1\leq N \leq 100
• 1\leq H_i \leq 10^9
• All H_i are different.
• All values in the input are integers.

Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of 50, 80, and 70, respectively, so the second bridge is the highest.
Thus, 2 should be printed.

Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.

Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of 97) is the highest.

Problem Statement

You are given a horizontally written text. Convert it to vertical writing, filling spaces with *.

You are given N strings S_1, S_2, \dots, S_N consisting of lowercase English letters. Let M be the maximum length of these strings.

Print M strings T_1, T_2, \dots, T_M that satisfy the following conditions:

• Each T_i consists of lowercase English letters and *.
• Each T_i does not end with *.
• For each 1 \leq i \leq N, the following holds:
  • For each 1 \leq j \leq |S_i|, the (N-i+1)-th character of T_j exists, and the concatenation of the (N-i+1)-th characters of T_1, T_2, \dots, T_{|S_i|} in this order equals S_i.
  • For each |S_i| + 1 \leq j \leq M, the (N-i+1)-th character of T_j either does not exist or is *.

Here, |S_i| denotes the length of the string S_i.

Constraints

• N is an integer between 1 and 100, inclusive.
• Each S_i is a string of lowercase English letters with length between 1 and 100, inclusive.

Sample Input 1

3
abc
de
fghi

Sample Output 1

fda
geb
h*c
i

Placing * as the 2nd character of T_3 puts the c in the correct position. On the other hand, placing * as the 2nd and 3rd characters of T_4 would make T_4 end with *, which violates the condition.

Sample Input 2

3
atcoder
beginner
contest

Sample Output 2

cba
oet
ngc
tio
end
sne
ter
*r

Problem Statement

You are given strings S and T consisting of lowercase English letters. Determine whether T is a (contiguous) substring of S.

A string Y is said to be a (contiguous) substring of X if and only if Y can be obtained by performing the operation below on X zero or more times.

• Do one of the following.
  • Delete the first character in X.
  • Delete the last character in X.

For instance, tag is a (contiguous) substring of voltage, while ace is not a (contiguous) substring of atcoder.

Constraints

• S and T consist of lowercase English letters.
• 1 \le |S|,|T| \le 100 (|X| denotes the length of a string X.)

Sample Input 1

voltage
tag

Sample Output 1

Yes

tag is a (contiguous) substring of voltage.

Sample Input 2

atcoder
ace

Sample Output 2

No

ace is not a (contiguous) substring of atcoder.

Sample Input 3

gorilla
gorillagorillagorilla

Sample Output 3

No

Sample Input 4

toyotasystems
toyotasystems

Sample Output 4

Yes

It is possible that S=T.

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

• L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
• \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

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

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9

Problem Statement

There are N buildings arranged in a line at equal intervals. The height of the i-th building from the front is H_i.

You want to decorate some of these buildings with illuminations so that both of the following conditions are satisfied:

• The chosen buildings all have the same height.
• The chosen buildings are arranged at equal intervals.

What is the maximum number of buildings you can choose? If you choose exactly one building, it is considered to satisfy the conditions.

Constraints

• 1 \leq N \leq 3000
• 1 \leq H_i \leq 3000
• All input values are integers.

Sample Input 1

8
5 7 5 7 7 5 7 7

Sample Output 1

3

Choosing the 2nd, 5th, and 8th buildings from the front satisfies the conditions.

Sample Input 2

10
100 200 300 400 500 600 700 800 900 1000

Sample Output 2

1

Choosing just one building is considered to satisfy the conditions.

Sample Input 3

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

Sample Output 3

3

Problem Statement

For a positive integer N, let V_N be the integer formed by concatenating N exactly N times.
More precisely, consider N as a string, concatenate N copies of it, and treat the result as an integer to get V_N.
For example, V_3=333 and V_{10}=10101010101010101010.

Find the remainder when V_N is divided by 998244353.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

5

Sample Output 1

55555

The remainder when V_5=55555 is divided by 998244353 is 55555.

Sample Input 2

9

Sample Output 2

1755646

The remainder when V_9=999999999 is divided by 998244353 is 1755646.

Sample Input 3

10000000000

Sample Output 3

468086693

Note that the input may not fit into a 32-bit integer type.

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

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

Sample Input 1

3
3 1 4

Sample Output 1

8

The sought value is

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8.

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

53

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

592622

Problem Statement

You are given a tree T with N vertices. The vertices are numbered from 0 to N-1, and the i-th edge (1\le i\le N-1) bidirectionally connects vertices u_i and v_i. (Note that vertex numbers are 0-indexed and edge numbers are 1-indexed.)

For a pair of integers (i,j) where 0 \leq i,j < N, define f(i,j) as follows:

• The vertex number of the vertex with the smallest number among the vertices not included in the path from vertex i to vertex j in tree T.
  • Here, if the path from vertex i to vertex j includes all vertices from vertex 0 to vertex N-1, let f(i,j)=N.

Note that the path from vertex i to vertex j in tree T includes vertices i and j.

Find the value of \displaystyle \sum_{0\le i \le j < N} f(i,j).

Constraints

• 2\le N\le 2\times 10^5
• 0\le u_i < v_i < N
• The graph given in the input is a tree.
• All input values are integers.

Sample Input 1

2
0 1

Sample Output 1

3

We have f(0,0)=1,f(0,1)=2,f(1,1)=0. Thus, output 1+2+0=3.

Sample Input 2

5
0 1
0 2
2 3
2 4

Sample Output 2

16

Sample Input 3

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

Sample Output 3

16