|Input file name:||matrices.in|
|Output file name:||matrices.out|
|Time limit:||2 s|
|Memory limit:||64 megabytes|
Pete often spends his free time solving hard mathematical problems. Few days ago he solved one. The solution of this problem was written on more than one hundred sheets of paper!
But now he has found that some of these sheets had been lost. He does not know what to do! There was a hardest work done on the lost sheets – there were calculated and then multiplied lots of matrices.
Pete has found calculated matrices in his drafts but he has forgotten how they were multiplied. Help Pete! Write a program which given a set of matrix dimensions will output one of the possible ways to multiply them all to get one matrix.
There is a total number of matrices M in the first line of input file (1≤ M≤ 32000). The next M lines contain two numbers each, ri and ci which are numbers of rows and columns in i-th matrix respectively. It is guaranteed that all ri and ci are in range from 1 to 3000.
Display exactly M lines corresponding to order in which the matrices may be multiplied. Each line contains numbers of columns and rows (separated by one space) in the j-th matrix of the product. Output in the first line one word "IMPOSSIBLE" if there are no ways to compose the product.
|2 2 1 1 2||1 2 2 1|
|2 1 2 3 4||IMPOSSIBLE|
Source: Petrozavodsk training camp, Summer 2002. Startup contest
Author: Andrew Lopatin, Nick Durov
Discuss Submit a solution