Problem Statement

You start with the number 0 and you want to reach the number N.

You can change the number, paying a certain amount of coins, with the following operations:

• Multiply the number by 2, paying A coins.
• Multiply the number by 3, paying B coins.
• Multiply the number by 5, paying C coins.
• Increase or decrease the number by 1, paying D coins.

You can perform these operations in arbitrary order and an arbitrary number of times.

What is the minimum number of coins you need to reach N?

You have to solve T testcases.

Constraints

• 1 \le T \le 10
• 1 \le N \le 10^{18}
• 1 \le A, B, C, D \le 10^9
• All numbers N, A, B, C, D are integers.

Sample Input 1

5
11 1 2 4 8
11 1 2 2 8
32 10 8 5 4
29384293847243 454353412 332423423 934923490 1
900000000000000000 332423423 454353412 934923490 987654321

Sample Output 1

20
19
26
3821859835
23441258666

For the first testcase, a sequence of moves that achieves the minimum cost of 20 is:

• Initially x = 0.
• Pay 8 to increase by 1 (x = 1).
• Pay 1 to multiply by 2 (x = 2).
• Pay 1 to multiply by 2 (x = 4).
• Pay 2 to multiply by 3 (x = 12).
• Pay 8 to decrease by 1 (x = 11).

For the second testcase, a sequence of moves that achieves the minimum cost of 19 is:

• Initially x = 0.
• Pay 8 to increase by 1 (x = 1).
• Pay 1 to multiply by 2 (x = 2).
• Pay 2 to multiply by 5 (x = 10).
• Pay 8 to increase by 1 (x = 11).

Problem Statement

Tonight, in your favourite cinema they are giving the movie Joker and all seats are occupied. In the cinema there are N rows with N seats each, forming an N\times N square. We denote with 1, 2,\dots, N the viewers in the first row (from left to right); with N+1, \dots, 2N the viewers in the second row (from left to right); and so on until the last row, whose viewers are denoted by N^2-N+1,\dots, N^2.

At the end of the movie, the viewers go out of the cinema in a certain order: the i-th viewer leaving her seat is the one denoted by the number P_i. The viewer P_{i+1} waits until viewer P_i has left the cinema before leaving her seat. To exit from the cinema, a viewer must move from seat to seat until she exits the square of seats (any side of the square is a valid exit). A viewer can move from a seat to one of its 4 adjacent seats (same row or same column). While leaving the cinema, it might be that a certain viewer x goes through a seat currently occupied by viewer y; in that case viewer y will hate viewer x forever. Each viewer chooses the way that minimizes the number of viewers that will hate her forever.

Compute the number of pairs of viewers (x, y) such that y will hate x forever.

Constraints

• 2 \le N \le 500
• The sequence P_1, P_2, \dots, P_{N^2} is a permutation of \{1, 2, \dots, N^2\}.

Sample Input 1

3
1 3 7 9 5 4 8 6 2

Sample Output 1

1

Before the end of the movie, the viewers are arranged in the cinema as follows:

1 2 3
4 5 6
7 8 9

The first four viewers leaving the cinema (1, 3, 7, 9) can leave the cinema without going through any seat, so they will not be hated by anybody.

Then, viewer 5 must go through one of the seats where viewers 2, 4, 6, 8 are currently seated while leaving the cinema; hence he will be hated by at least one of those viewers.

Finally the remaining viewers can leave the cinema (in the order 4, 8, 6, 2) without going through any occupied seat (actually, they can leave the cinema without going through any seat at all).

Sample Input 2

4
6 7 1 4 13 16 10 9 5 11 12 14 15 2 3 8

Sample Output 2

3

Sample Input 3

6
11 21 35 22 7 36 27 34 8 20 15 13 16 1 24 3 2 17 26 9 18 32 31 23 19 14 4 25 10 29 28 33 12 6 5 30

Sample Output 3

11

Problem Statement

There are 3^N people dancing in circle. We denote with 0,1,\dots, 3^{N}-1 the positions in the circle, starting from an arbitrary position and going around clockwise. Initially each position in the circle is occupied by one person.

The people are going to dance on two kinds of songs: salsa and rumba.

• When a salsa is played, the person in position i goes to position j, where j is the number obtained replacing all digits 1 with 2 and all digits 2 with 1 when reading i in base 3 (e.g., the person in position 46 goes to position 65).
• When a rumba is played, the person in position i moves to position i+1 (with the identification 3^N = 0).

You are given a string T=T_1T_2\cdots T_{|T|} such that T_i=S if the i-th song is a salsa and T_i=R if it is a rumba. After all the songs have been played, the person that initially was in position i is in position P_i. Compute the array P_0,P_1,\dots, P_{3^N-1}.

Constraints

• 1 \le N \le 12
• 1 \le |T| \le 200,000
• T contains only the characters S and R.

Sample Input 1

1
SRS

Sample Output 1

2 0 1 

Before any song is played, the positions are: 0, 1, 2.

When we say "person i", we mean "the person that was initially in position i".

1. After the first salsa, the positions are: 0, 2, 1.
2. After the rumba, the positions are: 1, 0, 2 (so, person 0 is in position 1, person 1 is in position 0 and person 2 is in position 2).
3. After the second salsa, the positions are 2, 0, 1 (so, person 0 is in position 2, person 1 is in position 0 and person 2 is in position 1).

Sample Input 2

2
RRSRSSSSR

Sample Output 2

3 8 1 0 5 7 6 2 4 

Sample Input 3

3
SRSRRSRRRSRRRR

Sample Output 3

23 9 22 8 3 7 20 24 19 5 18 4 17 12 16 2 6 1 14 0 13 26 21 25 11 15 10 

Problem Statement

This is an interactive task.

