Problem Statement

This problem is a sub-problem of Problem F (Operate K), with K=1.
You can solve this problem by submitting a correct solution for Problem F to this problem.

Determine whether it is possible to perform the following operation on string S between 0 and K times, inclusive, to make it identical to string T.

• Choose one of the following three operations and execute it.
  • Insert any one character at any position in S (possibly the beginning or end).
  • Delete one character from S.
  • Choose one character in S and replace it with another character.

Constraints

• Each of S and T is a string of length between 1 and 500000, inclusive, consisting of lowercase English letters.
• \color{red}{K=1}

Sample Input 1

1
abc
agc

Sample Output 1

Yes

Replacing the second character b of abc with g converts abc to agc in one operation.

Sample Input 2

1
abc
awtf

Sample Output 2

No

abc cannot be converted to awtf in one operation.

Sample Input 3

1
abc
ac

Sample Output 3

Yes

Deleting the second character b of abc converts abc to ac in one operation.

Sample Input 4

1
back
black

Sample Output 4

Yes

Inserting l between the first and second characters of back converts back to black in one operation.

Sample Input 5

1
same
same

Sample Output 5

Yes

It is also possible that S = T from the beginning.

Sample Input 6

1
leap
read

Sample Output 6

No

Problem Statement

Find the K-th lexicographically smallest string among the strings that are permutations of a string S.

Constraints

• 1 \le |S| \le 8
• S consists of lowercase English letters.
• There are at least K distinct strings that are permutations of S.

Sample Input 1

aab 2

Sample Output 1

aba

There are three permutations of a string aab: \{ aab, aba, baa \}. The 2-nd lexicographically smallest of them is aba.

Sample Input 2

baba 4

Sample Output 2

baab

Sample Input 3

ydxwacbz 40320

Sample Output 3

zyxwdcba

Problem Statement

There are N sports players.

Among them, there are M incompatible pairs. The i-th incompatible pair (1\leq i\leq M) is the A_i-th and B_i-th players.

You will divide the players into T teams. Every player must belong to exactly one team, and every team must have one or more players. Additionally, for each i=1,2,\ldots,M, the A_i-th and B_i-th players must not belong to the same team.

Find the number of ways to satisfy these conditions. Here, two divisions are considered different when there are two players who belong to the same team in one division and different teams in the other.

Constraints

• 1\leq T\leq N\leq10
• 0\leq M\leq\dfrac{N(N-1)}2
• 1\leq A _ i\lt B _ i\leq N\ (1\leq i\leq M)
• (A _ i,B _ i)\neq (A _ j,B _ j)\ (1\leq i\lt j\leq M)
• All input values are integers.

Sample Input 1

5 2 2
1 3
3 4

Sample Output 1

4

The following four divisions satisfy the conditions.

No other division satisfies them, so print 4.

Sample Input 2

5 1 2
1 3
3 4

Sample Output 2

0

There may be no division that satisfies the conditions.

Sample Input 3

6 4 0

Sample Output 3

65

There may be no incompatible pair.

Sample Input 4

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

Sample Output 4

8001

Problem Statement

The digit sum of a positive integer n is defined as the sum of its digits when n is written in decimal. For example, the digit sum of 2025 is 2 + 0 + 2 + 5 = 9.
A positive integer n is called a good integer if it is divisible by its digit sum. For example, 2025 is a good integer because it is divisible by its digit sum of 9.
A pair of positive integers (a, a+1) is called twin good integers if both a and a+1 are good integers. For example, (2024, 2025) is twin good integers.

You are given a positive integer N. Find a pair of twin good integers (a, a + 1) such that N \leq a and a + 1 \leq 2N. If no such pair exists, report that fact.

Constraints

• N is an integer at least 1 and less than 10^{100000}.

Sample Input 1

5

Sample Output 1

8

(8, 9) is a valid pair of twin good integers satisfying the conditions. Other examples include (5, 6), (6, 7), (7, 8), (9, 10).

Sample Input 2

21

Sample Output 2

-1

No pair of twin good integers satisfies the conditions.

Sample Input 3

1234

Sample Output 3

2024

(2024, 2025) is a valid pair of twin good integers.

Sample Input 4

1234567890123456789012345678901234567890

Sample Output 4

1548651852734633803438094164372911259190

Problem Statement

You are given a sequence of non-negative integers A = (A_1,\dots,A_N) of length N.

For each k = 1,\dots,N, solve the following problem:

• A has N-k+1 (contiguous) subarrays of length k. Take the maximum of each of them, and output the sum of these maxima.

Constraints

• 1 \le N \le 2 \times 10^{5}
• 0 \le A_i \le 10^{7} (1 \le i \le N)
• All input values are integers.

Sample Input 1

4
5 3 4 2

Sample Output 1

14
13
9
5

For k = 1, there are four subarrays of length k=1:

• (5), whose maximum is 5;
• (3), whose maximum is 3;
• (4), whose maximum is 4;
• (2), whose maximum is 2.

The sum is 5 + 3 + 4 + 2 = 14.

For k = 2, there are three subarrays of length k=2:

• (5,3), whose maximum is 5;
• (3,4), whose maximum is 4;
• (4,2), whose maximum is 4.

The sum is 5 + 4 + 4 = 13.

For k = 3, there are two subarrays of length k=3:

• (5,3,4), whose maximum is 5;
• (3,4,2), whose maximum is 4.

The sum is 5 + 4 = 9.

For k = 4, there is one subarray of length k=4:

• (5,3,4,2), whose maximum is 5.

The sum is 5.

Sample Input 2

8
2 0 2 5 0 5 2 4

Sample Output 2

20
28
27
25
20
15
10
5

Sample Input 3

11
9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010

Sample Output 3

61273615
68960818
69588453
65590626
61592799
57594972
47995810
38396648
28797486
19198324
9599162