Problem Statement

You are given a string S of length 3.
Print a character that occurs only once in S.
If there is no such character, print -1 instead.

Constraints

• S is a string of length 3 consisting of lowercase English letters.

Sample Input 1

pop

Sample Output 1

o

o occurs only once in pop.

Sample Input 2

abc

Sample Output 2

a

a, b, and c occur once each in abc, so you may print any of them.

Sample Input 3

xxx

Sample Output 3

-1

No character occurs only once in xxx.

Problem Statement

For a positive integer X, the Dragon String of level X is a string of length (X+3) formed by one L, X occurrences of o, one n, and one g arranged in this order.

You are given a positive integer N. Print the Dragon String of level N.
Note that uppercase and lowercase letters are distinguished.

Constraints

• 1 \leq N \leq 2024
• N is an integer.

Sample Input 1

3

Sample Output 1

Looong

Arranging one L, three os, one n, and one g in this order yields Looong.

Sample Input 2

1

Sample Output 2

Long

Problem Statement

N players, who are numbered 1, \ldots, N, have played a game. Player i has scored A_i, and a player with a smaller score ranks higher.

The player who ranks the second lowest will receive a booby prize. Who is this player? Answer with an integer representing the player.

Constraints

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

Sample Input 1

6
1 123 12345 12 1234 123456

Sample Output 1

3

It is Player 3 who ranks fifth among the six players.

Sample Input 2

5
3 1 4 15 9

Sample Output 2

5

Problem Statement

Takahashi is health-conscious and concerned about whether he is getting enough of M types of nutrients from his diet.

For the i-th nutrient, his goal is to take at least A_i units per day.

Today, he ate N foods, and from the i-th food, he took X_{i,j} units of nutrient j.

Determine whether he has met the goal for all M types of nutrients.

Constraints

• 1 \leq N \leq 100
• 1 \leq M \leq 100
• 0 \leq A_i, X_{i,j} \leq 10^7
• All input values are integers.

Sample Input 1

2 3
10 20 30
20 0 10
0 100 100

Sample Output 1

Yes

For nutrient 1, Takahashi took 20 units from the 1-st food and 0 units from the 2-nd food, totaling 20 units, thus meeting the goal of taking at least 10 units.
Similarly, he meets the goal for nutrients 2 and 3.

Sample Input 2

2 4
10 20 30 40
20 0 10 30
0 100 100 0

Sample Output 2

No

The goal is not met for nutrient 4.

Problem Statement

For positive integers x and y, define f(x, y) as the remainder of (x + y) divided by 10^8.

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

Constraints

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

Sample Input 1

3
3 50000001 50000002

Sample Output 1

100000012

• f(A_1,A_2)=50000004
• f(A_1,A_3)=50000005
• f(A_2,A_3)=3

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

Note that you are not asked to compute the remainder of the sum divided by 10^8.

Sample Input 2

5
1 3 99999999 99999994 1000000

Sample Output 2

303999988

Problem Statement

There are N types of beans, one bean of each type. The i-th type of bean has a deliciousness of A_i and a color of C_i. The beans are mixed and can only be distinguished by color.

You will choose one color of beans and eat one bean of that color. By selecting the optimal color, maximize the minimum possible deliciousness of the bean you eat.

Constraints

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

Sample Input 1

4
100 1
20 5
30 5
40 1

Sample Output 1

40

Note that beans of the same color cannot be distinguished from each other.

You can choose color 1 or color 5.

• There are two types of beans of color 1, with deliciousness of 100 and 40. Thus, the minimum deliciousness when choosing color 1 is 40.
• There are two types of beans of color 5, with deliciousness of 20 and 30. Thus, the minimum deliciousness when choosing color 5 is 20.

To maximize the minimum deliciousness, you should choose color 1, so print the minimum deliciousness in that case: 40.

Sample Input 2

10
68 3
17 2
99 2
92 4
82 4
10 3
100 2
78 1
3 1
35 4

Sample Output 2

35

Problem Statement

You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.

There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)

Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.

• Each row and each column contain exactly one A, one B, and one C.
• The leftmost character written in the i-th row matches the i-th character of R.
• The topmost character written in the i-th column matches the i-th character of C.

Constraints

• N is an integer between 3 and 5, inclusive.
• R and C are strings of length N consisting of A, B, and C.

Sample Input 1

5
ABCBC
ACAAB

Sample Output 1

