Problem Statement

You are given positive integers N, L, and R.
For a sequence A = (1, 2, \dots, N) of length N, an operation of reversing the L-th through R-th elements was performed once.
Print the sequence after this operation.

Constraints

• All input values are integers.
• 1 \leq L \leq R \leq N \leq 100

Sample Input 1

5 2 3

Sample Output 1

1 3 2 4 5

Initially, A = (1, 2, 3, 4, 5).
After reversing the second through third elements, the sequence becomes (1, 3, 2, 4, 5), which should be printed.

Sample Input 2

7 1 1

Sample Output 2

1 2 3 4 5 6 7

It is possible that L = R.

Sample Input 3

10 1 10

Sample Output 3

10 9 8 7 6 5 4 3 2 1

It is possible that L = 1 or R = N.

Problem Statement

Given a string S, print AC if it perfectly matches Hello,World!; otherwise, print WA.

Constraints

• 1 \le |S| \le 15
• S consists of English lowercase letters, English uppercase letters, ,, and !.

Sample Input 1

Hello,World!

Sample Output 1

AC

The string S perfectly matches Hello,World!.

Sample Input 2

Hello,world!

Sample Output 2

WA

The seventh character from the beginning should be an uppercase W in Hello,World!, but S has a lowercase w in that position. Thus, S does not match Hello,World!.

Sample Input 3

Hello!World!

Sample Output 3

WA

Problem Statement

Given an integer X between -10^{18} and 10^{18}, inclusive, print \left\lceil \dfrac{X}{10} \right\rceil.
Here, \left\lceil a \right\rceil denotes the smallest integer not less than a.

Constraints

• -10^{18} \leq X \leq 10^{18}
• X is an integer.

Sample Input 1

27

Sample Output 1

3

The integers not less than \frac{27}{10} = 2.7 are 3, 4, 5, \dots. Among these, the smallest is 3, so \left \lceil \frac{27}{10} \right \rceil = 3.

Sample Input 2

-13

Sample Output 2

-1

The integers not less than \frac{-13}{10} = -1.3 are all positive integers, 0, and -1. Among these, the smallest is -1, so \left \lceil \frac{-13}{10} \right \rceil = -1.

Sample Input 3

40

Sample Output 3

4

The smallest integer not less than \frac{40}{10} = 4 is 4 itself.

Sample Input 4

-20

Sample Output 4

-2

Sample Input 5

123456789123456789

Sample Output 5

12345678912345679

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

• 1 \leq i \lt j \leq N
• \min(a_i, a_j) = i
• \max(a_i, a_j) = j

Constraints

• 2 \leq N \leq 5 \times 10^5
• 1 \leq a_i \leq N \, (1 \leq i \leq N)
• All values in input are integers.

Sample Input 1

4
1 3 2 4

Sample Output 1

2

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

8

Problem Statement

There is a grid with 10^9 rows and 10^9 columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left.

There are N people on the grid. Initially, the i-th person is at square (R_i, C_i).

The time starts at 0. Each person can do the following move at times 1, 2, 3, 4, \ldots.

• Stay at the current position, or move to an 8-adjacent square. It is forbidden to leave the grid. Formally, let square (i, j) be the current square, and move to one of the squares (i - 1, j - 1), (i - 1, j), (i - 1, j + 1), (i, j - 1), (i, j), (i, j + 1), (i + 1, j - 1), (i + 1, j), (i + 1, j + 1) that exists. Assume that the move takes no time.

Find the minimum possible time when the N people are at the same square.

Constraints

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

Sample Input 1

3
2 3
5 1
8 1

Sample Output 1

3

All people will be at square (5, 4) at time 3 if each person moves as follows.

• At time 1, the 1st person moves to square (3, 4), the 2nd person moves to square (6, 2), and the 3rd person moves to square (7, 2).

• At time 2, the 1st person moves to square (4, 4), the 2nd person moves to square (5, 3), and the 3rd person moves to square (6, 3).

• At time 3, the 1st person moves to square (5, 4), the 2nd person moves to square (5, 4), and the 3rd person moves to square (5, 4).

Sample Input 2

5
6 7
6 7
6 7
6 7
6 7

Sample Output 2

0

All people start at the same square.

Sample Input 3

