## Problem A. ACM Rank Table ≡

 Author: A. Klenin Input file: input.txt Time limit: 2 sec Output file: output.txt Memory limit: 16 Mb

### Statement

ACM contests, like the one you are participating in, are hosted by the special software. That software, among other functions, preforms a job of accepting and evaluating teams' solutions (runs), and displaying results in a rank table. The scoring rules are as follows:

1. Each run is either accepted or rejected.
2. The problem is considered solved by the team, if one of the runs submitted for it is accepted.
3. The time consumed for a solved problem is the time elapsed from the beginning of the contest to the submission of the first accepted run for this problem (in minutes) plus 20 minutes for every other run for this problem before the accepted one. For an unsolved problem consumed time is not computed.
4. The total time is the sum of the time consumed for each problem solved.
5. Teams are ranked according to the number of solved problems. Teams that solve the same number of problems are ranked by the least total time.
6. While the time shown is in minutes, the actual time is measured to the precision of 1 second, and the the seconds are taken into account when ranking teams.
7. Teams with equal rank according to the above rules must be sorted by increasing team number.

Your task is, given the list of N runs with submission time and result of each run, compute the rank table for C teams.

### Input file format

Input contains integer numbers C N, followed by N quartets of integes ci pi ti ri, where ci — team number, pi — problem number, ti — submission time in seconds, ri — 1, if the run was accepted, 0 otherwise.

### Output file format

Output file must contain C integers — team numbers sorted by rank.

### Constraints

1 ≤ C, N ≤ 1000, 1 ≤ ciC, 1 ≤ pi ≤ 20, 1 ≤ ti ≤ 36000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 3
1 1 5000 0
1 1 500 1
2 1 10000 1

1 2
2
3 3
1 2 3000 0
1 2 3100 1
2 1 4200 1

2 1 3

## Problem B. Sales Report ≡

 Author: A. Klenin Input file: input.txt Time limit: 4 sec Output file: output.txt Memory limit: 16 Mb

### Statement

The Unknown Trading Company have installed a new inventory-tracking system, which stores a complete database of goods and trading points worldwide. Each salespoint and each item was assigned an integer unique identifier (id). For every sale, the system logs id of the item, number of items sold, and id of the salespoint.

Your task is to output a summary report, tabulating total sales by items and salespoints. The report must be a two-dimensional table, with the first row containing item ids in increasing order, first column containing salespoint ids in increasing order, and values inside the table representing total sales of corresponding item from the corresponding salespoint. The value in first column of the first row must be −1. The values in cells without corresponding sales must be 0.

### Input file format

Input contains number of records N, followed by N triplets of integers qi si vi, where qi — item id, si — salespoint id, vi — number of items sold.

### Output file format

Output file must a table as described above, row-by-row.

### Constraints

1 ≤ N ≤ 500000, 1 ≤ qi, si, vi ≤ 109, the summary table will have no more than 108 cells, the summary value in each cell will not exceed than 231−1.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4
10 1 3
20 2 5
10 2 2
20 2 1

-1 10 20
1 3 0
2 2 6
2
1
1 1 5

-1 1
1 5

## Problem C. Random Gap ≡

 Author: A. Klenin Input file: input.txt Time limit: 8 sec Output file: output.txt Memory limit: 2 Mb

### Statement

The pseudo-random number genegators (or RNGs for short) are widely used in statistical calculations. One of the simplest and ubiquitious is the linear congruence RNG, that calculates the n-th random number Rn as Rn = (aRn - 1 + c) mod m, where a, c and m are constants. For example, the sequence for a = 15, c = 7, m = 100 and starting value R0 = 1 is 1, 22, 37, 62, 37, 62, ...

Linear RNG is very fast, and can yield surprisinly good sequence of random numbers, given the right choice of constants. There are various measures of RNG quality, and your task is to calculate one of them, namely the longest gap between members of the sequence. More precisely, given the values of a, c, m, and R0, find such two elements Ri < Rj that:

1. there are no other Rk RiRkRj,
2. the difference RjRi is maximal.

### Input file format

Input file contains integer numbers a c m R0.

### Output file format

