Problem Statement

You are given a string S consisting of lowercase English letters and a positive integer N. The length of S is at least 2N+1.

Find the string obtained by removing N characters from the beginning and N characters from the end of S.

Constraints

• S is a string consisting of lowercase English letters.
• N is an integer.
• 2N+1 \leq |S| \leq 30
• 1 \leq N \leq 10

Sample Input 1

chemotherapy
3

Sample Output 1

mother

Removing the first three characters (che) and the last three characters (apy) from chemotherapy gives mother.

Sample Input 2

thermometer
4

Sample Output 2

mom

Sample Input 3

burger
1

Sample Output 3

urge

Problem Statement

Takahashi's cake has been eaten by someone. There are three suspects: person 1, person 2, and person 3.

There are two witnesses, Ringo and Snuke. Ringo remembers that person A is not the culprit, and Snuke remembers that person B is not the culprit.

Determine if the culprit can be uniquely identified based on the memories of the two witnesses. If the culprit can be identified, print the person's number.

Constraints

• 1 \leq A, B \leq 3
• All input values are integers.

Sample Input 1

1 2

Sample Output 1

3

From the memories of the two witnesses, it can be determined that person 3 is the culprit.

Sample Input 2

1 1

Sample Output 2

-1

From the memories of the two witnesses, it cannot be determined whether person 2 or person 3 is the culprit. Therefore, print -1.

Sample Input 3

3 1

Sample Output 3

2

Problem Statement

There are N competitive programmers numbered person 1, person 2, \ldots, and person N.
There is a relation called superiority between the programmers. For all pairs of distinct programmers (person X, person Y), exactly one of the following two relations holds: "person X is stronger than person Y" or "person Y is stronger than person X."
The superiority is transitive. In other words, for all triplets of distinct programmers (person X, person Y, person Z), it holds that:

• if person X is stronger than person Y and person Y is stronger than person Z, then person X is stronger than person Z.

A person X is said to be the strongest programmer if person X is stronger than person Y for all people Y other than person X. (Under the constraints above, we can prove that there is always exactly one such person.)

You have M pieces of information on their superiority. The i-th of them is that "person A_i is stronger than person B_i."
Can you determine the strongest programmer among the N based on the information?
If you can, print the person's number. Otherwise, that is, if there are multiple possible strongest programmers, print -1.

Constraints

• 2 \leq N \leq 50
• 0 \leq M \leq \frac{N(N-1)}{2}
• 1 \leq A_i, B_i \leq N
• A_i \neq B_i
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j).
• There is at least one way to determine superiorities for all pairs of distinct programmers, that is consistent with the given information.

Sample Input 1

3 2
1 2
2 3

Sample Output 1

1

You have two pieces of information: "person 1 is stronger than person 2" and "person 2 is stronger than person 3."
By the transitivity, you can also infer that "person 1 is stronger than person 3," so person 1 is the strongest programmer.

Sample Input 2

3 2
1 3
2 3

Sample Output 2

-1

Both person 1 and person 2 may be the strongest programmer. Since you cannot uniquely determine which is the strongest, you should print -1.

Sample Input 3

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

Sample Output 3

-1

Problem Statement

The digit sum of a positive integer n is defined as the sum of the digits when n is represented in decimal. For example, the digit sum of 2026 is 2+0+2+6=10.

Find the number of positive integers not exceeding N whose digit sum is K.

Constraints

• 1\leq N,K \leq 10^5
• All input values are integers.

Sample Input 1

30 4

Sample Output 1

3

Among the positive integers not exceeding 30, there are three integers whose digit sum is 4: 4,13,22.

Sample Input 2

2026 10

Sample Output 2

121

Sample Input 3

99999 45

Sample Output 3

1

Problem Statement

A string T of length 3 consisting of uppercase English letters is an airport code for a string S of lowercase English letters if and only if T can be derived from S by one of the following methods:

