Problem Statement

A game is played on a strip consisting of N cells consecutively numbered from 1 to N.

Alice has her token on cell A. Borys has his token on a different cell B.

Players take turns, Alice moves first. The moving player must shift his or her token from its current cell X to the neighboring cell on the left, cell X-1, or on the right, cell X+1. Note that it's disallowed to move the token outside the strip or to the cell with the other player's token. In one turn, the token of the moving player must be shifted exactly once.

The player who can't make a move loses, and the other player wins.

Both players want to win. Who wins if they play optimally?

Constraints

• 2 \leq N \leq 100
• 1 \leq A < B \leq N
• All input values are integers.

Sample Input 1

5 2 4

Sample Output 1

Alice

Alice can move her token to cell 3. After that, Borys will be unable to move his token to cell 3, so he will have to move his token to cell 5. Then, Alice moves her token to cell 4. Borys can't make a move and loses.

Sample Input 2

2 1 2

Sample Output 2

Borys

Alice can't make the very first move and loses.

Sample Input 3

58 23 42

Sample Output 3

Borys

Problem Statement

An adult game master and N children are playing a game on an ice rink. The game consists of K rounds. In the i-th round, the game master announces:

• Form groups consisting of A_i children each!

Then the children who are still in the game form as many groups of A_i children as possible. One child may belong to at most one group. Those who are left without a group leave the game. The others proceed to the next round. Note that it's possible that nobody leaves the game in some round.

In the end, after the K-th round, there are exactly two children left, and they are declared the winners.

You have heard the values of A_1, A_2, ..., A_K. You don't know N, but you want to estimate it.

Find the smallest and the largest possible number of children in the game before the start, or determine that no valid values of N exist.

Constraints

• 1 \leq K \leq 10^5
• 2 \leq A_i \leq 10^9
• All input values are integers.

Sample Input 1

4
3 4 3 2

Sample Output 1

6 8

For example, if the game starts with 6 children, then it proceeds as follows:

• In the first round, 6 children form 2 groups of 3 children, and nobody leaves the game.
• In the second round, 6 children form 1 group of 4 children, and 2 children leave the game.
• In the third round, 4 children form 1 group of 3 children, and 1 child leaves the game.
• In the fourth round, 3 children form 1 group of 2 children, and 1 child leaves the game.

The last 2 children are declared the winners.

Sample Input 2

5
3 4 100 3 2

Sample Output 2

-1

This situation is impossible. In particular, if the game starts with less than 100 children, everyone leaves after the third round.

Sample Input 3

10
2 2 2 2 2 2 2 2 2 2

Sample Output 3

2 3

Problem Statement

You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

• 1 \leq N \leq 2000
• 1 \leq A_i \leq 2000
• All input values are integers.

Sample Input 1

3
1 2 1

Sample Output 1

2

In this case, S = (1, 1, 2, 2, 3, 3, 4). Its median is S_4 = 2.

Sample Input 2

1
58

Sample Output 2

58

In this case, S = (58).

Problem Statement

Let f(A, B), where A and B are positive integers, be the string satisfying the following conditions:

• f(A, B) has length A + B;
• f(A, B) contains exactly A letters A and exactly B letters B;
• The length of the longest substring of f(A, B) consisting of equal letters (ex., AAAAA or BBBB) is as small as possible under the conditions above;
• f(A, B) is the lexicographically smallest string satisfying the conditions above.

For example, f(2, 3) = BABAB, and f(6, 4) = AABAABAABB.

Answer Q queries: find the substring of f(A_i, B_i) from position C_i to position D_i (1-based).

Constraints

• 1 \leq Q \leq 10^3
• 1 \leq A_i, B_i \leq 5 \times 10^8
• 1 \leq C_i \leq D_i \leq A_i + B_i
• D_i - C_i + 1 \leq 100
• All input values are integers.

Partial Score

• 500 points will be awarded for passing the testset satisfying 1 \leq A_i, B_i \leq 10^3.

Sample Input 1

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

Sample Output 1

BABAB
AABAABAABB
A
BAABA
ABAB

Problem Statement

Consider the following set of rules for encoding strings consisting of 0 and 1:

• Strings 0 and 1 can be encoded as 0 and 1, respectively.
• If strings A and B can be encoded as P and Q, respectively, then string AB can be encoded as PQ.
• If string A can be encoded as P and K \geq 2 is a positive integer, then string AA...A (A repeated K times) can be encoded as (PxK).

For example, string 001001001, among other possibilities, can be encoded as 001001001, 00(1(0x2)x2)1 and (001x3).

Let's call string A a subset of string B if:

• A and B are equal in length and consist of 0 and 1;
• for all indices i such that A_i = 1, it's also true that B_i = 1.

You are given string S consisting of 0 and 1. Find the total number of distinct encodings of all subsets of S, modulo 998244353.

Constraints

• 1 \leq |S| \leq 100
• S consists of 0 and 1.

Sample Input 1

011

Sample Output 1

9

There are four subsets of S:

• 011 can be encoded as 011 and 0(1x2);
• 010 can be encoded as 010;
• 001 can be encoded as 001 and (0x2)1;
• 000 can be encoded as 000, 0(0x2), (0x2)0 and (0x3).

Thus, the total number of encodings of all subsets of S is 2 + 1 + 2 + 4 = 9.

Sample Input 2

0000

Sample Output 2

10

This time S has only one subset, but it can be encoded in 10 different ways.

Sample Input 3

101110

Sample Output 3

156

Sample Input 4

001110111010110001100000100111

Sample Output 4

363383189

Don't forget to take the result modulo 998244353.

Problem Statement

You have a circle of length C, and you are placing N arcs on it. Arc i has length L_i.

Every arc i is placed on the circle uniformly at random: a random real point on the circle is chosen, then an arc of length L_i centered at this point appears.

Note that the arcs are placed independently. For example, they may intersect or contain each other.

What is the probability that every real point of the circle will be covered by at least one arc? Assume that an arc covers its ends.

Constraints

• 2 \leq N \leq 6
• 2 \leq C \leq 50
• 1 \leq L_i < C
• All input values are integers.

Sample Input 1

2 3
2 2

Sample Output 1

0.3333333333333333

The centers of the two arcs must be at distance at least 1. The probability of this on a circle of length 3 is 1 / 3.

Sample Input 2

4 10
1 2 3 4

Sample Output 2

0.0000000000000000

Even though the total length of the arcs is exactly C and it's possible that every real point of the circle is covered by at least one arc, the probability of this event is 0.

Sample Input 3

4 2
1 1 1 1

Sample Output 3

0.5000000000000000

Sample Input 4

3 5
2 2 4

Sample Output 4

0.4000000000000000

Sample Input 5

4 6
4 1 3 2

Sample Output 5

0.3148148148148148

Sample Input 6

6 49
22 13 27 8 2 19

Sample Output 6

0.2832340720702695