Output file should contain the single number — the maximal difference found.

### Constraints

0 ≤ a, c, R0 ≤ 107, 1 ≤ m ≤ 16000000, am + c < 232.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
15 7 100 1
25
2
2 0 127 5
26

## Problem D. Radio Coverage ≡

 Author: B. Vasilyev, A. Klenin Input file: input.txt Time limit: 5 sec Output file: output.txt Memory limit: 4 Mb

### Statement Radio station 'ACM Rock' is broadcasting over the circular area with center in point (x0, y0) and radius R. In order to increase the auditorium, it were suggested to build several relay stations. N locations were selected as candidate sites for relay stations. Relay station placed in i-th location will cover a circular area with center in point (xi, yi) and radius ri, where center lies inside the area covered by the base station, (x0 - xi)2 + (y0 - yi)2R2.

Your task is to select a subset of sites for relay stations so that:

1. the covered areas for relays do not intersect (but may touch) one another,
2. the total area covered by base station and all relays is maximum possible.

### Input file format

Input file contains integer number N followed by real numbers x0 y0 R, followed by N triples of real numbers xi yi ri.

### Output file format

Output file should contain a single real number — the maximal coverage area with the absolute error less than 10−2.

### Constraints

1 ≤ N ≤ 10, 0 ≤ xi, yi, x0, y0 ≤ 1000, 1 ≤ riR ≤ 1000.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1 0 0 10
10 0 10
505.4816

## Problem E. Circle Drawing ≡

 Author: A. Klenin Input file: input.txt Time limit: 3 sec Output file: output.txt Memory limit: 4 Mb

### Statement

Graphics libraries usually implement drawing of graphics primitives, like lines, polygons and circles. Your task is to write a program that draws circles.

Graphic canvas is represented as an array of Xsize by Ysize pixels. Each pixel have a color ranged from 0 to 9. Initially all pixels have color 0. Pixels are thought of as small sqares with the side of length 1. A circle with center (xc, yc) and radius R is a set of pixels (x, y) satisfying the inequality (xxc)2 + (yyc)2R2

To draw a circle, your program should set the color of all pixels in a set defined above to the color of the circle. After drawing N given circles, the program should output the color of all pixels of the canvas.

### Input file format

Input file contains numbers Xsize Ysize N followed by N sets of numbers xi yi Ri ci, describing the coordinates of center, radius and color of i-th circle.

### Output file format

Output file should contain Ysize lines of Xsize characters each, where i-th character of j-th line is a digit corresponding to color of the pixel (i, j).

### Constraints

1 ≤ Xsize, Ysize ≤ 1000, 1 ≤ N ≤ 10000, 0 ≤ xi < Xsize, 0 ≤ yi < Ysize, 1 ≤ Ri ≤ 200, 0 ≤ ci ≤ 9.

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 5 1
2 2 1 3
00000
00300
03330
00300
00000
2
4 3 2
2 2 2 5
0 1 1 9

9050
9955
9555

## Problem F. Harder Sokoban Problem ≡

 Author: A. Klenin Input file: input.txt Time limit: 5 sec Output file: output.txt Memory limit: 16 Mb

### Statement

The game of sokoban is played in a rectangular labirinth of N by N cells with each cell either empty, denoted by '.' character (ASCII 46), or occupied by wall, denoted by '#' character (ASCII 35). There is also a single destination cell, denoted by '*' character (ASCII 42).

One player and one container are located in the empty cells of the labirinth. The player can move between the empty cells in horizontal or vertical direction. If the cell where the player tries to move is occupied by container, the container is "pushed" to the next cell in the same direction. That next cell must, of course, be empty.

The objective of the game is well-known: to place the container in the destination cell with the minimum number of moves. Your task, however, is different: given the field, select starting position for the player and the container so as to maximize the required number of moves.

### Input file format

First line of input contains number N — the field size. The following N lines consist of N characters each — representation the field. The input field always contains at least one empty cell adjacent to the destination cell.

### Output file format

Output file must contain a single integer — the maximal number of moves.

2 ≤ N ≤ 25

### Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
..
.*
0
2
3
..#
...
..*
10

0.091s 0.004s 19