• Take a subsequence of length 3 from S (not necessarily contiguous) and convert it to uppercase letters to form T.
• Take a subsequence of length 2 from S (not necessarily contiguous), convert it to uppercase letters, and append X to the end to form T.

Given strings S and T, determine if T is an airport code for S.

Constraints

• S is a string of lowercase English letters with a length between 3 and 10^5, inclusive.
• T is a string of uppercase English letters with a length of 3.

Sample Input 1

narita
NRT

Sample Output 1

Yes

The subsequence nrt of narita, when converted to uppercase, forms the string NRT, which is an airport code for narita.

Sample Input 2

losangeles
LAX

Sample Output 2

Yes

The subsequence la of losangeles, when converted to uppercase and appended with X, forms the string LAX, which is an airport code for losangeles.

Sample Input 3

snuke
RNG

Sample Output 3

No

Problem Statement

You are given a string S consisting of uppercase English letters.
Apply the following procedure to S, and then output the resulting string:

As long as the string contains WA as a (contiguous) substring, repeat the following operation:

• Among all occurrences of WA in the string, replace the leftmost one with AC.

It can be proved under the constraints of this problem that this operation is repeated at most a finite number of times.

Constraints

• S is a string of uppercase English letters with length between 1 and 3\times 10^5, inclusive.

Sample Input 1

WACWA

Sample Output 1

ACCAC

Initially, the string is S= WACWA.
This string contains WA as a substring in two places: from the 1st to the 2nd character, and from the 4th to the 5th character.
In the first operation, we replace the leftmost occurrence (the substring from the 1st to the 2nd character) with AC, resulting in ACCWA.
After the first operation, the string contains WA as a substring in exactly one place: from the 4th to the 5th character.
In the second operation, we replace it with AC, resulting in ACCAC.
Since ACCAC does not contain WA as a substring, the procedure ends. Therefore, we output ACCAC.

Sample Input 2

WWA

Sample Output 2

ACC

Initially, the string is S= WWA.
This string contains WA as a substring in exactly one place: from the 2nd to the 3rd character.
In the first operation, we replace it with AC, resulting in WAC.
Then, after the first operation, the string contains WA in exactly one place: from the 1st to the 2nd character.
In the second operation, we replace it with AC, resulting in ACC.
Since ACC does not contain WA as a substring, the procedure ends. Therefore, we output ACC.

Sample Input 3

WWWWW

Sample Output 3

WWWWW

Since S does not contain WA as a substring from the start, no operations are performed and the procedure ends immediately. Therefore, we output WWWWW.

Problem Statement

In the Kingdom of AtCoder, two kinds of bills are in circulation: 1-dollar bills and K-dollar bills.

At Company J's fully automated cafeteria in the kingdom, desserts and drinks are sold as products.

The company's fully automated cafeteria has a dessert vending machine that sells N desserts, and a drink vending machine that sells M drinks. The desserts are numbered 1 through N, and the drinks are numbered 1 through M.

Dessert i costs A_i dollars, and drink j costs B_j dollars.

As payment, the dessert vending machine accepts both 1-dollar bills and K-dollar bills, but the drink vending machine accepts only K-dollar bills. Both vending machines give change using only 1-dollar bills. You cannot buy two or more of the same product.

Takahashi came to Company J's fully automated cafeteria with X 1-dollar bills and Y K-dollar bills.

Among the combinations of products that he can buy with the bills he has, find the maximum number of products he can purchase.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 2 \leq K \leq 10^9
• 0 \leq X \leq 10^{15}
• 0 \leq Y \leq 10^9
• 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq B_j \leq 10^9 (1 \leq j \leq M)
• All input values are integers.

Sample Input 1

2 3 10
50 6
22 30
20 12 24

Sample Output 1

4

By shopping as follows, Takahashi can buy four products.

