Problem Statement

There are N computers and N sockets in a one-dimensional world. The coordinate of the i-th computer is a_i, and the coordinate of the i-th socket is b_i. It is guaranteed that these 2N coordinates are pairwise distinct.

Snuke wants to connect each computer to a socket using a cable. Each socket can be connected to only one computer.

In how many ways can he minimize the total length of the cables? Compute the answer modulo 10^9+7.

Constraints

• 1 ≤ N ≤ 10^5
• 0 ≤ a_i, b_i ≤ 10^9
• The coordinates are integers.
• The coordinates are pairwise distinct.

Sample Input 1

2
0
10
20
30

Sample Output 1

2

There are two optimal connections: 0-20, 10-30 and 0-30, 10-20. In both connections the total length of the cables is 40.

Sample Input 2

3
3
10
8
7
12
5

Sample Output 2

1

Problem Statement

Snuke received a triangle as a birthday present. The coordinates of the three vertices were (x_1, y_1), (x_2, y_2), and (x_3, y_3).

He wants to draw two circles with the same radius inside the triangle such that the two circles do not overlap (but they may touch). Compute the maximum possible radius of the circles.

Constraints

• 0 ≤ x_i, y_i ≤ 1000
• The coordinates are integers.
• The three points are not on the same line.

Sample Input 1

0 0
1 1
2 0

Sample Output 1

0.292893218813

Sample Input 2

3 1
1 5
4 9

Sample Output 2

0.889055514217

Problem Statement

A cheetah and a cheater are going to play the game of Nim. In this game they use N piles of stones. Initially the i-th pile contains a_i stones. The players take turns alternately, and the cheetah plays first. In each turn, the player chooses one of the piles, and takes one or more stones from the pile. The player who can't make a move loses.

However, before the game starts, the cheater wants to cheat a bit to make sure that he can win regardless of the moves by the cheetah. From each pile, the cheater takes zero or one stone and eats it before the game. In case there are multiple ways to guarantee his winning, he wants to minimize the number of stones he eats.

Compute the number of stones the cheater will eat. In case there is no way for the cheater to win the game even with the cheating, print -1 instead.

Constraints

• 1 ≤ N ≤ 10^5
• 2 ≤ a_i ≤ 10^9

Sample Input 1

3
2
3
4

Sample Output 1

3

The only way for the cheater to win the game is to take stones from all piles and eat them.

Sample Input 2

3
100
100
100

Sample Output 2

-1

Problem Statement

There are two (6-sided) dice: a red die and a blue die. When a red die is rolled, it shows i with probability p_i percents, and when a blue die is rolled, it shows j with probability q_j percents.

Petr and tourist are playing the following game. Both players know the probabilistic distributions of the two dice. First, Petr chooses a die in his will (without showing it to tourist), rolls it, and tells tourist the number it shows. Then, tourist guesses the color of the chosen die. If he guesses the color correctly, tourist wins. Otherwise Petr wins.

If both players play optimally, what is the probability that tourist wins the game?

Constraints

• 0 ≤ p_i, q_i ≤ 100
• p_1 + ... + p_6 = q_1 + ... + q_6 = 100
• All values in the input are integers.

Sample Input 1

25 25 25 25 0 0
0 0 0 0 50 50

Sample Output 1

1.000000000000

tourist can always win the game: If the number is at most 4, the color is definitely red. Otherwise the color is definitely blue.

Sample Input 2

10 20 20 10 20 20
20 20 20 10 10 20

Sample Output 2

0.550000000000

Problem Statement

There are N cities in a two-dimensional plane. The coordinates of the i-th city is (x_i, y_i). Initially, the amount of water stored in the i-th city is a_i liters.

Snuke can carry any amount of water from a city to another city. However, water leaks out a bit while he carries it. If he carries l liters of water from the s-th city to the t-th city, only max(l-d_{s,t}, 0) liters of water remains when he arrives at the destination. Here d_{s,t} denotes the (Euclidean) distance between the s-th city and the t-th city. He can perform arbitrary number of operations of this type.

Snuke wants to maximize the minimum amount of water among the N cities. Find the maximum X such that he can distribute at least X liters of water to each city.

Constraints

• 1 ≤ N ≤ 15
• 0 ≤ x_i, y_i, a_i ≤ 10^9
• All values in the input are integers.
• No two cities are at the same position.

Sample Input 1

3
0 0 10
2 0 5
0 5 8

Sample Output 1

6.500000000000

The optimal solution is to carry 3.5 liters of water from the 1st city to the 2nd city. After the operation, both the 1st and the 2nd cities will have 6.5 liters of water, and the 3rd city will have 8 liters of water.

Sample Input 2

15
335279264 849598327 822889311
446755913 526239859 548830120
181424399 715477619 342858071
625711486 448565595 480845266
647639160 467825612 449656269
160714711 336869678 545923679
61020590 573085537 816372580
626006012 389312924 135599877
547865075 511429216 605997004
561330066 539239436 921749002
650693494 63219754 786119025
849028504 632532642 655702582
285323416 611583586 211428413
990607689 590857173 393671555
560686330 679513171 501983447

