Problem Statement

There is a single integer N written on a blackboard.
Takahashi will repeat the following series of operations until all integers not less than 2 are removed from the blackboard:

• Choose one integer x not less than 2 written on the blackboard.
• Erase one occurrence of x from the blackboard. Then, write two new integers \left \lfloor \dfrac{x}{2} \right\rfloor and \left\lceil \dfrac{x}{2} \right\rceil on the blackboard.
• Takahashi must pay x yen to perform this series of operations.

Here, \lfloor a \rfloor denotes the largest integer not greater than a, and \lceil a \rceil denotes the smallest integer not less than a.

What is the total amount of money Takahashi will have paid when no more operations can be performed?
It can be proved that the total amount he will pay is constant regardless of the order in which the operations are performed.

Constraints

• 2 \leq N \leq 10^{17}

Sample Input 1

3

Sample Output 1

5

Here is an example of how Takahashi performs the operations:

• Initially, there is one 3 written on the blackboard.
• He chooses 3. He pays 3 yen, erases one 3 from the blackboard, and writes \left \lfloor \dfrac{3}{2} \right\rfloor = 1 and \left\lceil \dfrac{3}{2} \right\rceil = 2 on the blackboard.
• There is one 2 and one 1 written on the blackboard.
• He chooses 2. He pays 2 yen, erases one 2 from the blackboard, and writes \left \lfloor \dfrac{2}{2} \right\rfloor = 1 and \left\lceil \dfrac{2}{2} \right\rceil = 1 on the blackboard.
• There are three 1s written on the blackboard.
• Since all integers not less than 2 have been removed from the blackboard, the process is finished.

Takahashi has paid a total of 3 + 2 = 5 yen for the entire process, so print 5.

Sample Input 2

340

Sample Output 2

2888

Sample Input 3

100000000000000000

Sample Output 3

5655884811924144128

Problem Statement

You are given positive integers N and Q, and a string S of length N consisting of lowercase English letters.

Process Q queries. Each query is of one of the following two types.

• 1 x: Perform the following x times in a row: delete the last character of S and append it to the beginning.
• 2 x: Print the x-th character of S.

Constraints

• 2 \le N \le 5 \times 10^5
• 1 \le Q \le 5 \times 10^5
• 1 \le x \le N
• |S|=N
• S consists of lowercase English letters.
• At least one query in the format 2 x.
• N, Q, x are all integers.

Sample Input 1

3 3
abc
2 2
1 1
2 2

Sample Output 1

b
a

In the 1-st query, S is abc, so the 2-nd character b should be printed. In the 2-nd query, S is changed from abc to cab. In the 3-rd query, S is cab, so the 2-nd character a should be printed.

Sample Input 2

10 8
dsuccxulnl
2 4
2 7
1 2
2 7
1 1
1 2
1 3
2 5

Sample Output 2

c
u
c
u

Problem Statement

You are given a string S of length N consisting of lowercase English letters and the characters ( and ).
Print the string S after performing the following operation as many times as possible.

• Choose and delete a contiguous substring of S that starts with (, ends with ), and does not contain ( or ) other than the first and last characters.

It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.

Constraints

• 1 \leq N \leq 2 \times 10^5
• N is an integer.
• S is a string of length N consisting of lowercase English letters and the characters ( and ).

Sample Input 1

8
a(b(d))c

Sample Output 1

ac

Here is one possible procedure, after which S will be ac.

• Delete the substring (d) formed by the fourth to sixth characters of S, making it a(b)c.
• Delete the substring (b) formed by the second to fourth characters of S, making it ac.
• The operation can no longer be performed.

Sample Input 2

5
a(b)(

Sample Output 2

a(

Sample Input 3

2
()

Sample Output 3

The string S after the procedure may be empty.

Sample Input 4

6
)))(((

Sample Output 4

)))(((

Problem Statement

You are given an integer N. You can perform the following two types of operations:

• Pay X yen to replace N with \displaystyle\left\lfloor\frac{N}{A}\right\rfloor.
• Pay Y yen to roll a die (dice) that shows an integer between 1 and 6, inclusive, with equal probability. Let b be the outcome of the die, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

Here, \lfloor s \rfloor denotes the greatest integer less than or equal to s. For example, \lfloor 3 \rfloor=3 and \lfloor 2.5 \rfloor=2.

Determine the minimum expected cost paid before N becomes 0 when optimally choosing operations.
The outcome of the die in each operation is independent of other rolls, and the choice of operation can be made after observing the results of the previous operations.

Constraints

• 1 \leq N \leq 10^{18}
• 2 \leq A \leq 6
• 1 \leq X, Y \leq 10^9
• All input values are integers.

Sample Input 1

3 2 10 20

Sample Output 1

20.000000000000000

The available operations are as follows:

• Pay 10 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is to perform the first operation twice.

Sample Input 2

3 2 20 20

Sample Output 2

32.000000000000000

The available operations are as follows:

• Pay 20 yen. Replace N with \displaystyle\left\lfloor\frac{N}{2}\right\rfloor.
• Pay 20 yen. Roll a die. Let b be the outcome, and replace N with \displaystyle\left\lfloor\frac{N}{b}\right\rfloor.

The optimal strategy is as follows:

• First, perform the second operation to roll the die.
  • If the outcome is 4 or greater, then N becomes 0.
  • If the outcome is 2 or 3, then N becomes 1. Now, perform the first operation to make N = 0.
  • If the outcome is 1, restart from the beginning.

Sample Input 3

314159265358979323 4 223606797 173205080

Sample Output 3

6418410657.7408381

Problem Statement

You are given a string S of length N consisting of lowercase English letters, and Q queries. Process the queries in order.

Each query is of one of the following two kinds:

• 1 x c : replace the x-th character of S by the character c.
• 2 l r : let T be the string obtained by sorting the characters of S in ascending order. Print Yes if the string consisting of the l-th through r-th characters of S is a substring of T; print No otherwise.

Constraints

• 1\leq N \leq 10^5
• S is a string of length N consisting of lowercase English letters.
• 1 \leq Q \leq 10^5
• For each query of the first kind, 1 \leq x \leq N.
• For each query of the first kind, c is a lowercase English letter.
• For each query of the second kind, 1 \leq l \leq r \leq N.

Sample Input 1

6
abcdcf
4
2 1 3
2 2 6
1 5 e
2 2 6

Sample Output 1

Yes
No
Yes

• In the 1-st query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string abc, consisting of the 1-st through 3-rd characters of S, is a substring of T, so Yes should be printed.
• In the 2-nd query, abccdf is the string T obtained by sorting the characters of S in ascending order. The string bcdcf, consisting of the 2-nd through 6-th characters of S, is not a substring of T, so No should be printed.
• The 3-rd query sets the 5-th character of S to e, making S abcdef.
• In the 4-th query, abcdef is the string T obtained by sorting the characters of S in ascending order. The string bcdef, consisting of the 2-nd through 6-th characters of S, is a substring of T, so Yes should be printed.