Problem Statement

There are four balls, and the color of the i-th ball is A_i.

Find the maximum number of times you can perform this operation: choose two balls of the same color and discard both.

Constraints

• Each of A_1, A_2, A_3, A_4 is an integer between 1 and 4, inclusive.

Sample Input 1

2 1 2 1

Sample Output 1

2

The first and third balls both have color 2, so you can perform the operation to discard the first and third balls together.

Next, the second and fourth balls both have color 1, so you can perform the operation to discard the second and fourth balls together.

Hence, you can perform a total of two operations.

Sample Input 2

4 4 4 1

Sample Output 2

1

Sample Input 3

1 2 3 4

Sample Output 3

0

There are cases where you cannot perform the operation even once.

Problem Statement

On a certain planet, a year has D days, and contests are held every 7 days. Contests never span across days.

The first contest of a certain year was held on the F-th day of the year. On what day of the next year will the first contest of the next year be held?

The constraints of this problem guarantee that at least one contest will be held in the next year.

Constraints

• 10 \leq D \leq 366
• 1 \leq F \leq 7
• All input values are integers.

Sample Input 1

365 4

Sample Output 1

3

If the first contest of a certain year was held on the 4th day of the year, the first contest of the next year will be held on the 3rd day of the year.

Sample Input 2

10 5

Sample Output 2

2

Problem Statement

You are given a sequence of 26 integers P=(P_1,P_2, \ldots ,P_{26}) consisting of integers from 1 through 26. It is guaranteed that all elements in P are distinct.

Print a string S of length 26 that satisfies the following condition.

• For every i (1 \leq i \leq 26), the i-th character of S is the lowercase English letter that comes P_i-th in alphabetical order.

Constraints

• 1 \leq P_i \leq 26
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

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

Sample Output 1

abcdefghijklmnopqrstuvwxyz

Sample Input 2

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

Sample Output 2

bacdefghijklmnopqrstuvwxyz

Sample Input 3

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

Sample Output 3

eklpyqragjdwtcbxzsnifvhmou

Problem Statement

There are N weights called Weight 1, Weight 2, \dots, Weight N. Weight i has a mass of A_i.
Let us say a positive integer n is a good integer if the following condition is satisfied:

• We can choose at most 3 different weights so that they have a total mass of n.

How many positive integers less than or equal to W are good integers?

Constraints

• 1 \leq N \leq 300
• 1 \leq W \leq 10^6
• 1 \leq A_i \leq 10^6
• All values in input are integers.

Sample Input 1

2 10
1 3

Sample Output 1

3

If we choose only Weight 1, it has a total mass of 1, so 1 is a good integer.
If we choose only Weight 2, it has a total mass of 3, so 3 is a good integer.
If we choose Weights 1 and 2, they have a total mass of 4, so 4 is a good integer.
No other integer is a good integer. Also, all of 1, 3, and 4 are integers less than or equal to W. Therefore, the answer is 3.

Sample Input 2

2 1
2 3

Sample Output 2

0

There are no good integers less than or equal to W.

Sample Input 3

4 12
3 3 3 3

Sample Output 3

3

There are 3 good integers: 3, 6, and 9.
For example, if we choose Weights 1, 2, and 3, they have a total mass of 9, so 9 is a good integer.
Note that 12 is not a good integer.

Sample Input 4

7 251
202 20 5 1 4 2 100

Sample Output 4

48

Problem Statement

You are given a length-N sequence of non-negative integers.
When B is a sequence obtained by choosing K elements from A and concatenating them without changing the order, find the maximum possible value of MEX(B).

Here, for a sequence X, we define MEX(X) as the unique non-negative integer m that satisfies the following conditions:

• Every integer i such that 0 \le i < m is contained in X.
• m is not contained in X.

Constraints

• All values in the input are integers.
• 1 \le K \le N \le 3 \times 10^5
• 0 \le A_i \le 10^9

Sample Input 1

7 3
2 0 2 3 2 1 9

Sample Output 1

3

In this input, A=(2,0,2,3,2,1,9), and you obtain the sequence B by picking K=3 elements. For example,

• If the 1-st, 2-nd, and 3-rd elements are chosen, MEX(B)=MEX(2,0,2)=1.
• If the 3-rd, 4-th, and 6-th elements are chosen, MEX(B)=MEX(2,3,1)=0.
• If the 2-nd, 6-th, and 7-th elements are chosen, MEX(B)=MEX(0,1,9)=2.
• If the 2-nd, 3-rd, and 6-th elements are chosen, MEX(B)=MEX(0,2,1)=3.

The maximum possible MEX is 3.

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

• 2 \leq N \leq 3\times 10^5
• 1 \leq P_i \leq N
• The values of P_i are distinct.
• 1 \leq Q_i \leq N
• The values of Q_i are distinct.
• All input values are integers.

Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Sample Input 2

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

Sample Output 2

4 8 6 5 3 10 9 2 1 7

Problem Statement

A non-negative integer X is called a palindrome number if its decimal representation (without leading zeros) is a palindrome.
For example, 363, 12344321, and 0 are all palindrome numbers.

Find the N-th smallest palindrome number.

Constraints

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

Sample Input 1

46

Sample Output 1

363

The 46th smallest palindrome number is 363.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

1000000000000000000

Sample Output 3

90000000000000000000000000000000009

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

Find the number of sequences that satisfy all of the conditions below, modulo 998244353.

• The length is N.
• Each of the elements is an integer between 1 and M (inclusive).
• Its longest increasing subsequence has the length of exactly 3.

Notes

A subsequence of a sequence is the result of removing zero or more elements from it and concatenating the remaining elements without changing the order. For example, (10,30) is a subsequence of (10,20,30), while (20,10) is not a subsequence of (10,20,30).

A longest increasing subsequence of a sequence is its strictly increasing subsequence with the greatest length.

Constraints

• 3 \leq N \leq 1000
• 3 \leq M \leq 10
• All values in input are integers.

Sample Input 1

4 5

Sample Output 1

135

One sequence that satisfies the conditions is (3,4,1,5).
On the other hand, (4,4,1,5) do not, because its longest increasing subsequence has the length of 2.

Sample Input 2

3 4

Sample Output 2

4

Sample Input 3

111 3

Sample Output 3

144980434

Find the count modulo 998244353.