Problem Statement

Takahashi and Aoki decided to jog.
Takahashi repeats the following: "walk at B meters a second for A seconds and take a rest for C seconds."
Aoki repeats the following: "walk at E meters a second for D seconds and take a rest for F seconds."
When X seconds have passed since they simultaneously started to jog, which of Takahashi and Aoki goes ahead?

Constraints

• 1 \leq A, B, C, D, E, F, X \leq 100
• All values in input are integers.

Sample Input 1

4 3 3 6 2 5 10

Sample Output 1

Takahashi

During the first 10 seconds after they started to jog, they move as follows.

• Takahashi walks for 4 seconds, takes a rest for 3 seconds, and walks again for 3 seconds. As a result, he advances a total of (4 + 3) \times 3 = 21 meters.
• Aoki walks for 6 seconds and takes a rest for 4 seconds. As a result, he advances a total of 6 \times 2 = 12 meters.

Since Takahashi goes ahead, Takahashi should be printed.

Sample Input 2

3 1 4 1 5 9 2

Sample Output 2

Aoki

Sample Input 3

1 1 1 1 1 1 1

Sample Output 3

Draw

Problem Statement

A sport event is held in June of every year whose remainder when divided by 4 is 2.
Suppose that it is now January of the year Y. In what year will this sport event be held next time?

Constraints

• 2000 \leq Y \leq 3000
• Y is an integer.

Sample Input 1

2022

Sample Output 1

2022

The remainder when 2022 is divided by 4 is 2, so if it is now January of 2022, the next games will be held in June of the same year.

Sample Input 2

2023

Sample Output 2

2026

Sample Input 3

3000

Sample Output 3

3002

Problem Statement

Takahashi has N foods in his house. The i-th food has the tastiness of A_i.
He dislikes K of these foods: for each i=1,2,\ldots,K, he dislikes the B_i-th food.

Out of the foods with the greatest tastiness among the N foods, Takahashi will randomly choose one and eat it.
If he has a chance to eat something he dislikes, print Yes; otherwise, print No.

Constraints

• 1\leq K\leq N\leq 100
• 1\leq A_i\leq 100
• 1\leq B_i\leq N
• All B_i are distinct.
• All values in input are integers.

Sample Input 1

5 3
6 8 10 7 10
2 3 4

Sample Output 1

Yes

Among the five foods, the ones with the greatest tastiness are Food 3 and 5, of which he eats one.
He dislikes Food 2, 3, and 4, one of which he has a chance to eat: Food 3.
Therefore, the answer is Yes.

Sample Input 2

5 2
100 100 100 1 1
5 4

Sample Output 2

No

The foods with the greatest tastiness are Food 1, 2, and 3, none of which he has a chance to eat.

Sample Input 3

2 1
100 1
2

Sample Output 3

No

The food with the greatest tastiness is Food 1, which he has no chance to eat.

Problem Statement

You are given three strings S_1, S_2, S_3 consisting of lowercase English letters, and a string T consisting of 1, 2, 3.

Concatenate the three strings according to the characters in T and print the resulting string. Formally, conform to the following instructions.

• For each integer i such that 1 \leq i \leq |T|, let the string s_i be defined as follows:
  • S_1, if the i-th character of T is 1;
  • S_2, if the i-th character of T is 2;
  • S_3, if the i-th character of T is 3.
• Concatenate the strings s_1, s_2, \dots, s_{|T|} in this order and print the resulting string.

Constraints

• 1 \leq |S_1|, |S_2|, |S_3| \leq 10
• 1 \leq |T| \leq 1000
• S_1, S_2, and S_3 consist of lowercase English letters.
• T consists of 1, 2, and 3.

Sample Input 1

mari
to
zzo
1321

Sample Output 1

marizzotomari

We have s_1 = mari, s_2 = zzo, s_3 = to, s_4 = mari. Concatenate these and print the resulting string: marizzotomari.

Sample Input 2

abra
cad
abra
123

Sample Output 2

abracadabra

Sample Input 3

a
b
c
1

Sample Output 3

a

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Sample Input 1

5 1 2
rrefa

Sample Output 1

3

First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa

Sample Output 2

4000000000

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

Problem Statement

In a parallel universe, AtCoder holds AtCoder Big Contest, where 10^{16} problems are given at once.
The IDs of the problems are as follows, from the 1-st problem in order: A, B, ..., Z, AA, AB, ..., ZZ, AAA, ...

In other words, the IDs are given in the following order:

