Problem Statement

We have three boxes A, B, and C, each of which contains an integer.
Currently, the boxes A, B, and C contain the integers X, Y, and Z, respectively.
We will now do the operations below in order. Find the content of each box afterward.

• Swap the contents of the boxes A and B
• Swap the contents of the boxes A and C

Constraints

• 1 \leq X,Y,Z \leq 100
• All values in input are integers.

Sample Input 1

1 2 3

Sample Output 1

3 1 2

After the contents of the boxes A and B are swapped, A, B, and C contain 2, 1, and 3, respectively.
Then, after the contents of A and C are swapped, A, B, and C contain 3, 1, and 2, respectively.

Sample Input 2

100 100 100

Sample Output 2

100 100 100

Sample Input 3

41 59 31

Sample Output 3

31 41 59

Problem Statement

We have held a popularity poll for N items on sale. Item i received A_i votes.

From these N items, we will select M as popular items. However, we cannot select an item with less than \dfrac{1}{4M} of the total number of votes.

If M popular items can be selected, print Yes; otherwise, print No.

Constraints

• 1 \leq M \leq N \leq 100
• 1 \leq A_i \leq 1000
• A_i are distinct.
• All values in input are integers.

Sample Input 1

4 1
5 4 2 1

Sample Output 1

Yes

There were 12 votes in total. The most popular item received 5 votes, and we can select it.

Sample Input 2

3 2
380 19 1

Sample Output 2

No

There were 400 votes in total. The second and third most popular items received less than \dfrac{1}{4\times 2} of the total number of votes, so we cannot select them. Thus, we cannot select two popular items.

Sample Input 3

12 3
4 56 78 901 2 345 67 890 123 45 6 789

Sample Output 3

Yes

Problem Statement

Given any integer x, Aoki can do the operation below.

Operation: Replace x with the absolute difference of x and K.

You are given the initial value of an integer N. Find the minimum possible value taken by N after Aoki does the operation zero or more times.

Constraints

• 0 ≤ N ≤ 10^{18}
• 1 ≤ K ≤ 10^{18}
• All values in input are integers.

Sample Input 1

7 4

Sample Output 1

1

Initially, N=7.

After one operation, N becomes |7-4| = 3.

After two operations, N becomes |3-4| = 1, which is the minimum value taken by N.

Sample Input 2

2 6

Sample Output 2

2

N=2 after zero operations is the minimum.

Sample Input 3

1000000000000000000 1

Sample Output 3

0

Problem Statement

A positive integer X is said to be a lunlun number if and only if the following condition is satisfied:

• In the base ten representation of X (without leading zeros), for every pair of two adjacent digits, the absolute difference of those digits is at most 1.

For example, 1234, 1, and 334 are lunlun numbers, while none of 31415, 119, or 13579 is.

You are given a positive integer K. Find the K-th smallest lunlun number.

Constraints

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

Sample Input 1

15

Sample Output 1

23

We will list the 15 smallest lunlun numbers in ascending order:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23.
Thus, the answer is 23.

Sample Input 2

1

Sample Output 2

1

Sample Input 3

13

Sample Output 3

21

Sample Input 4

100000

Sample Output 4

3234566667

Note that the answer may not fit into the 32-bit signed integer type.

Problem Statement

Takahashi has decided to work on K days of his choice from the N days starting with tomorrow.

You are given an integer C and a string S. Takahashi will choose his workdays as follows:

• After working for a day, he will refrain from working on the subsequent C days.
• If the i-th character of S is x, he will not work on Day i, where Day 1 is tomorrow, Day 2 is the day after tomorrow, and so on.

Find all days on which Takahashi is bound to work.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 0 \leq C \leq N
• The length of S is N.
• Each character of S is o or x.
• Takahashi can choose his workdays so that the conditions in Problem Statement are satisfied.

Sample Input 1

11 3 2
ooxxxoxxxoo

Sample Output 1

6

Takahashi is going to work on 3 days out of the 11 days. After working for a day, he will refrain from working on the subsequent 2 days.

There are four possible choices for his workdays: Day 1,6,10, Day 1,6,11, Day 2,6,10, and Day 2,6,11.

Thus, he is bound to work on Day 6.

Sample Input 2

5 2 3
ooxoo

Sample Output 2

1
5

There is only one possible choice for his workdays: Day 1,5.

Sample Input 3

5 1 0
ooooo

Sample Output 3

There may be no days on which he is bound to work.

Sample Input 4

16 4 3
ooxxoxoxxxoxoxxo

Sample Output 4

11
16

Problem Statement

Given is a positive integer N.

We will choose an integer K between 2 and N (inclusive), then we will repeat the operation below until N becomes less than K.

• Operation: if K divides N, replace N with N/K; otherwise, replace N with N-K.

In how many choices of K will N become 1 in the end?

Constraints

• 2 \leq N \leq 10^{12}
• N is an integer.

Sample Input 1

6

Sample Output 1

3

There are three choices of K in which N becomes 1 in the end: 2, 5, and 6.

In each of these choices, N will change as follows:

• When K=2: 6 \to 3 \to 1
• When K=5: 6 \to 1
• When K=6: 6 \to 1

Sample Input 2

3141

Sample Output 2

13

Sample Input 3

314159265358

Sample Output 3

9