행렬 곱셈

$n$개의 행렬 $M_1, M_2, \dots, M_n$이 주어진다. 행렬 $M_i$ ($i = 1, 2, \dots, n$)는 $R[i]$개의 행과 $C[i]$개의 열을 가진다 ($R[i] \times C[i]$).

정수 $i$ ($1 \le i \le n$)에 대해 다음 값 $V_i$를 계산하려고 한다.

먼저, $i$개의 행렬 $M_1, M_2, \dots, M_i$를 모두 곱할 수 있는 순서가 있는지 알아본다. 행렬 곱셈에서 $R \times C$ 행렬과 $R' \times C'$ 행렬을 곱하려면 $C = R'$이어야 하고, 결과는 $R \times C'$ 행렬이다. $i$개의 행렬을 순서를 자유롭게 재배치하더라도 곱하는 것이 불가능하면 $V_i = 0$으로 정의한다. 가능하면, 가능한 모든 방법 중 최종 결과 행렬의 크기가 가장 커지는 방법을 찾아, 그때 결과로 나온 행렬의 크기 (행의 수 $\times$ 열의 수)가 $V_i$ 값이 된다.

$V_1, V_2, \dots, V_n$을 구해보자.

첫째 줄에는 자연수 $n$이 주어진다 ($1 \le n \le 1{,}000$). 다음 $n$줄에는 각 줄에 정수 두 개가 주어지는데, 각 행렬의 행의 수 $R[i]$와 열의 수 $C[i]$이다. 각 행렬의 행의 수와 열의 수는 1 이상 1,000 이하이다.

총 $n$줄을 출력해야 하고, 각 줄에는 $V_1$부터 $V_n$까지 $V_i$ 값을 출력한다.