Niebieskie ksi.eczki
VIII Olimpiada Informatyczna 2000/2001

Task: BAN
Author: Marcin Kubica

III Stage contest, the second day  

There are four currencies in Byteland. These are: denary, frank, grosz and taler. They are not convertible (i.e. one cannot exchange one currency into another) and this is a serious disadvantage for the inhabitants of Byteland. The Byteland Bank of Business (short BBB), due to mistake between currencies, has faced the view of bankruptcy. It had made several contracts on giving credits. All of the contracts are of the following form:

BBB does not have enough money to fulfill all its clients needs, whereas no client will pay back his credit before he gets all the money he needs. BBB asked The Byteland National Bank (short BNB) for help. BNB agreed to help BBB, but requested the detailed report on minimal amount of money in each currency sufficient for BBB to make every client pay back his credit. The experts from BBB discovered that there are many possible solutions for the problem (see example). BNB replied that they are interested in any of them. BNB requests four integers - the amount of money in each official currency of Byteland that all together would suffice BBB to make every client give back his credit, but if BBB would have 1 less in any of the currencies and the same amount in the remaining currencies it would be not enough to be sure BBB can end up all the credits.


Write a program which:

If there are many possible answers, your program should write any of them.


In the first line of the text file BAN.IN there is written one positive integer n equal to the number of clients, 1<=n<=8 000. The clients are numbered from 1 to n. In each of the following n lines there are written eight nonnegative integers. In the (i+1)-th line (i = 1,...,n) there are written integers mi,1,mi,2,mi,3,mi,4,wi,1,wi,2,wi,3,wi,4, (0<=wi,j<=mi,j<=50 000, for j=1,...,4). Integers mi,j and wi,j denote respectively credit limit and current credit of client number i in: denars (j=1), francs (j=2), groszes (j=3) and talers (j=4).



Your program should write in the first and only line of the text file BAN.OUT four nonnegative integers separated by single spaces. They should denote the minimal amounts of money BBB needs in denars, francs, groszes and talers respectively.



For the input file BAN.IN:

3 2 1 2 0 2 0 1
2 4 1 8 1 2 1 1
3 2 0 3 1 0 0 1
3 0 1 2 1 0 0 1

the correct answer might be the text file BAN.OUT:

1 2 0 7


2 0 1 4