Problem Statement

You are given a string S. Find the number of strings that can result from performing the following operation exactly once.

• Let N be the length of S. Choose a pair of integers (i,j) such that 1\leq i<j\leq N and swap the i-th and j-th characters of S.

It can be proved that you can always perform it under the constraints of this problem.

Constraints

• S is a string of length between 2 and 10^6, inclusive, consisting of lowercase English letters.

Sample Input 1

abc

Sample Output 1

3

The length of S is 3, so 1\leq i<j\leq 3 is satisfied by three pairs of integers (i,j): (1,2), (1,3), and (2,3).

• Swapping the 1-st and 2-nd characters of S results in S being bac.
• Swapping the 1-st and 3-rd characters of S results in S being cba.
• Swapping the 2-nd and 3-rd characters of S results in S being acb.

Therefore, the operation on abc results in one of the three strings: bac, cba, and acb, so print 3.

Sample Input 2

aaaaa

Sample Output 2

1

Swapping any two characters results in S remaining aaaaa. Thus, only one string can result from the operation.

Problem Statement

We have an empty box.
Takahashi can cast the following two spells any number of times in any order.

• Spell A: puts one new ball into the box.
• Spell B: doubles the number of balls in the box.

Tell us a way to have exactly N balls in the box with at most \mathbf{120} casts of spells.
It can be proved that there always exists such a way under the Constraints given.

There is no way other than spells to alter the number of balls in the box.

Constraints

• 1 \leq N \leq 10^{18}
• All values in input are integers.

Sample Input 1

5

Sample Output 1

AABA

This changes the number of balls as follows: 0 \xrightarrow{A} 1\xrightarrow{A} 2 \xrightarrow{B}4\xrightarrow{A} 5.
There are also other acceptable outputs, such as AAAAA.

Sample Input 2

14

Sample Output 2

BBABBAAAB

This changes the number of balls as follows: 0 \xrightarrow{B} 0 \xrightarrow{B} 0 \xrightarrow{A}1 \xrightarrow{B} 2 \xrightarrow{B} 4 \xrightarrow{A}5 \xrightarrow{A}6 \xrightarrow{A} 7 \xrightarrow{B}14.
It is not required to minimize the length of S.

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

• 1\leq N,M \leq 2\times 10^5
• 1\leq A_i,B_j \leq 10^8
• 1\leq P \leq 2\times 10^8
• All input values are integers.

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24

• If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
• If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
• If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
• If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

Sample Output 3

2115597124

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N. The elements of A are distinct.

Process Q queries in the order they are given. Each query is of one of the following two types:

• 1 x y : Insert y immediately after the element x in A. It is guaranteed that x exists in A when this query is given.
• 2 x : Remove the element x from A. It is guaranteed that x exists in A when this query is given.

It is guaranteed that after processing each query, A will not be empty, and its elements will be distinct.

Print A after processing all the queries.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq Q \leq 2\times 10^5
• 1 \leq A_i \leq 10^9
• A_i \neq A_j
• For queries of the first type, 1 \leq x,y \leq 10^9.
• When a query of the first type is given, x exists in A.
• For queries of the second type, 1 \leq x \leq 10^9.
• When a query of the second type is given, x exists in A.
• After processing each query, A is not empty, and its elements are distinct.
• All input values are integers.

Sample Input 1

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

Sample Output 1

4 5 1 3

The queries are processed as follows:

• Initially, A=(2,1,4,3).
• The first query removes 1, making A=(2,4,3).
• The second query inserts 5 immediately after 4, making A=(2,4,5,3).
• The third query removes 2, making A=(4,5,3).
• The fourth query inserts 1 immediately after 5, making A=(4,5,1,3).

Sample Input 2

6
3 1 4 5 9 2
7
2 5
1 3 5
1 9 7
2 9
2 3
1 2 3
2 4

Sample Output 2

5 1 7 2 3

Problem Statement

You are planning to travel from coordinate 0 to coordinate X_N on a number line, then turn around and return to coordinate 0. Here, you can only move in the positive direction on the outbound trip and in the negative direction on the return trip.
You will travel by car. The car consumes one liter of fuel for every unit distance it travels. You can carry up to H liters of fuel and cannot move without fuel.
For each i = 1, 2, \ldots, N-1, there is a gas station at coordinate X_i, where you can get F_i liters of fuel for P_i yen. However, you cannot carry more than H liters of fuel. More precisely, if you have x liters of fuel and use the gas station at coordinate X_i, you must pay P_i yen, and your amount of fuel becomes \min(x + F_i, H) liters. Each gas station can be used at most once in total during the round trip.
Determine if you can achieve this plan when you initially have H liters of fuel, and if it is possible, find the minimum amount of money required.

Constraints

• 1 \leq N, H \leq 300
• 0 < X_1 < X_2 < \ldots < X_N \leq 10^5
• 1 \leq P_i \leq 10^5
• 1 \leq F_i \leq H
• All input values are integers.

Sample Input 1

4 10
2 5 9 11
8 10
5 8
4 9

Sample Output 1

9

You can achieve the plan by using the gas station at coordinate 5 on the outbound trip and the one at coordinate 9 on the return trip, paying a total of 9 yen.
It is impossible to achieve the plan by paying 8 yen or less. Note that you cannot use the same gas station on both the outbound and return trips.

Sample Input 2

1 1
100000

Sample Output 2

-1

Sample Input 3

5 20
4 13 16 18 23
1 16
2 8
4 11
8 13

Sample Output 3

13