전국시대 timer 4초 memory 8MB

정올 대륙은 큰 강을 따라 작은 규모의 국가들이 일렬로 길게 늘어서 있다. 

이 대륙은 강의 상류에서부터 하류까지의 모든 나라들이 강을 공유하고 있기 때문에, 상류에 있는 나라들이 버린 폐수가 강으로 흘러 들어가, 강 하류 사람들이 피해를 보는 경우가 있다.

하류 국가들은 이러한 피해를 명분 삼아 상류 국가들에게 전쟁을 선포하는 경우가 많다.

그러나 국가의 크기가 작기 때문에 하나의 국가로써 전쟁하는 것은 불리할 수가 있으므로,  인접한 주변 국가들을 끌어들여 연합을 결성한 후에야 전쟁을 선포한다.

이에 맞서 상류 국가들도 인접한 국가끼리 연합을 맺어, 결국에는 상류 연합 대 하류 연합의 구조를 띠게 된다.

N개의 국가들은 강의 제일 상류에 있는 국가부터 순서대로 a₁, a₂, … a_N의 군사력을 가지고 있다.

강 하류에 위치한 j번째 국가가 인접한 국가들끼리 동맹을 맺어 s번째부터 e번째까지의 국가끼리 연합하게 되면,  이들의 총 군사력은 a_s+a_s+1+…a_j+…a_e-1+a_e이다. 

이에 맞서는 i번째 국가가 인접한 국가들끼리 동맹을 맺어 l번째부터 r번째까지의 국가끼리 연합하게 되면, 

마찬가지의 계산법으로 a_l+a_l+1+…a_i+…a_r-1+a_r의 군사력을 가지게 된다.  

두 연합간의 대결은 단순히 총 군사력이 큰 연합이 이기게 된다. 

만약 상류의 i번 국가를 필두로 한 연합이 이긴다면, 그 결과로, j국가의 군사력 a_j의 반절을 떼어 a_i에 더하게 된다.

마찬가지로, 하류 국가 연합이 이긴다면, a_i의 반절을 a_j에 뺏기게 된다.  (여기서 x의 반절이라 함은, x/2를 반올림한 값을 말한다.) 

만약 두 연합의 군사력이 같다면, 무승부로 끝나고 아무 일도 일어나지 않는다.

초기 상태의 모든 나라의 군사력이 주어지고, 현재까지 일어난 모든 전쟁이 어느 연합 대 어느 연합이었는지에 대한 기록이 모두 주어질 때,  현재 각 나라의 군사력을 모두 출력하는 프로그램을 작성하라.​