은행

바이트랜드에는 네 가지 화폐가 있다. 데나르, 프랑, 그로시, 탈러이다. 서로 환전할 수 없어서 이 나라 사람들에게는 큰 불편이다.

바이트랜드 비즈니스 은행(BBB)은 많은 신용 계약을 맺었는데, 화폐를 혼동하는 바람에 파산 위기에 놓였다. 모든 계약은 다음과 같이 동작한다.

• 계약은 네 화폐 각각에 대해 고객의 신용 한도를 정한다.
• 고객은 원할 때 언제든 어떤 화폐로든 신용의 일부를 요청할 수 있다. 은행에 기한은 없지만, 고객이 모든 화폐에서 한도를 넘지 않는 한 요청한 돈은 언젠가 반드시 지급되어야 한다.
• 한도를 다 쓰지 않은 고객은 계속 추가로 요청할 수 있다.
• 마지막에 고객은 빌린 돈을 모두 되갚는다. 여기에도 기한은 없지만 언젠가는 갚는다.
• 고객이 한도를 전부 쓸 필요는 없으며, 이자나 수수료도 없다.

BBB는 모든 고객의 요구를 한꺼번에 맞출 수 없고, 어떤 고객도 원하는 돈을 전부 받기 전에는 아무것도 갚지 않는다. 따라서 BBB는 최악의 경우에도 고객을 한 명씩 차례로 처리할 수 있도록 각 화폐에 충분한 준비금을 보유해야 한다. 한 고객을 처리한다는 것은 네 화폐 모두에서 그 고객을 한도까지 채워 주는 것이며, 이는 현재 준비금이 그 고객의 남은 필요액(한도에서 현재 신용을 뺀 값)을 네 화폐에서 동시에 감당할 수 있을 때에만 가능하다. 한도까지 채워진 고객은 빌린 돈을 모두 되갚고, 그 돈은 준비금으로 돌아온다.

BBB는 바이트랜드 국립은행(BNB)에 도움을 청했다. BNB는 BBB가 모든 고객에게 빚을 갚게 만들기에 딱 충분한 준비금, 즉 화폐마다 하나씩 네 정수를 알고 싶어 한다. 이 준비금이면 어떤 순서로든 모든 고객을 처리할 수 있지만, 네 화폐 중 어느 하나라도 $1$을 줄이면(나머지 셋은 그대로 두고) 처리가 불가능해져야 한다.

이런 준비금은 여러 개일 수 있다. 답을 유일하게 만들기 위해 사전순으로 가장 작은 것을 출력한다. 즉 데나르 준비금을 먼저 최소화하고, 그다음 프랑, 그다음 그로시, 마지막으로 탈러 준비금을 최소화한다.

첫째 줄에 고객 수 $n$이 주어진다 ($1 \le n \le 8000$). 고객은 $1$번부터 $n$번까지 번호가 매겨진다.

이어지는 $n$개의 줄에는 각각 여덟 개의 음이 아닌 정수 $m_{i,1}, m_{i,2}, m_{i,3}, m_{i,4}, w_{i,1}, w_{i,2}, w_{i,3}, w_{i,4}$이 주어지며 $0 \le w_{i,j} \le m_{i,j} \le 50000$을 만족한다. 여기서 $m_{i,j}$는 신용 한도, $w_{i,j}$는 고객 $i$의 현재 신용이고, $j=1$은 데나르, $j=2$는 프랑, $j=3$은 그로시, $j=4$는 탈러를 뜻한다.

음이 아닌 네 정수를 한 줄에 공백 하나로 구분하여 출력한다. 순서대로 데나르, 프랑, 그로시, 탈러의 최소 준비금이다. 이 준비금은 BBB가 모든 고객에게 빚을 갚게 만들 수 있어야 하고, 네 값 중 어느 하나라도 $1$을 줄이면 부족해져야 한다. 그런 준비금이 여러 개이면 사전순으로 가장 작은 것을 출력한다(데나르 값을 먼저 비교하고, 그다음 프랑, 그로시, 탈러 순).