Yes
AC..B
.BA.C
C.BA.
BA.C.
..CBA

The grid in the output example satisfies all the following conditions, so it will be treated as correct.

• Each row contains exactly one A, one B, and one C.
• Each column contains exactly one A, one B, and one C.
• The leftmost characters written in the rows are A, B, C, B, C from top to bottom.
• The topmost characters written in the columns are A, C, A, A, B from left to right.

Sample Input 2

3
AAA
BBB

Sample Output 2

No

For this input, there is no way to fill the grid to satisfy the conditions.

Problem Statement

You are given a sequence of N numbers: A=(A_1,A_2,\ldots,A_N). Here, each A_i (1\leq i\leq N) satisfies 1\leq A_i \leq N.

Takahashi and Aoki will play N rounds of a game. For each i=1,2,\ldots,N, the i-th game will be played as follows.

1. Aoki specifies a positive integer K_i.
2. After knowing K_i Aoki has specified, Takahashi chooses an integer S_i between 1 and N, inclusive, and writes it on a blackboard.

3. Repeat the following K_i times.

   • Replace the integer x written on the blackboard with A_x.

If i is written on the blackboard after the K_i iterations, Takahashi wins the i-th round; otherwise, Aoki wins.
Here, K_i and S_i can be chosen independently for each i=1,2,\ldots,N.

Find the number of rounds Takahashi wins if both players play optimally to win.

Constraints

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

Sample Input 1

3
2 2 3

Sample Output 1

2

In the first round, if Aoki specifies K_1=2, Takahashi cannot win whichever option he chooses for S_1: 1, 2, or 3.

For example, if Takahashi writes S_1=1 on the initial blackboard, the two operations will change this number as follows: 1\to 2(=A_1), 2\to 2(=A_2). The final number on the blackboard will be 2(\neq 1), so Aoki wins.

On the other hand, in the second and third rounds, Takahashi can win by writing 2 and 3, respectively, on the initial blackboard, whatever value Aoki specifies as K_i.

Therefore, if both players play optimally to win, Takashi wins two rounds: the second and the third. Thus, you should print 2.

Sample Input 2

2
2 1

Sample Output 2

2

In the first round, Takahashi can win by writing 2 on the initial blackboard if K_1 specified by Aoki is odd, and 1 if it is even.

Similarly, there is a way for Takahashi to win the second round. Thus, Takahashi can win both rounds: the answer is 2.

Problem Statement

There are N points labeled 1, 2, \dots, N on the xy-plane. Point i is located at coordinates (X_i, Y_i).
You can perform the following operation between 0 and K times, inclusive.

• First, choose one of the N points. Let k be the selected point, and assume it is currently at (x, y).
• Next, choose and execute one of the following four actions:
  • Move point k along the x-axis by +1. The coordinates of point k become (x+1, y).
  • Move point k along the x-axis by -1. The coordinates of point k become (x-1, y).
  • Move point k along the y-axis by +1. The coordinates of point k become (x, y+1).
  • Move point k along the y-axis by -1. The coordinates of point k become (x, y-1).
• It is allowed to have multiple points at the same coordinates. Note that the input may already have multiple points at the same coordinates.

After all your operations, draw one square that includes all the N points inside or on the circumference, with each side parallel to the x- or y-axis.
Find the minimum possible value for the length of a side of this square. This value can be shown to be an integer since all points are always on lattice points.

In particular, if all points can be made to exist at the same coordinates, the answer is considered to be 0.

Constraints

• All input values are integers.
• 1 \le N \le 2 \times 10^5
• 0 \le K \le 4 \times 10^{14}
• 0 \le X_i, Y_i \le 10^9

Sample Input 1

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

Sample Output 1

3

The figure below illustrates this case with the horizontal x-axis and the vertical y-axis.

For example, after performing four moves following the arrows in the figure, you can include all points inside or on the circumference of the square shown in the figure with a side length of 3, and this can be shown to be the minimum value.

Sample Input 2

4 400000000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

Sample Output 2

0

All points already exist at the same coordinates from the beginning.
For example, by performing zero operations, all points can be made to exist at the same coordinates, so the answer for this input is 0.

Sample Input 3

10 998244353
489733278 189351894
861289363 30208889
450668761 133103889
306319121 739571083
409648209 922270934
930832199 304946211
358683490 923133355
369972904 539399938
915030547 735320146
386219602 277971612

Sample Output 3

484373824