Problem Statement

You've come to your favorite store Infinitesco to buy some ice tea.

The store sells ice tea in bottles of different volumes at different costs. Specifically, a 0.25-liter bottle costs Q yen, a 0.5-liter bottle costs H yen, a 1-liter bottle costs S yen, and a 2-liter bottle costs D yen. The store has an infinite supply of bottles of each type.

You want to buy exactly N liters of ice tea. How many yen do you have to spend?

Constraints

• 1 \leq Q, H, S, D \leq 10^8
• 1 \leq N \leq 10^9
• All input values are integers.

Sample Input 1

20 30 70 90
3

Sample Output 1

150

Buy one 2-liter bottle and two 0.5-liter bottles. You'll get 3 liters for 90 + 30 + 30 = 150 yen.

Sample Input 2

10000 1000 100 10
1

Sample Output 2

100

Even though a 2-liter bottle costs just 10 yen, you need only 1 liter. Thus, you have to buy a 1-liter bottle for 100 yen.

Sample Input 3

10 100 1000 10000
1

Sample Output 3

40

Now it's better to buy four 0.25-liter bottles for 10 + 10 + 10 + 10 = 40 yen.

Sample Input 4

12345678 87654321 12345678 87654321
123456789

Sample Output 4

1524157763907942

Problem Statement

You have a string A = A_1 A_2 ... A_n consisting of lowercase English letters.

You can choose any two indices i and j such that 1 \leq i \leq j \leq n and reverse substring A_i A_{i+1} ... A_j.

You can perform this operation at most once.

How many different strings can you obtain?

Constraints

• 1 \leq |A| \leq 200,000
• A consists of lowercase English letters.

Sample Input 1

aatt

Sample Output 1

5

