Problem A. Aquatic life ≡

Statement

Scientists of Nearsea Institute of Underwater Life obtained a picture of the mysterious aquatic life form. They wanted to determine the creature's species.

To do that, picture copies were distributed among N experts. Each expert made G_i guesses, each guess consisting of the name of the species and the score s_ij reflecting expert's level of confidence in the guess. For each expert, all guesses name different species.

You program must choose the species which received the highest total score from all experts.

In the first sample below "Ceramaster_arcticus" species received the total score of 14.

Input file format

Input file contains integer N on the first line, followed by N line blocks — one for each expert.

Each line block contains integer G_i, on the first line, followed by G_i lines — one for each guess.

Each guess line contains an integer s_ij followed by a string — guess score and species name. Names consist of Latin letters and underscores (ASCII 95). Names are case-sensitive ("a" and "A" are different names).

Output file format

Output file must contain names of all species with the score equal to the highest total score, one name per line, sorted lexicographically.

Constraints

1 ≤ N ≤ 100, 1 ≤ G_i ≤ 100, 1 ≤ s_ij ≤ 100

Species names contain from 1 to 50 characters.

Sample tests

3
2
5 Ceramaster_patagonicus
5 Ceramaster_arcticus 
3
7 Neoferdina_insolita
1 Neoferdina_glyptodisca
1 Ceramaster_arcticus 
2
8 Ceramaster_arcticus
2 Neoferdina_insolita

Ceramaster_arcticus

2
3
5 a
6 b
1 c
2
3 a
7 c

a
c

1
4
13 a
7 b
13 B
9 A

B
a

Problem B. Bottom of the sea ≡

Statement

The Nearsea Institute of Underwater Studies decided to make a survey of the sea bottom.

The area where the survey takes place is represented by a rectangular grid. The x axis runs from west to east and the y axis runs from south to north.

A robotic underwater vehicle is used to perform the survey. The vehicle has a program which allows him to cover a rectangular part of the sea bottom defined by the coordinates of its south-west and north-east corners.

Initially it was planned for a robot to submerge once and survey a single rectangular area with coordinates (a_x, a_y) − (b_x, b_y).

Suddenly, a representative of the Ministry of Defense showed up, and declared that the rectangular area with coordinates (c_x, c_y) − (d_x, d_y) contains secret military installations, and must not be visited by the vehicle.

It was decided to split the survey area into a smaller rectangles and perform a separate submersion for each of them. Rectangles must not intersect neither the restricted area nor each other and must cover all survey area except the restricted area.

Your program must find the splitting which requires minimal number of submersions.

Input file format

Input file contains 8 integers a_x a_y b_x b_y c_x c_y d_x d_y.

Output file format

Output file should contain minimum number of submersions M followed by M groups of 4 integers x_i y_i u_i v_i — coordinates of the south-east and north-west corners of the area which should be covered by i-th submersion. If there is more than one optimal solution, output any of them.

Constraints

Sample tests

-10 -10 10 10
0 0 20 20

2
-10 -10 10 0
-10 0 0 10

1 2 3 4
10 11 12 13

1
1 2 3 4

-1 -1 1 1
-2 -2 2 2

0

Problem C. Cthulhu spawn ≡

Statement

Scientists of the Nearsea Institute of Underwater Mythology are researching the mythical creature called Cthulhu.

The creature is famous for producing many offspring known as Cthulhu spawn. Each spawn has a small round body with N radially protruding appendages. Each appendage is either a tentacle or a claw.

Two spawns are considered identical, if one of them can be rotated in such a way that the sequence of tentacles and claws will coincide with the other spawn.

For example, if we designate tentacle by "T" and claw by "C", spawns "TCTCCT" and "CCTTCT" are identical and different from spawns "TTTCCT" ad "CCTTTC".

You program must, for given N, calculate the total number of different spawns with N appendages.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — number of different spawns.

Constraints

1 ≤ N ≤ 58

Sample tests

1

2

4

6

Problem D. Das mouse legacy ≡

Statement

The great and modern underwater city of R'Lyeh occupies vast area on the ocean floor. It is surrounded by R'Lyeh Ring Road (RRR) which separates business and cultural center from the rest of the city. The road itself is nothing more than a traffic pattern, which all underwater vehicles should obey.

The ocean floor around the city is flat, and vehicles can only crawl, not swim, so the road can be represented by a two-dimensional map.

Denizens of R'Lyeh built their first vehicles based on design brought to them by the famous explorers named Pinky and Brain, who visited R'Lyeh during their expedition to sunken "Titanic".

That design had one shortcoming — the vehicles were only able to turn to the right. Such a bizarre engineering solution had a serious impact on the design of RRR: it is possible to depart from any point on the road, make one or more circles around the business center and return to the starting point place, having visited all the road and making right turns only.

The traffic is one-way everywhere, so driving around R'Lyeh is simple. The only complication is a necessity to pass intersections. When passing an intersection, vehicles must move straight ahead (i.e. turns on intersections are forbidden).

