Problem A. Add one ≡

Statement

Your task is the most trivial one: given non-negative integer N, output N + 1.

The only complication is that the integer is given in an unknown base between 2 and 36 inclusive. Because of that, your program should output all possible distinct answers in lexicographically increasing order.

Input file format

Output file format

Constraints

N contains from 1 to 100 digits

Sample tests

32

33

9

10
A

Problem B. Beat the jocks ≡

Statement

It is well known that high school students are usually divided into "nerds", who prefer to solve problems using their brains, and "jocks", who rely on their muscles instead. These groups often deride each other, each claiming their way is superior.

To determine which group is better at problem solving, teacher suggested the "locker challenge":

There is a corridor in the school with a row of N closed lockers. If you "toggled" the state of each locker (i.e. opening it if its closed, closing it if its open) in the following manner, which lockers would remain open?

• Every single locker is toggled (since all lockers start closed, this means each one is opened).
• Every other locker is toggled (in this case, closed), starting with the second.
• Every third locker is toggled, starting with the third.
• Every fourth locker is toggled, starting with the forth.
• ...
• The N-th locker is toggled.

The jocks would simply run along the corridor, opening and closing the lockers until they answered the question. Nerds try to work the solution out on paper. The first team to get the correct answer wins.

Since you are, hopefully, from the nerds camp, can you beat the jocks by writing the program which calculates the answer quickly enough?

Input file format

Output file format

Constraints

1 ≤ N ≤ 10⁹

Sample tests

1

1

5

1 4

Problem C. Calculate a limit ≡

Statement

Your program must calculate the value of limx ↦ ∞a₁x + a₂x² + …  + a_nxⁿb₁x + b₂x² + …  + b_nxⁿ.

All coefficients are integers, so the answer must be calculated exactly and presented in the form of irreducible fraction.

Input file format

Output file format

Constraints

1 ≤ n ≤ 100, 0 ≤ a_i, b_i ≤ 10⁹, ∑i (b_i + a_i) > 0

Sample tests

1
2 4

1 2

2
0 1  1 0

1 0

Problem D. Deliver barbed wire ≡

Statement

Dedicated to the 25th anniversary of the Elite game.

The planet Lave has a form of a perfect sphere. There are N cities on the surface of the planet. Each city may belong to one of several countries.

The history of Lave knows many wars and annexations, so government of each country tries to keep it's territory simple in shape and it's borders short.

If cities A and B are located in the same country, the shortest path from A to B lies fully within that country. Furthermore, if three cities A, B and C are all located in the same country, the shortest path from C to every point of the shortest path form A to B also lies fully within that country.

The border of each country is continuous, connected (no enclaves), and as short as possible while keeping all the above mentioned properties. All countries have non-zero area.

Some parts of the planet surface may remain neutral. In particular, Lave international conventions state that Northern and Southern poles never belong to any country.

Space merchant and freelancer Dave B. is planning a business trip to Lave. He wants to sell some barbed wire to the country with the longest perimeter. Unfortunately for him, the political situation on Lave changes so rapidly, that he is not sure about which city will belong to which country at the moment he arrives.

So, Dave hired you to calculate the longest length of country border over all possible city allegiances.

Input file format

Input file contains integer N — number of cities, followed by N triplets of real numbers x_i y_i z_i — city coordinates. The center of the planet is located at point (0, 0, 0). Both poles lie on Oz axis.

Output file format

Output file must contain a single real number with at least 5 correct digits after the decimal point — the longest possible country perimeter. If the cities are located so that no countries can exist, output "0".

Constraints

Sample tests

3
1 0 0
0 1 0
0.577350269 0.577350269 0.577350269

3.48143

Problem E. Emulate a robot ≡

Statement

Young robot technician Vasya built his first robot. Vasya is already good with mechanics, but not so good with programming, so he created a very simple program for his robot.

Robot drives forward at the speed of 1 meter per second until the nearest obstacle. Then it rotates to the left by 90° steps until there is no obstacle in front of it, and continues driving. The turning is so fast it can be considered instantaneous. The robot never stops by itself.

To test the robot, Vasya has found a big field and built a labyrinth in it. The labyrinth is represented by N × N array of characters, where '#' represents 1 × 1 meter obstacle and '.' — empty place of the same size. All space outside the labyrinth is empty too.

North-west corner of the labyrinth has coordinates (1, 1). Coordinate axises run from west to east and from north to south.

Vasya placed the robot at coordinates (x, y) facing north, started it and waited for S seconds. Where is the robot now?

