Problem A. Advanced ASCII Cubes ≡

Statement

The table surface is divided into N by M square cells. Some cubes are stacked one upon another over the cells, forming towers. For each cell the number of cubes stacked over it is given in the matrix A.

Your program must output the view of the table in ASCII graphics, where each cube is represented as shown below:

  +---+
 /   /|      
+---+ |      
|   | + 
|   |/ 
+---+

Input file format

Output file format

Constraints

Sample tests

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

........+---+..........
......+/   /|-+---+---+
...../+---+ |/   /   /|
....+-|   | +---+---+ |
.../  |   |/   /   /| +
..+---+---+---+---+ |/.
./   /   /   /   /| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......

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

......+---+---+...+---+---+
..+---+  /   /|../   /   /|
./   /|-+---+ |.+---+---+ |
+---+ |/   /| +-|  /   /| +
|   | +---+ |/+---+---+ |/|
|   |/   /| +/   /   /| + |
+---+---+ |/+---+---+ |/| +
|   |   | +-|   |   | + |/.
|   |   |/  |   |   |/| +..
+---+---+---+---+---+ |/...
|   |   |   |   |   | +....
|   |   |   |   |   |/.....
+---+---+---+---+---+......

Problem B. 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

Задача C. Ближайшее число - 1 ≡

Условие

Дан массив A, состоящий из N неотрицательных целых чисел.

Назовём правым (левым) соседом нулевого элемента ближайший к нему справа (слева) ненулевой элемент.

Требуется построить массив B, который получается из массива A заменой каждого нулевого элемента на его ближайшего соседа в массиве A. Если оба соседа отсутствуют либо расстояния до них равны, замена не производится (элемент остаётся нулевым).

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
0 0 1 0 2

1 1 1 0 2

4
8 0 0 6

8 8 6 6

Problem D. Ganking ≡

Statement

Popular on-line game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.

Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.

Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:

• the victim only attacked players from set G, and
• players from set G attacked and were attacked only by the victim.

Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.

Input file format

Input file contains integers N T followed by N quartets of integers t_i a_i v_i k.

Output file format

Output file must contain 10 integers — the numbers of ganks for each player.

Constraints

1 ≤ N ≤ 10000, 1 ≤ t_i ≤ t_i+1 ≤ 10⁵, 1 ≤ T ≤ 10⁵. Either 1 ≤ a_i ≤ 5 < v_i ≤ 10 or 1 ≤ v_i ≤ 5 < a_i ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

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

0 1 2 0 0 0 0 1 0 0 

Problem E. Expression with period ≡

Statement

An expression for a function is composed of single-digit numbers, variable x, signs + and *, and zero or one calls to function sin. More formally:

• expression ::= 0|1|2|3|4|5|6|7|8|9|x
• expression ::= expression+expression
• expression ::= expression*expression
• expression ::= sin(expression)

Function f(x) has period p if f(x+p) = f(x) for all x.

Your program must, given an expression with no more than one call to sin, determine the minimal period of a function.

Input file format

The input file contains a single string — expression.

Output file format

Output file must contain single a floating point number — period with relative error not greater than 10⁻⁶. If a function is constant or aperiodic, output number 0.

Constraints

Expression length is between 1 and 25 characters. There are no spaces in expression.

Sample tests

sin(x)+x

0

5*6*sin(2*x+5+x*7+x)+1

0.62831853

sin(x*0)

0

Problem F. Fireworks ≡

Statement

You task is to display a firework in ASCII graphics. A firework consists of one or more explosions called breaks. Each break has an integer radius R and a level L and is displayed by '*' (ASCII 42) character at the center and 8 rays: 4 horizontal ('-', ASCII 45) and vertical ('|', ASCII 124) rays, each R + E characters long (where E is an additional parameter equal for all breaks); 4 diagonal ('/', ASCII 47 and '\', ASCII 92) rays, each R characters long. If the level of the break is greater then 1, at the end of each horizontal and vertical ray a new "child" break of radius R − 1 and level L − 1 is located. Child break has only 7 rays, because the ray in the direction leading to the "parent" break is not drawn. A firework starts from a single break. It must be output as a square of characters, having minimal size sufficient to display all the breaks. Characters not belonging to any break must be output as '.' (ASCII 46). Characters belonging to more than one break must be output as 'x' (ASCII 120).

Input file format

Input file contains integers L R E — level and radius of the initial break and the additional horizontal/vertical rays length.

Output file format

Output file must contain display of a firework.

Constraints

1 ≤ L ≤ R ≤ 10, 1 ≤ E ≤ 20

Sample tests

1 1 1

..|..
.\|/.
--*--
./|\.
..|..

2 4 1

..........|..........
.......\..|../.......
........\.|./........
.........\|/.........
......----*----......
........./|\.........
....|.\./.|.\./.|....
.\..|..x..|..x..|../.
..\.|./.\.|./.\.|./..
...\|/...\|/...\|/...
----*-----*-----*----
.../|\.../|\.../|\...
../.|.\./.|.\./.|.\..
./..|..x..|..x..|..\.
....|./.\.|./.\.|....
.........\|/.........
......----*----......
........./|\.........
......../.|.\........
......./..|..\.......
..........|..........