0033. Matrices

Имя входного файла: matrices.in
Имя выходного файла: matrices.out
Ограничение по времени: 2 s
Ограничение по памяти: 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, 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.

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.inmatrices.out
2 2 1 1 2 1 2 2 1
2 1 2 3 4IMPOSSIBLE


Источник: Petrozavodsk training camp, Summer 2002. Startup contest
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати