Problem A. Ancient Cipher ≡

Statement

Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping. The most popular ciphers in those times were so called substitution cipher and permutation cipher.

Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from 'A' to 'Y' to the next ones in the alphabet, and changes 'Z' to 'A', to the message 'VICTORIOUS' one gets the message 'WJDUPSJPVT'.

Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation < 2, 1, 5, 4, 3, 7, 6, 10, 9, 8 > to the message 'VICTORIOUS' one gets the message 'IVOTCIRSUO'.

It was quickly noticed that being applied separately, both substitution cipher and permutation cipher were rather weak. But when being combined, they were strong enough for those times. Thus, the most important messages were first encrypted using substitution cipher, and then the result was encrypted using permutation cipher. Encrypting the message 'VICTORIOUS' with the combination of the ciphers described above one gets the message 'JWPUDJSTVP'.

Archeologists have recently found the message engraved on a stone plate. At the first glance it seemed completely meaningless, so it was suggested that the message was encrypted with some substitution and permutation ciphers. They have conjectured the possible text of the original message that was encrypted, and now they want to check their conjecture. They need a computer program to do it, so you have to write one.

Input file format

Output file format

Constraints

Sample tests

JWPUDJSTVP
VICTORIOUS

YES

MAMA
ROME

NO

HAHA
HEHE

YES

AAA
AAA

YES

NEERCISTHEBEST
SECRETMESSAGES

NO

Problem B. Box ≡

Statement

Ivan works at a factory that produces heavy machinery. He has a simple job — he knocks up wooden boxes of different sizes to pack machinery for delivery to the customers. Each box is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets to make a box. Each pallet is used for one side of the box.

Joe delivers pallets for Ivan. Joe is not very smart and often makes mistakes — he brings Ivan pallets that do not fit together to make a box. But Joe does not trust Ivan. It always takes a lot of time to explain Joe that he has made a mistake.

Fortunately, Joe adores everything related to computers and sincerely believes that computers never make mistakes. Ivan has decided to use this for his own advantage. Ivan asks you to write a program that given sizes of six rectangular pallets tells whether it is possible to make a box out of them.

Input file format

Output file format

Constraints

Sample tests

1345 2584
2584 683
2584 1345
683 1345
683 1345
2584 683

POSSIBLE

1234 4567
1234 4567
4567 4321
4322 4567
4321 1234
4321 1234

IMPOSSIBLE

Problem C. Chandelier ≡

Statement

Lamps-O-Matic company assembles very large chandeliers. A chandelier consists of multiple levels. On the first level crystal pendants are attached to the rings. Assembled rings and new pendants are attached to the rings of the next level, and so on. At the end there is a single large ring — the complete chandelier with multiple smaller rings and pendants hanging from it.

A special-purpose robot assembles chandeliers. It has a supply of crystal pendants and empty rings, and a stack to store elements of a chandelier during assembly. Initially the stack is empty. Robot executes a list of commands to assemble a chandelier.

On command 'a' robot takes a new crystal pendant and places it on the top of the stack. On command '1' to '9' robot takes the corresponding number of items from the top of the stack and consecutively attaches them to the new ring. The newly assembled ring is then placed on the top of the stack. At the end of the program there is a single item on the stack — the complete chandelier.

Unfortunately, for some programs it turns out that the stack during their execution needs to store too many items at some moments. Your task is to optimize the given program, so that the overall design of the respective chandelier remains the same, but the maximal number of items on the stack during the execution is minimal. A pendant or any complex multi-level assembled ring count as a single item of the stack.

The design of a chandelier is considered to be the same if each ring contains the same items in the same order. Since rings are circular it does not matter what item is on the top of the stack when the robot receives a command to assemble a new ring, but the relative order of the items on the stack is important. For example, if the robot receives command '4' when items < i₁, i₂, i₃, i₄ > are on the top of the stack in this order (i₁ being the topmost), then the same ring is also assembled if these items are arranged on the stack in the following ways: < i₂, i₃, i₄, i₁ >, or < i₃, i₄, i₁, i₂ >, or < i₄, i₁, i₂, i₃ >.

Input file format

Output file format

Constraints

Sample tests

aaaaa3aaa2aaa45

6
aaa3aaa2aaa4aa5

Problem D. Document Indexing ≡

Statement

Andy is fond of old computers. He loves everything about them and he uses emulators of old operating systems on his modern computer. Andy also likes writing programs for them. Recently he has decided to write a text editor for his favorite text-mode operating system.