You can obtain aatt (don't do anything), atat (reverse A[2..3]), atta (reverse A[2..4]), ttaa (reverse A[1..4]) and taat (reverse A[1..3]).

Sample Input 2

xxxxxxxxxx

Sample Output 2

1

Whatever substring you reverse, you'll always get xxxxxxxxxx.

Sample Input 3

abracadabra

Sample Output 3

44

Problem Statement

In the city of Nevermore, there are 10^8 streets and 10^8 avenues, both numbered from 0 to 10^8-1. All streets run straight from west to east, and all avenues run straight from south to north. The distance between neighboring streets and between neighboring avenues is exactly 100 meters.

Every street intersects every avenue. Every intersection can be described by pair (x, y), where x is avenue ID and y is street ID.

There are N fountains in the city, situated at intersections (X_i, Y_i). Unlike normal intersections, there's a circle with radius 10 meters centered at the intersection, and there are no road parts inside this circle.

The picture below shows an example of how a part of the city with roads and fountains may look like.

City governors don't like encountering more than one fountain while moving along the same road. Therefore, every street contains at most one fountain on it, as well as every avenue.

Citizens can move along streets, avenues and fountain perimeters. What is the shortest distance one needs to cover in order to get from intersection (x_1, y_1) to intersection (x_2, y_2)?

Constraints

• 0 \leq x_1, y_1, x_2, y_2 < 10^8
• 1 \leq N \leq 200,000
• 0 \leq X_i, Y_i < 10^8
• X_i \neq X_j for i \neq j
• Y_i \neq Y_j for i \neq j
• Intersections (x_1, y_1) and (x_2, y_2) are different and don't contain fountains.
• All input values are integers.

Sample Input 1

1 1 6 5
3
3 2
5 3
2 4

Sample Output 1

891.415926535897938

One possible shortest path is shown on the picture below. The path starts at the blue point, finishes at the purple point and follows along the red line.

Sample Input 2

3 5 6 4
3
3 2
5 3
2 4

Sample Output 2

400.000000000000000

Sample Input 3

4 2 2 2
3
3 2
5 3
2 4

Sample Output 3

211.415926535897938

Problem Statement

You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1.

You can transform A using the following operations in any order and as many times as you want:

• Shift A by one character to the left (i.e., if A = A_1 A_2 ... A_n, replace A with A_2 A_3 ... A_n A_1).
• Shift A by one character to the right (i.e., if A = A_1 A_2 ... A_n, replace A with A_n A_1 A_2 ... A_{n-1}).
• Choose any i such that B_i = 1. Flip A_i (i.e., set A_i = 1 - A_i).

You goal is to make strings A and B equal.

Print the smallest number of operations required to achieve this, or -1 if the goal is unreachable.

Constraints

• 1 \leq |A| = |B| \leq 2,000
• A and B consist of 0 and 1.

Sample Input 1

1010
1100

Sample Output 1

3

Here is one fastest way to achieve the goal:

• Flip A_1: A = 0010
• Shift A to the left: A = 0100
• Flip A_1 again: A = 1100

Sample Input 2

1
0

Sample Output 2

-1

There is no way to flip the only bit in A.

Sample Input 3

11010
10001

Sample Output 3

4

Here is one fastest way to achieve the goal:

• Shift A to the right: A = 01101
• Flip A_5: A = 01100
• Shift A to the left: A = 11000
• Shift A to the left again: A = 10001

Sample Input 4

0100100
1111111

Sample Output 4

5

Flip A_1, A_3, A_4, A_6 and A_7 in any order.

Problem Statement

You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1. The number of 1's in A and B is equal.

You've decided to transform A using the following algorithm:

• Let a_1, a_2, ..., a_k be the indices of 1's in A.
• Let b_1, b_2, ..., b_k be the indices of 1's in B.
• Replace a and b with their random permutations, chosen independently and uniformly.
• For each i from 1 to k, in order, swap A_{a_i} and A_{b_i}.

Let P be the probability that strings A and B become equal after the procedure above.

Let Z = P \times (k!)^2. Clearly, Z is an integer.

Find Z modulo 998244353.

Constraints

• 1 \leq |A| = |B| \leq 10,000
• A and B consist of 0 and 1.
• A and B contain the same number of 1's.
• A and B contain at least one 1.

Partial Score

• 1200 points will be awarded for passing the testset satisfying 1 \leq |A| = |B| \leq 500.

Sample Input 1

1010
1100

Sample Output 1

3

After the first two steps, a = [1, 3] and b = [1, 2]. There are 4 possible scenarios after shuffling a and b:

• a = [1, 3], b = [1, 2]. Initially, A = 1010. After swap(A_1, A_1), A = 1010. After swap(A_3, A_2), A = 1100.
• a = [1, 3], b = [2, 1]. Initially, A = 1010. After swap(A_1, A_2), A = 0110. After swap(A_3, A_1), A = 1100.
• a = [3, 1], b = [1, 2]. Initially, A = 1010. After swap(A_3, A_1), A = 1010. After swap(A_1, A_2), A = 0110.
• a = [3, 1], b = [2, 1]. Initially, A = 1010. After swap(A_3, A_2), A = 1100. After swap(A_1, A_1), A = 1100.

Out of 4 scenarios, 3 of them result in A = B. Therefore, P = 3 / 4, and Z = 3.

Sample Input 2

01001
01001

Sample Output 2

4

No swap ever changes A, so we'll always have A = B.

Sample Input 3

101010
010101

Sample Output 3

36

Every possible sequence of three swaps puts the 1's in A into the right places.

Sample Input 4

1101011011110
0111101011101

Sample Output 4

932171449

Problem Statement

You are participating in a quiz with N + M questions and Yes/No answers.

It's known in advance that there are N questions with answer Yes and M questions with answer No, but the questions are given to you in random order.

You have no idea about correct answers to any of the questions. You answer questions one by one, and for each question you answer, you get to know the correct answer immediately after answering.

Suppose you follow a strategy maximizing the expected number of correct answers you give.

Let this expected number be P/Q, an irreducible fraction. Let M = 998244353. It can be proven that a unique integer R between 0 and M - 1 exists such that P = Q \times R modulo M, and it is equal to P \times Q^{-1} modulo M, where Q^{-1} is the modular inverse of Q. Find R.

Constraints

• 1 \leq N, M \leq 500,000
• Both N and M are integers.

Partial Score

• 1500 points will be awarded for passing the testset satisfying N = M and 1 \leq N, M \leq 10^5.

Sample Input 1

1 1

Sample Output 1

499122178

There are two questions. You may answer randomly to the first question, and you'll succeed with 50% probability. Then, since you know the second answer is different from the first one, you'll succeed with 100% probability.

The expected number of your correct answers is 3 / 2. Thus, P = 3, Q = 2, Q^{-1} = 499122177 (modulo 998244353), and P \times Q^{-1} = 499122178 (again, modulo 998244353).

Sample Input 2

2 2

Sample Output 2

831870297

The expected number of your correct answers is 17 / 6.

Sample Input 3

3 4

Sample Output 3

770074220

The expected number of your correct answers is 169 / 35.

Sample Input 4

10 10

Sample Output 4

208827570

Sample Input 5

42 23

Sample Output 5

362936761