• the strings of length 1 consisting of uppercase English letters, in lexicographical order;
• the strings of length 2 consisting of uppercase English letters, in lexicographical order;
• the strings of length 3 consisting of uppercase English letters, in lexicographical order;
• ...

Given a string S that is an ID of a problem given in this contest, find the index of the problem. (See also Samples.)

Constraints

• S is a valid ID of a problem given in AtCoder Big Contest.

Sample Input 1

AB

Sample Output 1

28

The problem whose ID is AB is the 28-th problem of AtCoder Big Contest, so 28 should be printed.

Sample Input 2

C

Sample Output 2

3

The problem whose ID is C is the 3-rd problem of AtCoder Big Contest, so 3 should be printed.

Sample Input 3

BRUTMHYHIIZP

Sample Output 3

10000000000000000

The problem whose ID is BRUTMHYHIIZP is the 10^{16}-th (last) problem of AtCoder Big Contest, so 10^{16} should be printed as an integer.

Problem Statement

The AtCoder Archipelago consists of N islands connected by N bridges. The islands are numbered from 1 to N, and the i-th bridge (1\leq i\leq N-1) connects islands i and i+1 bidirectionally, while the N-th bridge connects islands N and 1 bidirectionally. There is no way to travel between islands other than crossing the bridges.

On the islands, a tour that starts from island X_1 and visits islands X_2, X_3, \dots, X_M in order is regularly conducted. The tour may pass through islands other than those being visited, and the total number of times bridges are crossed during the tour is defined as the length of the tour.

More precisely, a tour is a sequence of l+1 islands a_0, a_1, \dots, a_l that satisfies all the following conditions, and its length is defined as l:

• For all j\ (0\leq j\leq l-1), islands a_j and a_{j+1} are directly connected by a bridge.
• There are some 0 = y_1 < y_2 < \dots < y_M = l such that for all k\ (1\leq k\leq M), a_{y_k} = X_k.

Due to financial difficulties, the islands will close one bridge to reduce maintenance costs. Determine the minimum possible length of the tour when the bridge to be closed is chosen optimally.

Constraints

• 3\leq N \leq 2\times 10^5
• 2\leq M \leq 2\times 10^5
• 1\leq X_k\leq N
• X_k\neq X_{k+1}\ (1\leq k\leq M-1)
• All input values are integers.

Sample Input 1

3 3
1 3 2

Sample Output 1

2

• If the first bridge is closed: By taking the sequence of islands (a_0, a_1, a_2) = (1, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 2 can be conducted. There is no shorter tour.
• If the second bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 3, 1, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.
• If the third bridge is closed: By taking the sequence of islands (a_0, a_1, a_2, a_3) = (1, 2, 3, 2), it is possible to visit islands 1, 3, 2 in order, and a tour of length 3 can be conducted. There is no shorter tour.

Therefore, the minimum possible length of the tour when the bridge to be closed is chosen optimally is 2.

The following figure shows, from left to right, the cases when bridges 1, 2, 3 are closed, respectively. The circles with numbers represent islands, the lines connecting the circles represent bridges, and the blue arrows represent the shortest tour routes.

Sample Input 2

4 5
2 4 2 4 2

Sample Output 2

8

The same island may appear multiple times in X_1, X_2, \dots, X_M.

Sample Input 3

163054 10
62874 19143 77750 111403 29327 56303 6659 18896 64175 26369

Sample Output 3

390009

Problem Statement

Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

• Choose an integer i\ (1\leq i \leq 9). Pay C_i yen (the currency in Japan) to replace x with 10x + i.

Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

Constraints

• 1 \leq N \leq 10^6
• 1 \leq C_i \leq N
• All values in input are integers.

Sample Input 1

5
5 4 3 3 2 5 3 5 3

Sample Output 1

95

For example, the operations where i = 9 and i=5 in this order change x as:

0 \rightarrow 9 \rightarrow 95.

The amount of money required for these operations is C_9 + C_5 = 3 + 2 = 5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

Sample Input 2

20
1 1 1 1 1 1 1 1 1

Sample Output 2

99999999999999999999

Note that the answer may not fit into a 64-bit integer type.

Problem Statement

There is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

• 1\leq K\leq N \leq 2\times 10^5
• -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
• (S_X,S_Y)\neq (X_i,Y_i)
• (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
• All input values are integers.

Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

1. Leave his house with two presents.
2. Go to child 1's house and deliver a present.
3. Return to his house and replenish one present.
4. Go to child 2's house and deliver a present.
5. Go to child 3's house and deliver a present.
6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.

Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562