The most difficult task he has got stuck with is document indexing. An index of the document is the lexicographically ordered list of all words occurring in the document with the numbers of pages they occur at. Andy feels that he is not able to write the component of the editor that performs indexing, so he asks you to help.

A document is a sequence of paragraphs. Each paragraph consists of one or more lines. Paragraphs are separated from each other with exactly one blank line.

First, the document is paginated — divided into pages. Each page consists of up to n lines. Lines are placed on the page one after another, until n lines are placed. The following correction rules are then applied:

1) If the last line on a page is the last line of the paragraph, then the following empty line is skipped, i.e. it is not placed on any page. Therefore, the page never starts with a blank line.

2) If the last line on a page is the first line of a paragraph that contains more than one line (so called orphan line), then it is moved to the next page.

3) If the last line on a page is the next-to-last line of a paragraph that contains more than three lines, then this line is moved to the next page (otherwise, the last line of the paragraph would be alone on the page — so called widow line).

4) If the last line on a page is the next-to-last line of a paragraph that contains exactly two or three lines, then the whole paragraph is moved to the next page (so we have neither orphan, nor widow lines).

After applying the correction rules the next page is formed, and so on until the whole document is paginated.

A word is a continuous sequence of letters of the English alphabet. Case is not important.

The index of the document contains each word from the document and the list of the pages it occurs at. The numbers of pages a word occurs at must be listed in the ascending order. Numbers must be separated by commas. If a word occurs on three or more consecutive pages, only the first and the last page numbers of this range must be listed, separated by a dash, for example '3-5,7-10,12,13,15'.

Input file format

Output file format

Constraints

4 ≤ n ≤ 100

The size of the input file does not exceed 20000 bytes. The length of each line of the document does not exceed 200 characters.

Sample tests

6
From thousands of teams competing in regional 
contests held from September to December 2004 
world-wide, seventy-five teams will advance to 
the World Finals in Shanghai, April 3-7, 2005.  

Awards, prizes, scholarships, and bragging rights 
will be at stake for some of the world's finest 
university students of the computing science.

Join us for the challenge, camaraderie, 
and the fun! Become the best of the best
of the best in ACM ICPC!

ACM ICPC is the best contest!

ACM 3
ADVANCE 1
AND 2,3
APRIL 1
AT 2
AWARDS 2
BE 2
BECOME 3
BEST 3
BRAGGING 2
CAMARADERIE 3
CHALLENGE 3
COMPETING 1
COMPUTING 2
CONTEST 3
CONTESTS 1
DECEMBER 1
FINALS 1
FINEST 2
FIVE 1
FOR 2,3
FROM 1
FUN 3
HELD 1
ICPC 3
IN 1,3
IS 3
JOIN 3
OF 1-3
PRIZES 2
REGIONAL 1
RIGHTS 2
S 2
SCHOLARSHIPS 2
SCIENCE 2
SEPTEMBER 1
SEVENTY 1
SHANGHAI 1
SOME 2
STAKE 2
STUDENTS 2
TEAMS 1
THE 1-3
THOUSANDS 1
TO 1
UNIVERSITY 2
US 3
WIDE 1
WILL 1,2
WORLD 1,2

Problem E. Easy Trading ≡

Statement

Frank is a professional stock trader for Advanced Commercial Markets Limited (ACM Ltd). He likes 'easy trading' — using a straightforward strategy to decide when to buy stock and when to sell it.

Frank has a database of historical stock prices for each day. He uses two integer numbers m and n as parameters of his trading strategy. Every day he computes two numbers: P(m) — an average stock price for the previous m days, and P(n) — an average stock price for the previous n days. P(m) > P(n) is an indicator of the upward trend (traders call it bullish trend), and P(m) < P(n) is an indicator of the downward trend (traders call it bearish trend). In practice the values for P(m) and P(n) are never equal.

When a trend reverses from bearish to bullish it is a signal for Frank to buy stock. When a trend reverses from bullish to bearish it is a signal to sell.

Frank has different values for m and n in mind and he wants to backtest them using historical prices. He takes a set of k historical prices p_i For each i (n ≤ i ≤ k) he computes P_i(m) and P_i(n) — an arithmetic average of p_i-m+1 ... p_i and p_i-n+1 ... p_i respectively.

Backtesting generates trading signals according to the following rules.

1) If P_i(m) > P_i(n) there is a bullish trend for day i and a 'BUY ON DAY i' signal is generated if i=n or there was a bearish trend on day i-1.

2) If P_i(m) < P_i(n) there is a bearish tread for day i and a 'SELL ON DAY i' signal is generated if i=n or there was a bullish trend on day i-1.