• Pay two 10-dollar bills to buy drink 1. No change.
• Pay two 10-dollar bills to buy drink 2. The change is eight 1-dollar bills.
• Pay two 10-dollar bills and ten 1-dollar bills to buy dessert 2. No change.
• Pay twenty-two 1-dollar bills to buy dessert 1. No change.

He cannot buy more than four products, so the answer is 4.

Sample Input 2

1 7 67
677677677766666 0
777666777
20 12 24 67 67 67 67

Sample Output 2

1

By shopping as follows, Takahashi can buy one product.

• Pay 600000777666777 1-dollar bills to buy dessert 1. The change is 600000000000000 1-dollar bills.

He cannot buy more than one product, so the answer is 1.

Sample Input 3

20 20 30
605776135 133105105
97363214 218434035 697895427 109255624 299037330 227873982 195540071 411713803 828357845 244535208 138059186 639510883 39844882 707397687 371274487 696536603 351588202 319490007 47121612 87169661
32256972 567982330 554885983 299718223 443859449 687952877 264684780 666659381 576335424 941894234 406248934 321334900 423472560 863738035 213143887 384834384 468161291 673106162 164648316 15903323

Sample Output 3

22

Problem Statement

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

The following operation will be performed K times:

• For i=1,2,\ldots,N, simultaneously update P_i to P_{P_i}.

Print P after all operations.

Constraints

• 1\leq N\leq2\times10^5
• 1\leq K\leq10^{18}
• 1\leq P_i\leq N\ (1\leq i\leq N)
• P_i\neq P_j\ (1\leq i\lt j\leq N)
• All input values are integers.

Sample Input 1

6 3
5 6 3 1 2 4

Sample Output 1

6 1 3 2 4 5

With each operation, P changes as follows:

• After the first operation, P is (2,4,3,5,6,1).
• After the second operation, P is (4,5,3,6,1,2).
• After the third operation, P is (6,1,3,2,4,5).

Thus, print 6 1 3 2 4 5.

Sample Input 2

5 1000000000000000000
1 2 3 4 5

Sample Output 2

1 2 3 4 5

Since P_i=i, P does not change no matter how many operations are performed.

Sample Input 3

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

Sample Output 3

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

Problem Statement

There are N push buttons. One of them is the winning button, and the other N-1 are losing buttons.

Aoki knows which button is winning, but Takahashi does not. Also, Takahashi cannot distinguish the N buttons.

They play a game using these buttons. The game consists of repeating the following sequence T times:

1. Aoki arranges the N buttons in a random order.
2. Takahashi performs the operation “choose a button and press it” M times. He may choose the same button multiple times.
3. Aoki tells Takahashi the number of times the winning button has been pressed so far since the start of the game.

Takahashi wins if and only if the winning button has been pressed a total of at least K times throughout the T repetitions.

Find Takahashi’s probability of winning when he plays to maximize his win probability.

Constraints

• 1 \le N \le 2\times 10^5
• 1 \le T \le 30
• 1 \le M \le 30
• 1 \le K \le 30
• All input values are integers.

Sample Input 1

3 2 2 3

Sample Output 1

0.222222222222222

The game can proceed as follows (not necessarily optimally):

• 1st repetition
  • Aoki randomly arranges the buttons so that the winning button is at position 1, and the losing buttons are at positions 2 and 3.
  • Takahashi presses button 1.
  • Takahashi presses button 2.
  • Aoki tells him the winning button has been pressed 1 time.
• 2nd repetition
  • Aoki randomly arranges the buttons so that the winning button is at position 3, and the losing buttons are at positions 1 and 2.
  • Takahashi presses button 3.
  • Takahashi presses button 3.
  • Aoki tells him the winning button has been pressed 3 times.
• Since the winning button has been pressed not less than 3 times, Takahashi wins.

The true answer in this case is \tfrac{2}{9}, so outputs like 0.222222 or 0.222223141592 are also accepted.

Sample Input 2

10 1 10 1

Sample Output 2

1.000000000000000

Sample Input 3

100 10 10 2

Sample Output 3

0.401263060761621