더 저렴하게 먹기

호는 비밀 출장을 위해 어느 비밀스러운 장소에 도착했다. 출장은 최대 $N$일 이하로 끝난다는 것은 알고 있지만, 정확히 며칠 동안 머무를지는 모른다. 완벽주의자인 호는 1일부터 $N$일까지 가능한 모든 출장 기간에 대해 날마다의 식사 목록을 만들고 싶어 한다. 이 비밀스러운 장소에는 우연히도 정확히 $2N$종류의 메뉴를 파는 식당이 하나 있다. 이 식당은 점심 시간과 저녁 시간에만 문을 연다. 같은 메뉴라도 점심 가격과 저녁 가격이 다를 수 있다. 호는 매일 점심과 저녁에 메뉴를 하나씩 먹고, 출장 기간 내내 같은 메뉴를 두 번 먹지 않는다. 호는 어떤 메뉴를 먹는지에는 신경 쓰지 않으며, 중요한 것은 식사 금액의 합이 최소가 되는 것뿐이다. 이런 조건에서 식사 목록을 적을 수는 있지만, $N(N+1)$개의 메뉴를 모두 적는 것은 번거롭고 힘든 일이다. 그래서 호는 식사 목록을 만드는 대신, $i$개의 점심 메뉴와 $i$개의 저녁 메뉴를 먹을 때의 최소 합계 금액을 $i$가 1부터 $N$까지인 경우마다 계산한다. 호의 열성 팬인 당신의 임무는 호가 계산한 $N$개의 금액을 출력하는 것이다.

첫 줄에 정수 $N$이 주어진다. 이어지는 $2N$개의 줄에는 각각 정수 $l$과 $d$가 주어지며, 이는 해당 메뉴의 점심 가격과 저녁 가격이다.

$N$줄을 출력한다. $i$번째 줄($1 \leq i \leq N$)에는 점심 메뉴 $i$개와 저녁 메뉴 $i$개를 먹을 때의 최소 합계 금액을 정수로 출력한다.

$1 \leq N \leq 250\,000$이고 $1 \leq l, d \leq 10^9$이다.