Problem Statement

There were N contestants in the qualification round of a programming contest. All contestants got distinct ranks.
You are given a length-N string S, which represents whether the contestants want to participate in the final round or not. Specifically,

• if the i-th character of S is o, the contestant ranked i-th in the qualification wants to participate in the final;
• if the i-th character of S is x, the contestant ranked i-th in the qualification does not want to participate in the final.

Among those who want to participate in the final, K contestants with the smallest ranks advance to the final.

Print a string T of length N that satisfies the following conditions:

• if the contestant ranked i-th in the qualification advances to the final, the i-th character of T is o;
• if the contestant ranked i-th in the qualification does not advance to the final, the i-th character of T is x.

Constraints

• N and K are integers.
• 1 \le K \le N \le 100
• S is a string of length N consisting of o and x.
• S has at least K o's.

Sample Input 1

10 3
oxxoxooxox

Sample Output 1

oxxoxoxxxx

In this input, N=10 people took part in the qualification round, and K=3 of them advance to the final.

• The participant who ranked 1-st in the qualification wants to participate in the final, so the participant advances to the final. 1 participant has advanced so far.
• The participants who ranked 2-nd and 3-rd in the qualification do not want to participate in the final, so the participants do not advance to the final.
• The participant who ranked 4-th in the qualification wants to participate in the final, so the participant advances to the final. 2 participants have advanced so far.
• The participants who ranked 5-th in the qualification does not want to participate in the final, so the participant does not advance to the final.
• The participant who ranked 6-th in the qualification wants to participate in the final, so the participant advances to the final. 3 participants have advanced so far.
• Now that 3 people have advanced to the final, no participants ranked 7-th or lower advance to the final.

Problem Statement

Takahashi has a string S consisting of lowercase English letters.

On this string, he will do the operation below just once.

• First, choose a non-negative integer K.
• Then, shift each character of S to the right by K (see below).

Here,

• a shifted to the right by 1 is b;
• b shifted to the right by 1 is c;
• c shifted to the right by 1 is d;
• \cdots
• y shifted to the right by 1 is z;
• z shifted to the right by 1 is a.

For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.

You are given a string T. Determine whether Takahashi can make S equal T by the operation above.

Constraints

• Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
• The lengths of S and T are equal.

Sample Input 1

abc
ijk

Sample Output 1

Yes

When Takahashi chooses K=8,

• a is shifted to the right by 8 and becomes i,
• b is shifted to the right by 8 and becomes j,
• c is shifted to the right by 8 and becomes k,

and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.

Sample Input 2

z
a

Sample Output 2

Yes

Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.

Sample Input 3

ppq
qqp

Sample Output 3

No

There is no non-negative integer K that he can choose to make S equal T, so No should be printed.

Sample Input 4

atcoder
atcoder

Sample Output 4

Yes

Choosing K=0 makes S and T equal.

Problem Statement

You are given a string S of length N consisting of lowercase English letters. Each character of S is painted in one of the M colors: color 1, color 2, ..., color M; for each i = 1, 2, \ldots, N, the i-th character of S is painted in color C_i.

For each i = 1, 2, \ldots, M in this order, let us perform the following operation.

• Perform a right circular shift by 1 on the part of S painted in color i. That is, if the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters are painted in color i from left to right, then simultaneously replace the p_1-th, p_2-th, p_3-th, \ldots, p_k-th characters of S with the p_k-th, p_1-th, p_2-th, \ldots, p_{k-1}-th characters of S, respectively.

Print the final S after the above operations.

The constraints guarantee that at least one character of S is painted in each of the M colors.

Constraints

• 1 \leq M \leq N \leq 2 \times 10^5
• 1 \leq C_i \leq M
• N, M, and C_i are all integers.
• S is a string of length N consisting of lowercase English letters.
• For each integer 1 \leq i \leq M, there is an integer 1 \leq j \leq N such that C_j = i.

Sample Input 1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

Sample Output 1

cszapqbr

Initially, S = apzbqrcs.

• For i = 1, perform a right circular shift by 1 on the part of S formed by the 1-st, 4-th, 7-th characters, resulting in S = cpzaqrbs.
• For i = 2, perform a right circular shift by 1 on the part of S formed by the 2-nd, 5-th, 6-th, 8-th characters, resulting in S = cszapqbr.
• For i = 3, perform a right circular shift by 1 on the part of S formed by the 3-rd character, resulting in S = cszapqbr (here, S is not changed).

Thus, you should print cszapqbr, the final S.

Sample Input 2

2 1
aa
1 1

Sample Output 2

aa

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

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

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750

Problem Statement

The string 20230322 can be rearranged into 02320232, which is a repetition of 0232 twice.
Similarly, a string consisting of digits is said to be happy when it can be rearranged into (or already is) a repetition of some string twice.
You are given a string S consisting of digits. Find the number of pairs of integers (l,r) satisfying all of the following conditions.

• 1 \le l \le r \le |S|. (|S| is the length of S.)
• The (contiguous) substring formed of the l-th through r-th characters of S is happy.

Constraints

• S is a string consisting of digits whose length is between 1 and 5 \times 10^5, inclusive.

Sample Input 1

20230322

Sample Output 1

4

We have S= 20230322.

Here are the four pairs of integers (l,r) that satisfy the condition: (1,6), (1,8), (2,7), and (7,8).

Sample Input 2

0112223333444445555556666666777777778888888889999999999

Sample Output 2

185

S may begin with 0.

Sample Input 3

3141592653589793238462643383279502884197169399375105820974944

Sample Output 3

9