Problem Statement

There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?

Constraints

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

Sample Input 1

4
5 15 2 10

Sample Output 1

11

Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.

Sample Input 2

4
15 5 2 10

Sample Output 2

0

Person 1 is already the strongest, so no more programming skill is needed.

Sample Input 3

3
100 100 100

Sample Output 3

1

Problem Statement

In the calendar of AtCoder Kingdom, a year consists of M months from month 1 to month M, and each month consists of D days from day 1 to day D.

What day follows year y, month m, day d in this calendar?

Constraints

• 1000 \leq y \leq 9000
• 1 \leq m \leq M \leq 99
• 1 \leq d \leq D \leq 99
• All input values are integers.

Sample Input 1

12 30
2023 12 30

Sample Output 1

2024 1 1

In the calendar of the kingdom, a year consists of 12 months, and each month consists of 30 days. Thus, the day following year 2023, month 12, day 30 is year 2024, month 1, day 1.

Sample Input 2

36 72
6789 23 45

Sample Output 2

6789 23 46

In the calendar of the kingdom, one year consists of 36 months, and each month consists of 72 days. Thus, the day following year 6789, month 23, day 45 is year 6789, month 23, day 46.

Sample Input 3

12 30
2012 6 20

Sample Output 3

2012 6 21

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

• Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
• S_1, S_2, and S_3 are pairwise different.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC

Problem Statement

We have a sequence of length N consisting of positive integers: A=(A_1,\ldots,A_N). Any two adjacent terms have different values.

Let us insert some numbers into this sequence by the following procedure.

1. If every pair of adjacent terms in A has an absolute difference of 1, terminate the procedure.
2. Let A_i, A_{i+1} be the pair of adjacent terms nearest to the beginning of A whose absolute difference is not 1.
   • If A_i < A_{i+1}, insert A_i+1,A_i+2,\ldots,A_{i+1}-1 between A_i and A_{i+1}.
   • If A_i > A_{i+1}, insert A_i-1,A_i-2,\ldots,A_{i+1}+1 between A_i and A_{i+1}.
3. Return to step 1.

Print the sequence when the procedure ends.

Constraints

• 2 \leq N \leq 100
• 1 \leq A_i \leq 100
• A_i \neq A_{i+1}
• All values in the input are integers.

Sample Input 1

4
2 5 1 2

Sample Output 1

2 3 4 5 4 3 2 1 2

The initial sequence is (2,5,1,2). The procedure goes as follows.

• Insert 3,4 between the first term 2 and the second term 5, making the sequence (2,3,4,5,1,2).
• Insert 4,3,2 between the fourth term 5 and the fifth term 1, making the sequence (2,3,4,5,4,3,2,1,2).

Sample Input 2

6
3 4 5 6 5 4

Sample Output 2

3 4 5 6 5 4

No insertions may be performed.

Problem Statement

There are N people standing in a line: person 1, person 2, \ldots, person N.

You are given the arrangement of the people as a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

A _ i\ (1\leq i\leq N) represents the following information:

• if A _ i=-1, person i is at the front of the line;
• if A _ i\neq -1, person i is right behind person A _ i.

Print the people's numbers in the line from front to back.

Constraints

• 1\leq N\leq3\times10 ^ 5
• A _ i=-1 or 1\leq A _ i\leq N\ (1\leq i\leq N)
• There is exactly one way to arrange the N people consistent with the information given.
• All input values are integers.

Sample Input 1

6
4 1 -1 5 3 2

Sample Output 1

3 5 4 1 2 6

If person 3, person 5, person 4, person 1, person 2, and person 6 stand in line in this order from front to back, the arrangement matches the given information.

Indeed, it can be seen that:

• person 1 is standing right behind person 4,
• person 2 is standing right behind person 1,
• person 3 is at the front of the line,
• person 4 is standing right behind person 5,
• person 5 is standing right behind person 3, and
• person 6 is standing right behind person 2.

Thus, print 3, 5, 4, 1, 2, and 6 in this order, separated by spaces.

Sample Input 2

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

Sample Output 2

1 2 3 4 5 6 7 8 9 10

Sample Input 3

30
3 25 20 6 18 12 26 1 29 -1 21 17 23 9 8 30 10 15 22 27 4 13 5 11 16 24 28 2 19 7

Sample Output 3

10 17 12 6 4 21 11 24 26 7 30 16 25 2 28 27 20 3 1 8 15 18 5 23 13 22 19 29 9 14

Problem Statement

How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?

• 1\le A_i \le M (1 \le i \le N)

• \displaystyle\sum _{i=1}^N A_i \leq K

