Matrix Multiplication

Time limit2sMemory limit512 MB

Summary

For each prefix of n matrices, decide whether some multiplication order is valid, and if so report the largest possible area of the final product.

Level: Hard8 of 10
Topics: Greedy, Sorting, Implementation, Math
Solved: No attempts yet

Problem

You are given $n$ matrices $M_1, M_2, \dots, M_n$ . Matrix $M_i$ ( $i = 1, 2, \dots, n$ ) has $R[i]$ rows and $C[i]$ columns ( $R[i] \times C[i]$ ).

For an integer $i$ ( $1 \le i \le n$ ), you want to compute the value $V_i$ defined as follows.

First, determine whether there is an order in which all $i$ matrices $M_1, M_2, \dots, M_i$ can be multiplied. In matrix multiplication, to multiply an $R \times C$ matrix by an $R' \times C'$ matrix, we need $C = R'$ , and the resulting matrix is $R \times C'$ . If the $i$ matrices cannot be multiplied even when their order is rearranged freely, define $V_i = 0$ . If they can, find the method that makes the final resulting matrix as large as possible, and the size of the resulting matrix (number of rows $\times$ number of columns) is the value $V_i$ .

Compute $V_1, V_2, \dots, V_n$ .

Input

The first line contains the natural number $n$ ( $1 \le n \le 1{,}000$ ). The next $n$ lines each contain two integers, the number of rows $R[i]$ and the number of columns $C[i]$ of each matrix. The number of rows and columns of each matrix is between 1 and 1,000 inclusive.

Output

Output $n$ lines in total, and on each line output the value $V_i$ from $V_1$ to $V_n$ .

Examples5

Example 1
Input
```
3
8 2
2 8
2 2
```
Expected output
```
16
64
64
```
Example 2
Input
```
3
4 9
9 1
9 9
```
Expected output
```
36
4
4
```
Example 3
Input
```
3
4 10
10 1
10 6
```
Expected output
```
40
4
0
```
Example 4
Input
```
3
10 3
3 10
5 5
```
Expected output
```
30
100
0
```
Example 5
Input
```
4
1 1
1 1
1 1
1 1
```
Expected output
```
1
1
1
1
```