Starting position is not inside of an obstacle and is not surrounded by the obstacles from all sides.

Input file format

Output file format

Output file must contain integers x′ y′ — coordinates of the robot after S seconds.

Note that both starting and final coordinates may be outside of the labyrinth.

Constraints

1 ≤ N ≤ 1000,  − 10⁵ ≤ x, y ≤ 10⁵, 1 ≤ S ≤ 10⁹

Sample tests

3 2 5 10
###
#..
#..

2 9

Problem F. Fence relicts ≡

Statement

The Nearsea region has a large forest, where many relict trees grow. The local government decided to create a reservation park with the area between 0 and S square meters. The park must have a shape of rectangle with the sides parallel to coordinate axises.

Environment activists surveyed the forest and found out that it contained N relict trees located at coordinates (x_i, y_i), measured in meters.

Find such park location and size that the number of relict trees inside of it or on its boundary is maximum possible.

Input file format

Output file format

Constraints

1 ≤ N ≤ 500,  − 10⁴ ≤ x_i, y_i ≤ 10⁴, 1 ≤ S ≤ 10⁹

Sample tests

5 100
0 0  10 0  10 10  0 10  15 10

0 0 10 10

3 2
0 0  10 0  20 0

0 0 20 0

Problem G. Group by GCD ≡

Statement

Given N positive integers, divide them in two disjoint non-empty groups in such a way that the greatest common divisor of each group is greater than 1.

Input file format

Output file format

Constraints

Sample tests

2
3 5

3 0 5

4
2 2 6 8

2 6 2 0 8

3
3 4 5

-1

Problem H. Help Gridland environment ≡

Statement

The Gridland is a small country located on a beautiful hilly landscape. It is well known for its achievements in the fields of nanotechnology and car industry.

The country has many cities, located in the nodes of W × H grid with square cells. All roads between cities go straight along the lines of the grid in either north-south or east-west direction and have the same length.

A young scientist Vasya Reshetkin developed a new hi-tech car powered by nuclear batteries. The car is very energy-efficient: while going uphill, the car consumes a fixed amount of energy per unit of distance, and while going downhill it stops the engine, consuming no energy at all. That means that the amount of energy required to travel along the fixed route from A to B and then back from B to A depends only on the distance, and not on the inclination profile of the road.

Thus if the car requires a units of energy to move from a city to its neighbor, then moving back will require L − a units, where L is the same for all cities. To simplify maintenance, each battery was designed to store exactly L units of energy.

Unfortunately, prolonged storage of half-used batteries may lead to nuclear contamination of the environment, so it is important that the batteries are always used fully.

Your country is known for achievements in computer programming. So you have been given a job to write a program that plans a route from city A to city B such that it will use exactly L × k units of energy for some integer k. This route may not be the shortest one, but this is a price Gridland citizens are willing to pay for environment preservation.

Input file format

First line of input file contains integers L W H — battery capacity, width and height of city grid respectively.

Second line contains integers r_A c_A r_B c_B — row and column of city A and row and column of city B respectively. Rows span from west to east in order of increasing column numbers. Columns span from north to south in order of increasing row numbers. All numbering is zero-based.

Next H − 1 lines contain 2 * W − 1 integers e₁ s₁… e_W − 1 s_W − 1 s_W, where e_i is the energy required to move from i-th city in the row to its eastern neighbor, and s_i — energy to move to its southern neighbor.

Last line contains W − 1 integers e_i — energy required to move from the i-th city in the southernmost row to its eastern neighbor.

Output file format

Output file must contain a single line with the string of symbols "N", "S", "E", "W", describing a route from city A to city B which requires integer amount of batteries of capacity L. It there is more than one answer, output any of them not exceeding 3(H + W)L in length. If there is no answer, output a single symbol "X".

Constraints

Sample tests

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

ENE

Problem I. Improve RLE ≡

Statement

A computer programmer and mathematician Kumar Harikrishnan develops a new data compression system — ACM (Advanced Compression Method) — which will incorporate all of his brilliant ideas.

The first component of ACM will be a modification of well-known RLE algorithm, called Improved RLE. Since Kumar have much more difficult tasks to accomplish (such as to write Improved Hamming and Improved Lempel-Ziv), he asks you to implement this simple, yet important part of a system.

An algorithm should replace repeating substrings of source string with a single instance of substring concatenated with the number of repetitions. If some substring should not be repeated, it is concatenated with number 1.

Your program must find the shortest possible compression of the given string.

Input file format

Output file format

Constraints

Sample tests

aaaaaaaaaa

a10

a c c c

a1 c3

abc

abc1