Sample Output 2

434666178.237122833729

Problem Statement

Snuke received N intervals as a birthday present. The i-th interval was [-L_i, R_i]. It is guaranteed that both L_i and R_i are positive. In other words, the origin is strictly inside each interval.

Snuke doesn't like overlapping intervals, so he decided to move some intervals. For any positive integer d, if he pays d dollars, he can choose one of the intervals and move it by the distance of d. That is, if the chosen segment is [a, b], he can change it to either [a+d, b+d] or [a-d, b-d].

He can repeat this type of operation arbitrary number of times. After the operations, the intervals must be pairwise disjoint (however, they may touch at a point). Formally, for any two intervals, the length of the intersection must be zero.

Compute the minimum cost required to achieve his goal.

Constraints

• 1 ≤ N ≤ 5000
• 1 ≤ L_i, R_i ≤ 10^9
• All values in the input are integers.

Sample Input 1

4
2 7
2 5
4 1
7 5

Sample Output 1

22

One optimal solution is as follows:

• Move the interval [-2, 7] to [6, 15] with 8 dollars
• Move the interval [-2, 5] to [-1, 6] with 1 dollars
• Move the interval [-4, 1] to [-6, -1] with 2 dollars
• Move the interval [-7, 5] to [-18, -6] with 11 dollars

The total cost is 8 + 1 + 2 + 11 = 22 dollars.

Sample Input 2

20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80

Sample Output 2

7337

Problem Statement

Welcome to CODE FESTIVAL 2016! In order to celebrate this contest, find a string s that satisfies the following conditions:

• The length of s is between 1 and 5000, inclusive.
• s consists of uppercase letters.
• s contains exactly K occurrences of the string "FESTIVAL" as a subsequence. In other words, there are exactly K tuples of integers (i_0, i_1, ..., i_7) such that 0 ≤ i_0 < i_1 < ... < i_7 ≤ |s|-1 and s[i_0]='F', s[i_1]='E', ..., s[i_7]='L'.

It can be proved that under the given constraints, the solution always exists. In case there are multiple possible solutions, you can output any.

Constraints

• 1 ≤ K ≤ 10^{18}

Sample Input 1

7

Sample Output 1

FESSSSSSSTIVAL

Sample Input 2

256

Sample Output 2

FFEESSTTIIVVAALL

Problem Statement

Snuke received two matrices A and B as birthday presents. Each of the matrices is an N by N matrix that consists of only 0 and 1.

Then he computed the product of the two matrices, C = AB. Since he performed all computations in modulo two, C was also an N by N matrix that consists of only 0 and 1. For each 1 ≤ i, j ≤ N, you are given c_{i, j}, the (i, j)-element of the matrix C.

However, Snuke accidentally ate the two matrices A and B, and now he only knows C. Compute the number of possible (ordered) pairs of the two matrices A and B, modulo 10^9+7.

Constraints

• 1 ≤ N ≤ 300
• c_{i, j} is either 0 or 1.

Sample Input 1

2
0 1
1 0

Sample Output 1

6

Sample Input 2

10
1 0 0 1 1 1 0 0 1 0
0 0 0 1 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 0 1 1 0
0 0 1 0 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 1 0 0 0 0
1 0 1 0 0 1 1 1 1 1

Sample Output 2

741992411

Problem Statement

Construct an N-gon that satisfies the following conditions:

• The polygon is simple (see notes for the definition).
• Each edge of the polygon is parallel to one of the coordinate axes.
• Each coordinate is an integer between 0 and 10^9, inclusive.
• The vertices are numbered 1 through N in counter-clockwise order.
• The internal angle at the i-th vertex is exactly a_i degrees.

In case there are multiple possible answers, you can output any.

Notes

A polygon is called simple if each edge has a positive length, and no two edges have a common point (except for adjacent edges touching at a vertex).

Constraints

• 3 ≤ N ≤ 1000
• a_i is either 90 or 270.

Sample Input 1

8
90
90
270
90
90
90
270
90

Sample Output 1

0 0
2 0
2 1
3 1
3 2
1 2
1 1
0 1

Sample Input 2

3
90
90
90

Sample Output 2

-1

Problem Statement

Consider all integers between 1 and 2N, inclusive. Snuke wants to divide these integers into N pairs such that:

• Each integer between 1 and 2N is contained in exactly one of the pairs.
• In exactly A pairs, the difference between the two integers is 1.
• In exactly B pairs, the difference between the two integers is 2.
• In exactly C pairs, the difference between the two integers is 3.

Note that the constraints guarantee that N = A + B + C, thus no pair can have the difference of 4 or more.

Compute the number of ways to do this, modulo 10^9+7.

Constraints

• 1 ≤ N ≤ 5000
• 0 ≤ A, B, C
• A + B + C = N

Sample Input 1

3 1 2 0

Sample Output 1

2

There are two possibilities: 1-2, 3-5, 4-6 or 1-3, 2-4, 5-6.

Sample Input 2

600 100 200 300

Sample Output 2

522158867