Since the count can get enormous, find it modulo 998244353.

Constraints

• 1 \leq N, M \leq 50
• N \leq K \leq NM
• All values in input are integers.

Sample Input 1

2 3 4

Sample Output 1

6

The following six sequences satisfy the conditions.

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

Sample Input 2

31 41 592

Sample Output 2

798416518

Be sure to print the count modulo 998244353.

Problem Statement

There is a grid of H rows and W columns. Some cells (possibly zero) contain magnets.
The state of the grid is represented by H strings S_1, S_2, \ldots, S_H of length W. If the j-th character of S_i is #, it indicates that there is a magnet in the cell at the i-th row from the top and j-th column from the left; if it is ., it indicates that the cell is empty.

Takahashi, wearing an iron armor, can move in the grid as follows:

• If any of the cells vertically or horizontally adjacent to the current cell contains a magnet, he cannot move at all.
• Otherwise, he can move to any one of the vertically or horizontally adjacent cells.
  However, he cannot exit the grid.

For each cell without a magnet, define its degree of freedom as the number of cells he can reach by repeatedly moving from that cell. Find the maximum degree of freedom among all cells without magnets in the grid.

Here, in the definition of degree of freedom, "cells he can reach by repeatedly moving" mean cells that can be reached from the initial cell by some sequence of moves (possibly zero moves). It is not necessary that there is a sequence of moves that visits all such reachable cells starting from the initial cell. Specifically, each cell itself (without a magnet) is always included in the cells reachable from that cell.

Constraints

• 1 \leq H, W \leq 1000
• H and W are integers.
• S_i is a string of length W consisting of . and #.
• There is at least one cell without a magnet.

Sample Input 1

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

Sample Output 1

9

Let (i,j) denote the cell at the i-th row from the top and j-th column from the left. If Takahashi starts at (2,3), possible movements include:

• (2,3) \to (2,4) \to (1,4) \to (1,5) \to (2,5)
• (2,3) \to (2,4) \to (3,4)
• (2,3) \to (2,2)
• (2,3) \to (1,3)
• (2,3) \to (3,3)

Thus, including the cells he passes through, he can reach at least nine cells from (2,3).
Actually, no other cells can be reached, so the degree of freedom for (2,3) is 9.

This is the maximum degree of freedom among all cells without magnets, so print 9.

Sample Input 2

3 3
..#
#..
..#

Sample Output 2

1

For any cell without a magnet, there is a magnet in at least one of the adjacent cells.
Thus, he cannot move from any of these cells, so their degrees of freedom are 1.
Therefore, print 1.

Problem Statement

You are given a positive integer N and two strings S and T, each of length N and consisting of lowercase English letters.

Determine whether it is possible to make S identical to T by repeating the operation below any number of times (possibly zero). If it is possible, also find the minimum number of operations required.

• Choose two lowercase English letters x, y and replace every occurrence of x in S with y.

Constraints

• 1\leq N \leq 2\times 10^5
• N is an integer.
• Each of S and T is a string of length N, consisting of lowercase English letters.

Sample Input 1

6
afbfda
bkckbb

Sample Output 1

4

By performing the operation four times in the following way, you can make S identical to T:

1. Choose x= b and y= c. S becomes afcfda.
2. Choose x= a and y= b. S becomes bfcfdb.
3. Choose x= f and y= k. S becomes bkckdb.
4. Choose x= d and y= b. S becomes bkckbb, which is identical to T.

It cannot be done with fewer than four operations, so the minimum number of operations required is 4.

Sample Input 2

4
abac
abac

Sample Output 2

0

S and T are already identical, so no operations are required.

Sample Input 3

4
abac
abrc

Sample Output 3

-1

No matter how you repeat the operation, it is impossible to make S identical to T.

Sample Input 4

4
abac
bcba

Sample Output 4

4

Problem Statement

For a positive integer x, define f(x) as follows: "While x is even, keep dividing it by 2. The final value of x after these divisions is f(x)." For example, f(4)=f(2)=f(1)=1, and f(12)=f(6)=f(3)=3.

Given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N, find \displaystyle \sum_{i=1}^N \sum_{j=i}^N f(A_i+A_j).

Constraints

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

Sample Input 1

2
4 8

Sample Output 1

5

f(A_1+A_1)=f(8)=1, f(A_1+A_2)=f(12)=3, f(A_2+A_2)=f(16)=1. Thus, Print 1+3+1=5.

Sample Input 2

3
51 44 63

Sample Output 2

384

Sample Input 3

8
577752 258461 183221 889769 278633 577212 392309 326001

Sample Output 3

20241214