You have to guess a secret password S. A password is a nonempty string whose length is at most L. The characters of a password can be lowercase and uppercase english letters (a, b, ... , z, A, B, ... , Z) and digits (0, 1, ... , 9).

In order to guess the secret password S you can ask queries. A query is made of a valid password T, the answer to such query is the edit distance between S and T (the operations considered for the edit distance are: removal, insertion, substitution). You can ask at most Q queries.

Note: For a definition of edit distance (with operations: removal, insertion, substitution), see this wikipedia page.

Constraints

• L = 128
• Q = 850
• The secret password S is chosen before the beginning of the interaction.

Interaction

To ask a query, print on Standard Output (with a newline at the end)

? T

The string T must be a valid password.

The answer ans to each query shall be read from Standard Input in the form:

ans

As soon as you have determined the hidden password S, you should print on Standard Output (with a newline at the end)

! S

and terminate your program.

Judgement

• After each output, you must flush Standard Output. Otherwise you may get TLE.
• After you print (your guess of) the hidden password, the program must be terminated immediately. Otherwise, the behavior of the judge is undefined.
• If the password you have determined is wrong, you will get WA.
• If you ask a malformed query (for example because the string is not a valid password, or you forget to put ?) or if your program crashes or if you ask more than Q queries, the behavior of the judge is undefined (it does not necessarily give WA).

Samples

In the only sample testcase of this problem the hidden password is Atcod3rIsGreat.

The following one is an example of interaction if S=Atcod3rIsGreat.

Problem Statement

You are playing a game and your goal is to maximize your expected gain. At the beginning of the game, a pawn is put, uniformly at random, at a position p\in\{1,2,\dots, N\}. The N positions are arranged on a circle (so that 1 is between N and 2).

The game consists of turns. At each turn you can either end the game, and get A_p dollars (where p is the current position of the pawn), or pay B_p dollar to keep playing. If you decide to keep playing, the pawn is randomly moved to one of the two adjacent positions p-1, p+1 (with the identifications 0 = N and N+1=1).

What is the expected gain of an optimal strategy?

Note: The "expected gain of an optimal strategy" shall be defined as the supremum of the expected gain among all strategies such that the game ends in a finite number of turns.

Constraints

• 2 \le N \le 200,000
• 0 \le A_p \le 10^{12} for any p = 1,\ldots, N
• 0 \le B_p \le 100 for any p = 1, \ldots, N
• All values in input are integers.

Sample Input 1

5
4 2 6 3 5
1 1 1 1 1

Sample Output 1

4.700000000000

Sample Input 2

4
100 0 100 0
0 100 0 100

Sample Output 2

50.000000000000

Sample Input 3

14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4

Sample Output 3

7047.142857142857

Sample Input 4

10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61

Sample Output 4

815899161079.400024414062

Problem Statement

There are N people (with different names) and K clubs. For each club you know the list of members (so you have K unordered lists). Each person can be a member of many clubs (and also 0 clubs) and two different clubs might have exactly the same members. The value of the number K is the minimum possible such that the following property can be true for at least one configuration of clubs. If every person changes her name (maintaining the property that all names are different) and you know the new K lists of members of the clubs (but you don't know which list corresponds to which club), you are sure that you would be able to match the old names with the new ones.

Count the number of such configurations of clubs (or say that there are more than 1000). Two configurations of clubs that can be obtained one from the other if the N people change their names are considered equal.

Formal statement: A club is a (possibly empty) subset of \{1,\dots, N\} (the subset identifies the members, assuming that the people are indexed by the numbers 1, 2,\dots, N). A configuration of clubs is an unordered collection of K clubs (not necessarily distinct). Given a permutation \sigma(1), \dots, \sigma(N) of \{1,\dots, N\} and a configuration of clubs L=\{C_1, C_2, \dots, C_K\}, we denote with \sigma(L) the configuration of clubs \{\sigma(C_1), \sigma(C_2), \dots, \sigma(C_K)\} (if C is a club, \sigma(C)=\{\sigma(x):\, x\in C\}). A configuration of clubs L is name-preserving if for any pair of distinct permutations \sigma\not=\tau, it holds \sigma(L)\not=\tau(L).

You have to count the number of name-preserving configurations of clubs with the minimum possible number of clubs (so K is minimum). Two configurations L_1, L_2 such that L_2=\sigma(L_1) (for some permutation \sigma) are considered equal. If there are more than 1000 such configurations, print -1.

Constraints

• 2 \le N \le 2\cdot10^{18}

Sample Input 1

2

Sample Output 1

1

The value of K is 1 and the unique name-preserving configuration of clubs is \{\{1\}\} (the configuration \{\{2\}\} is considered the same).

Sample Input 2

3

Sample Output 2

1

The value of K is 2 and the unique (up to permutation) name-preserving configuration of clubs is \{\{1\}, \{1, 2\}\}.

Sample Input 3

4

Sample Output 3

7

The value of K is 3 and the name-preserving configurations of clubs with 3 clubs are:

• \{\{1\}, \{2\}, \{1, 3\}\}
• \{\{1\}, \{1, 2\}, \{2, 3\}\}
• \{\{1, 2\}, \{1, 2\}, \{1, 3\}\}
• \{\{1\}, \{1, 2\}, \{1, 2, 3\}\}
• \{\{1\}, \{2, 3\}, \{1, 2, 4\}\}
• \{\{1, 2\}, \{1, 3\}, \{1, 2, 4\}
• \{\{1, 2\}, \{1, 2, 3\}, \{2, 3, 4\}\}

Sample Input 4

13

Sample Output 4

6

Sample Input 5

26

Sample Output 5

-1

Sample Input 6

123456789123456789

Sample Output 6

-1