Recent technical and magical advancements allowed R'Lyeh engineers to create a new class of vehicles, capable of turning either right or left. After providing all citizens with new vehicles, it became possible to convert some intersections into turn pairs (see picture) to further simplify the life in R'Lyeh. THe conversion must preserve the direction of traffic on each road segment.

The One Who Dreams in the Deep calls for your help. You must plan how to convert a maximum possible number of intersections into turn pairs, without breaking RRR connectedness.

Input file format

First line of the input file contains integers W H. Following H lines contain W symbols each and represent a map of R'Lyeh Ring Road.

Used symbols are: '│' (ASCII 179), '─' (ASCII 196), '┌' (ASCII 218), '└' (ASCII 192), '┘' (ASCII 217), '┐' (ASCII 191), '┼' (ASCII 197, represents intersection), ' ' (ASCII 32).

NOTE: the input files are in DOS (aka CPP866) encoding. Copying samples from the problem text will not work unless you convert the encoding. You can download actual input files for the samples here: Sample 1 Sample 2.

It is guaranteed that somewhere on the map there exists an area of business and cultural center, which is always seen by the right hand when moving along the RRR.

Output file format

First line of output file should contain an integer K — maximal number of crossings that can be converted into turn pairs.

Following K lines should contain a sequence of integer pairs, separated by spaces — coordinates of these crossings. Each pair consist of row and column numbers of input matrix respectively. Numeration starts from 0, so upper-left corner of input matrix has coordinates 0 0.

Constraints

2 ≤ W, H ≤ 20

Sample tests

4 12
            
            
  ┌────────┐
  └────────┘

0

5 9
         
      ┌┐ 
     ┌┼┼┐
     └┼┘│
      └─┘

2
2 6
2 7

Problem E. Elementary arithmetic ≡

Statement

Underwater arithmetic is very elementary. There are just two operations: WITH and WITHOUT which mean addition and subtraction respectively.

Underwater mathematicians did not yet invent brackets, so all expressions are calculated from right to left. For example, the expression 3 WITH 5 WITHOUT 4 WITHOUT 7 is calculated as (3 + (5 − (4 − 7))).

Scientists of Nearsea Institute of Underwater Arithmetic need a program to evaluate such expressions.

Input file format

First line of input file contains a single integer N. Following 2 × N + 1 lines describe the expression. Odd lines contain integer operands, even lines contain operations.

Output file format

Output file must contain a single integer — calculation result.

Constraints

1 ≤ N ≤ 10³

All operands are in range from 0 to 10³.

Sample tests

1
2
WITH
3

5

3
10
WITHOUT
5
WITH
3
WITH
15

-13

Problem F. Force of thrust ≡

Statement

The Force can have a strong influence on the weak-minded.

Engineers of Nearsea Laboratory of Swimming developed brand new underwater vehicle. To receive additional funding, they were advised to name it "nano-vehicle".

After some thought about how to justify such a name, young engineer Vasya suggested to start measuring the force of vehicle thrusters in nano-newtons.

The proposal was cheerfully accepted, and you were asked to write a thruster control program for this vehicle.

The vehicle has four thrusters located on its left, right, up and down sides. Their thrust forces are denoted by integer values f_L, f_R, f_U and f_D accordingly. Valid values of these forces are integers in the range from −10⁸ to 10⁸ nano-newtons. Positive values mean forward thrust, negative values — backward thrust.

Although all thrusters are parallel to each other, they still can be used to rotate the vehicle. For example, if f_L = −10⁸, f_R = 10⁸, f_U = f_D = 0, then the vehicle turns left. If f_L = f_R = f_U = f_D = 10⁸, then the vehicle goes forward at full speed.

For the human controller, instead of directly setting each thrust force, it is easier to specify total thrust T, horizontal torque H and vertical torque V, which are defined as follows:

• T = f_L + f_R + f_U + f_D
• H = f_R − f_L
• V = f_U − f_D

Your program must, given the values of T, H and V, calculate valid values of f_L, f_R, f_U and f_D.

Input file format

Input file contains three integers T H V.

Output file format

Output file must contain four integers (valid thrusts) f_L f_R f_U f_D. If there are several solutions, output any of them. It is guaranteed that at least one solution exists.

Constraints

 −4*10⁸≤ T ≤ 4*10⁸;

 −2*10⁸≤ H, V ≤ 2*10⁸;

Sample tests

0 10 0

-5 5 0 0

10 0 2

5 5 1 -1

Problem G. Group performance ≡

Statement

Multi-vehicle cooperation is a hot topic in contemporary underwater robotics. Often a group of vehicles can finish the mission faster than just one. But you have to implement sophisticated control techniques to benefit from the cooperation.

Consider N vehicles and M tasks they should accomplish. Each task should be accomplished by exactly one vehicle. Each task is a track that a vehicle should follow. The task number i is defined by two edge points a_i and b_i, and length d_i (d_i ≥ |a_i − b_i|).