6
91 999999986
53 999999997
32 999999932
14 999999909
49 999999985
28 999999926

Sample Output 3

44

Problem Statement

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

A length-K sequence of indices (i_1, i_2, \dots, i_K) is called a good index sequence if it satisfies both of the following conditions:

• 1 \leq i_1 < i_2 < \dots < i_K \leq N.
• The subsequence (P_{i_1}, P_{i_2}, \dots, P_{i_K}) can be obtained by rearranging some consecutive K integers.
  Formally, there exists an integer a such that \lbrace P_{i_1},P_{i_2},\dots,P_{i_K} \rbrace = \lbrace a,a+1,\dots,a+K-1 \rbrace.

Find the minimum value of i_K - i_1 among all good index sequences. It can be shown that at least one good index sequence exists under the constraints of this problem.

Constraints

• 1 \leq K \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_i \neq P_j if i \neq j.
• All input values are integers.

Sample Input 1

4 2
2 3 1 4

Sample Output 1

1

The good index sequences are (1,2),(1,3),(2,4). For example, (i_1, i_2) = (1,3) is a good index sequence because 1 \leq i_1 < i_2 \leq N and (P_{i_1}, P_{i_2}) = (2,1) is a rearrangement of two consecutive integers 1, 2.

Among these good index sequences, the smallest value of i_K - i_1 is for (1,2), which is 2-1=1.

Sample Input 2

4 1
2 3 1 4

Sample Output 2

0

i_K - i_1 = i_1 - i_1 = 0 in all good index sequences.

Sample Input 3

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

Sample Output 3

5

Problem Statement

A positive integer N is a 400 number if and only if it satisfies both of the following two conditions:

• N has exactly 2 distinct prime factors.
• For each prime factor p of N, p divides N an even number of times. More formally, the maximum non-negative integer k such that p^k divides N is even.

Process Q queries. Each query gives you an integer A, so find the largest 400 number not exceeding A. Under the constraints of this problem, a 400 number not exceeding A always exists.

Constraints

• 1 \leq Q \leq 2 \times 10^5
• For each query, 36 \leq A \leq 10^{12}.
• All input values are integers.

Sample Input 1

5
404
36
60
1000000000000
123456789

Sample Output 1

400
36
36
1000000000000
123454321

Let us explain the first query.

There are exactly 2 prime factors of 400: 2 and 5. Also, 2 divides 400 four times and 5 divides it twice, so 400 is a 400 number. None of 401, 402, 403, and 404 is a 400 number, so the answer is 400.

Problem Statement

On a blackboard, there are N sets S_1,S_2,\dots,S_N consisting of integers between 1 and M. Here, S_i = \lbrace S_{i,1},S_{i,2},\dots,S_{i,A_i} \rbrace.

You may perform the following operation any number of times (possibly zero):

• choose two sets X and Y with at least one common element. Erase them from the blackboard, and write X\cup Y on the blackboard instead.

Here, X\cup Y denotes the set consisting of the elements contained in at least one of X and Y.

Determine if one can obtain a set containing both 1 and M. If it is possible, find the minimum number of operations required to obtain it.

Constraints

• 1 \le N \le 2 \times 10^5
• 2 \le M \le 2 \times 10^5
• 1 \le \sum_{i=1}^{N} A_i \le 5 \times 10^5
• 1 \le S_{i,j} \le M(1 \le i \le N,1 \le j \le A_i)
• S_{i,j} \neq S_{i,k}(1 \le j < k \le A_i)
• All values in the input are integers.

Sample Input 1

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

Sample Output 1

2

First, choose and remove \lbrace 1,2 \rbrace and \lbrace 2,3 \rbrace to obtain \lbrace 1,2,3 \rbrace.

Then, choose and remove \lbrace 1,2,3 \rbrace and \lbrace 3,4,5 \rbrace to obtain \lbrace 1,2,3,4,5 \rbrace.

Thus, one can obtain a set containing both 1 and M with two operations. Since one cannot achieve the objective by performing the operation only once, the answer is 2.

Sample Input 2

1 2
2
1 2

Sample Output 2

0

S_1 already contains both 1 and M, so the minimum number of operations required is 0.

Sample Input 3

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

Sample Output 3

-1

Sample Input 4

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

Sample Output 4

2