Your task is to write a program that backtests a specified strategy for Frank — you shall print a signal for the first tested day (day n) followed by the signals in increasing day numbers.

Input file format

Output file format

Constraints

1 ≤ m < n ≤ 100.

n < k ≤ 10000.

0 < p_i < 100 for 1 ≤ i ≤ k.

Sample tests

3 5 17
8.45
9.10
9.40
10.15
10.40
11.08
11.52
12.12
12.51
12.15
11.90
11.25
11.73
10.77
10.80
10.01
9.14

BUY ON DAY 5
SELL ON DAY 12

Problem F. Find the Border ≡

Statement

Closed polyline (with possible self-intersections) partitions a plane into a number of regions. One of the regions is unbounded — it is an exterior of the polyline. All the bounded regions together with the polyline itself form an interior of the polyline (shaded in the picture below). The border of the interior (bold line in the picture) is a polyline as well. This polyline has the same interior as the original one. Your task is to find the border of the interior of the given polyline.

To guarantee the uniqueness (up to the starting point) of the polyline representing the border we require that the following conditions are satisfied for it:

- it has no self-intersections, although may have self-touchings;

- no adjacent vertices of the border coincide;

- no adjacent edges of the border are collinear;

- when traversing the border, its interior is always to the left of its edges.

Input file format

Output file format

Constraints

Sample tests

10
4 9
9 9
12 4
10 2
9 5 
14 10
14 5
10 9
11 4
4 4

13
9.3333 4
10 2
12 4
10.5 6.5
11.5 7.5
14 5
14 10
11.5 7.5
10 9
10.5 6.5
9 9
4 9
4 4

Problem G. Gunman ≡

Statement

Consider a 3D scene with OXYZ coordinate system. Axis OX points to the right, axis OY points up, and axis OZ points away from you. There is a number of rectangular windows on the scene. The plane of each window is parallel to OXY, its sides are parallel to OX and OY. All windows are situated at different depths on the scene (different coordinates z > 0).

A gunman with a rifle moves along OX axis (y = 0 and z = 0). He can shoot a bullet in a straight line. His goal is to shoot a single bullet through all the windows. Just touching a window edge is enough.

Your task is to determine how to make such shot.

Input file format

Output file format

Constraints

Sample tests

3
1 3 5 5 3
1 2 5 7 5
5 2 7 6 6

SOLUTION
-1.000000
2.000000 3.000000 3.000000
4.000000 5.000000 5.000000
5.000000 6.000000 6.000000

3
2 1 5 4 1
3 5 6 8 2
4 3 8 6 4

UNSOLVABLE

Problem H. Heapsort ≡

Statement

A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.

The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:

- if 2i ≤ n then a[i] > a[2i];

- if 2i + 1 ≤ n then a[i] > a[2i + 1].

We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.

In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extract-max.

Now let us consider the part of the array a[1 ... n-1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n-1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n-1] to a heap by sifting, we apply extract-max again, putting second greatest element of the array to a[n-1], and so on.

For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extract-max. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extract-max again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extract-max and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extract-max, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extract-max finally gives (1, 2, 3, 4, 5).

It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.

In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.

Input file format

Output file format

Constraints

Sample tests

6

6 5 3 2 4 1

Problem I. Irrelevant Elements ≡

Statement

Young cryptoanalyst Georgie is investigating different schemes of generating random integer numbers ranging from 0 to m - 1. He thinks that standard random number generators are not good enough, so he has invented his own scheme that is intended to bring more randomness into the generated numbers.

First, Georgie chooses n and generates n random integer numbers ranging from 0 to m - 1. Let the numbers generated be a₁, a₂, ..., a_n. After that Georgie calculates the sums of all pairs of adjacent numbers, and replaces the initial array with the array of sums, thus getting n-1 numbers:a₁ + a₂, a₂ + a₃, ..., a_{n - 1} + a_n. Then he applies the same procedure to the new array, getting n - 2 numbers. The procedure is repeated until only one number is left. This number is then taken modulo m. That gives the result of the generating procedure.

Georgie has proudly presented this scheme to his computer science teacher, but was pointed out that the scheme has many drawbacks. One important drawback is the fact that the result of the procedure sometimes does not even depend on some of the initially generated numbers. For example, if n = 3 and m = 2, then the result does not depend on a₂.

Now Georgie wants to investigate this phenomenon. He calls the i-th element of the initial array irrelevant if the result of the generating procedure does not depend on a_i. He considers various n and m and wonders which elements are irrelevant for these parameters. Help him to find it out.