Vehicle is allowed to follow a track in any direction — either from a_i to b_i or from b_i to a_i. In both cases the length of the path will be d_i.

A plan is a sequence of tasks for each vehicle in order of execution. Every task in the plan is followed either in direct order (a to b) or in reverse order (from b to a). Each task should appear exactly once in the whole plan.

The j-th vehicle has a starting point s_j. Vehicle executes its tasks according to its part of a plan. When a vehicle accomplishes one task, it goes to the start point of the next one, moving along the straight line. When all tasks assigned to a vehicle are done, it stops. Vehicle path length is a total path traveled by the vehicle during the plan execution. Plan length is a maximal vehicle path length of all vehicles in the plan.

Your program must, given vehicles and tasks, find a plan of minimal length.

Assume that vehicles operate on a plane (plane of constant depth) and that the vehicle size may be ignored.

Input file format

Each point in the input file is described with two integers — its x and y coordinates.

On the first line of input file there are integers N M. Following N lines describe starting points s_i.

Next M lines describe tasks, each task descriptions consisting of points a_i, b_i and path length d_i.

Output file format

Output file must describe a plan of minimal length. If there several such plans, output any of them.

Plan description consists of N blocks, each describes a sequence of tasks for one vehicle. j−th block starts with non-negative integer num_j, followed by num_j pairs (t_jk, dir_jk). Here t_jk denotes a number of k-th task for j-th vehicle, it is an integer in range 1..M. The dir_jk is either 0 or 1: 0 stands for passing t_jk from a to b, 1 stands for passing t_jk from b to a.

Constraints

1 ≤ N, M≤ 10; 0 ≤ d_i ≤ 10⁴;

All coordinates are integers in range 0..10³.

Sample tests

3 4
2 8
2 5
2 2
5 2  12 2  14
14 7  12 9  3
12 4  5 6  14
5 7  10 8  10

2 4 0 2 1
1 3 1
1 1 0

Problem H. Hall of water life ≡

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x₁, …, x_N from the hall entrance (x_i < x_i + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers x_i.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

Problem I. Ichthyology ≡

Statement

Scientists of Nearsea Institute of Linguistic Ichthyology study the fish language. They found few specific sounds which some fishes can emit, and assign letters of Latin alphabet to them. Then they took an underwater sound record and used state-of-the-art pattern recognition software to convert it into a string of letters.

They hypothesize that one sub-string of letters may have particular meaning in the fish language (sand so serve as a kind of "word"), and so they want to calculate how often that sub-string may have been used during the record.

You program must, given the strings T and W, find minimum and maximum number of non-overlapping occurrences of W in T.

For example, if W="abab" and T="ababbbabababab", the string may be interpreted as "(abab)bb(abab)(abab)" (giving 3 occurrences) or as "(abab)bbab(abab)ab" (giving 2 occurrences). So, the minimal number is 2 and the maximum is 3.

Input file format

First line of input file contains string W. Second line of input file contains string T.

Output file format

Output file should contain two integers — minimum and maximum number of non-overlapping occurrences of W in T.

Constraints

1 ≤ length(W) ≤ 100;

1 ≤ length(T) ≤ 1000;

W and T contain small Latin letters only.

Sample tests

a
b

0 0

qq
qqaqqqaqqqq

3 4

Problem J. Jewel trade ≡

Statement

Recently, explorers have discovered a new species of giant sentient squids living at the bottom of a deep lake.

Squids are generally uninterested in dealing with humans. However, they showed appreciation for various jewels, especially diamonds, which are hard to find under water. In exchange, squids offered a wide selection of high-quality pearls.

So the trade was established. Each day, N different kinds of jewels were traded, some from the surface into the water, and some out of the water to the surface.

The Squid State Trading Commission established following rules:

1. Each jewel mush be enclosed in a separate container.
2. Jewels of the same kind must have identical containers.
3. The trade must not alter the water level of the lake, so the total volume of all containers moved into the lake must be equal to the total volume of all containers moved to the surface.

You program must find the volume of the container for each kind of jewel, so as to satisfy commission's requirements.

Input file format

Input file contains an integer N followed by N integers a_i, where a_i > 0 means that a_i jewels of i-th kind are moved from the surface to the lake, and a_i < 0 means that |a_i| jewels of i-th kind are moved from the lake to the surface.

Output file format

Output file must contain N integers b_i (1 ≤ b_i ≤ 10¹²), indicating the volume of containers for each kind of jewel. If there are several acceptable solutions, output any of them.

Constraints

2 ≤ N ≤ 10⁵

1 ≤ |a_i| ≤ 10⁵

2 × min(pos, neg) ≥ max(pos, neg), where pos is the number of positive values among a_i and neg is the number of negative values.

Sample tests

3
1 2 -3

1 1 1

5
20 -27 48 -17 6

5 13 8 11 9