0033. Matrices

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.

Input file

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, r_i and c_i which are numbers of rows and columns in i-th matrix respectively. It is guaranteed that all r_i and c_i are in range from 1 to 3000.

Output file

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.

Examples:

matrices.in	matrices.out
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



Printable version