Input file format

Output file format

Constraints

Sample tests

3 2

1
2

Problem J. Joke with Turtles ≡

Statement

There is a famous joke-riddle for children:

Three turtles are crawling along a road. One turtle says: "There are two turtles ahead of me." The other turtle says: "There are two turtles behind me." The third turtle says: "There are two turtles ahead of me and two turtles behind me." How could this have happened?

The answer is — the third turtle is lying!

Now in this problem you have n turtles crawling along a road. Some of them are crawling in a group, so that they do not see members of their group neither ahead nor behind them. Each turtle makes a statement of the form: "There are a_i turtles crawling ahead of me and b_i turtles crawling behind me." Your task is to find the minimal number of turtles that must be lying.

Let us formalize this task. Turtle i has x_i coordinate. Some turtles may have the same coordinate. Turtle i tells the truth if and only if a_i is the number of turtles such that x_j > x_i and b_i is the number of turtles such that x_j < x_i. Otherwise, turtle i is lying.

Input file format

Output file format

Constraints

Sample tests

3
2 0
0 2
2 2

1 3

5
0 2
0 3
2 1
1 2
4 0

2 1 4

Problem K. Kingdom of Magic ≡

Statement

Kingdom of Magic has a network of bidirectional magic portals between cities since ancient times. Each portal magically connects a pair of cities and allows fast magical communication and travel between them. Cities that are connected by the magic portal are called neighboring.

Prince Albert and Princess Betty are living in the neighboring cities. Since their childhood Albert and Betty were always in touch with each other using magic communication Orbs, which work via a magic portal between the cities.

Albert and Betty are in love with each other. Their love is so great that they cannot live a minute without each other. They always carry the Orbs with them, so that they can talk to each other at any time. There is something strange about their love — they have never seen each other and they even fear to be in the same city at the same time. People say that the magic of the Orbs have affected them.

Traveling through the Kingdom is a complicated affair for Albert and Betty. They have to travel through magic portals, which is somewhat expensive even for royal families. They can simultaneously use a pair of the portals to move to a different pair of cities, or just one of them can use a portal, while the other one stays where he or she is. At any moment of their travel they have to be in a neighboring cities. They cannot simultaneously move through the same portal.

Write a program that helps Albert and Betty travel from one pair of the cities to another pair. It has to find the cheapest travel plan — with the minimal number of times they have to move though the magic portals. When they move through the portals simultaneously it counts as two moves.

Input file format

The first line of the input file contains integer numbers n, m, a₁, b₁, a₂, b₂. Here n is a number of cities in the Kingdom (cities are numbered from 1 to n); m is a number of magic portals; a₁, b₁ (1 ≤ a₁, b₁ ≤ n, a₁ <> b₁) are the neighboring cities where Albert and Betty correspondingly start their travel from; a₂, b₂ (1 ≤ a₂, b₂ ≤ n, a₂ <> b₂) are the neighboring cities where Albert and Betty correspondingly want to get to (a₁ <> a₂ or b₁ <> b₂).

Following m lines describe the portals. Each line contains two numbers p_i1 and p_i2 (1 ≤ p_i1, p_i2 ≤ n, p_i1 <> p_i2) — cities that are connected by the portal. There is at most one portal connecting two cities.

Output file format

On the first line of the output file write two numbers c and k. Here c is the minimal number of moves in the travel plan; k is the number of neighboring city pairs that Albert and Betty visit during their travel including a₁, b₁ at the start and a₂, b₂ at the end.

Then write k lines with two integer numbers a'_i and b'_i on each line — consecutive different pairs of neighboring cities that Albert and Betty visit during their travel. If there are multiple travel plans with the same number of moves, then write any of them. It is guaranteed that solution exists.

Constraints

Sample tests

4 5 1 2 2 1
1 2
2 3
3 4
4 1
1 3

3 3
1 2
2 3
2 1

Problem L. Lattice Animals ≡

Statement

Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyominoes. Polyomino is usually represented as a set of sidewise connected squares. Polyomino with n squares is called n-polyomino.

In this problem you are to find a number of distinct free n-polyominoes that fit into rectangle w × h. Free polyominoes can be rotated and flipped over, so that their rotations and mirror images are considered to be the same.

For example, there are 5 different pentominoes (5-polyominoes) that fit into 2 × 4 rectangle and 3 different octominoes (8-polyominoes) that fit into 3 × 3 rectangle.

Input file format

Output file format

Constraints

Sample tests

5 1 4

0

5 2 4

5

5 3 4

11

5 5 5

12

8 3 3

3