Gigel is a Mathematics professor, but at one point of his existence he came to the conclusion that he has to set up his own business. Therefore, Gigel set up a company that deals with apartment rentals. His company prospered, so that now Gigel's company has many apartments available and makes a lot of transactions. Offers and requests are so numerous that Gigel decided that in order to effectively respond to his clients' demands he has to write a program.
First of all, Gigel took a map of the area and drew on it a grid, to be able to easily identify the buildings where the company has apartments for rent. Doing this he obtained a matrix with n lines (numbered from 1 to n) and m columns (numbered from 1 to m), the location of a building being identifiable by the line and column number where it is located.
Rent for apartments located in the same building is the same. So Gigel must store for each building the number of available apartments and the amount of rent.
Gigel needs a program that effectively executes the following operations:
1. renting an apartment;
2. clearing an apartment;
3. determining total income obtained from rentals in a given rectangular area.
Task
Write the program Gigel needs!
Input Data
Input file firma.in contains:
– on line one, positive integers n and m, separated by a space, representing the number of lines, and respectively of columns on the map;
– on line two, positive integer p, representing the number of buildings;
– each of the following p lines contains information regarding a building, under form x y nrmax nr pret, meaning "the building is located on line x, column y, has nrmax apartments for rent, of which nr are already rented, rent for each being $pret";
– the next line contains positive integer O, representing the number of operations being executed;
– each of the following O lines describes an operation; a line describing an operation begins with a positive integer, representing the type of operation (1, 2 or 3).
If it is a type 1 operation, two positive integers x and y follow, separated by a space, representing the location of the building where an apartment is being rented (if said position doesn't contain any building or there are no more free apartments in said building, the operation will be ignored).
If it is a type 2, operation, two positive integers x and y follow, separated by a space, representing the location of the building where an apartment is being cleared (if said position doesn't contain any buildings or there are no rented apartments in the building, the operation will be ignored).
If it is a type 3 operation, four positive integers x1 y1 x2 y2 follow; (x1, y1) and (x2, y2) represent coordinates (line, column) of two opposite corners of a rectangular area on the map (this operation determines total income obtained from rentals in that area and displays it in the output file).
Output Data
Output file firma.out will contain one line for each type 3 operation from the input file, line on which the income calculated from said operation will be written. The input file order of operations will be maintained.
Constraints and Statements
| firma.in | firma.out |
| 4 5 3 2 2 50 5 10 4 2 70 0 15 3 5 20 2 4 12 3 1 2 4 4 1 1 4 1 2 2 2 3 5 2 3 5 1 4 2 3 4 1 2 5 2 1 1 2 3 5 1 3 5 1 4 2 3 4 5 3 1 |
50 |
Time limit: 0.7 seconds/test
prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com