Разбор случаев

Черный рейнджер нашел в жерле заброшенного вулкана n прямоугольных листов металла разного размера, i-й лист имеет размер a_i на b_i метров.
Зордон поручил построить Черному рейнджеру тюрьму для злобного генерала Зедда, и эта находка оказалась для него просто подарком судьбы. Тюрьма должна иметь вид прямоугольного параллелепипеда каждая грань которого представляет собой цельный лист металла. Так что рейнджер собирается взять 6 из найденных им листов металла, сложить из них параллелепипед, и показать его Зордону. Листы нельзя гнуть или разрезать, листы, из которых будет сложена тюрьма не должны выступать за её края.
Поскольку чем больше тюрьма, чем надежнее, параллелепипед должен иметь максимальный возможный объем. Помогите герою выбрать 6 листов прямоугольников так, чтобы собрать из них самую большую тюрьму.
Листы можно поворачивать, таким образом, например, листы 4 на 7 метров и 7 на 4 метра считаются одинаковыми.

Формат входных данных
В первой строке дано одно число n — количество листов металла у Черного Рейнджера (6 ≤ n ≤ 200 000).
В следующих n строках даны пары чисел a_i; b_i — размеры i-го куска металла (1 ≤ a_i; b_i ≤ 10⁶).

Формат выходных данных
Выведите одно целое число — максимальный объем прямоугольного параллелепипеда, который можно собрать из этих кусков металла.
Если из данных листов невозможно собрать прямоугольный параллелепипед, выведите -1.

Примеры

№	Входные данные	Выходные данные
1	6 3 6 6 9 9 3 6 3 3 9 9 6	162
2	6 1 1 1 1 1 1 1 1 1 1 1 1	1
3	6 1 2 2 3 3 4 4 5 5 6 6 1	-1

Как известно, личная олимпиада по информатике проходит в два тура. На каждом из туров участники получают какие-то баллы, при этом итоговый балл определяется как сумма полученных баллов. Известны баллы, которые каждый участник получил на каждом из туров. Жюри хочет фальсифицировать итоги олимпиады так, чтобы победил «нужный» участник.

При этом жюри может делать следующие «подтасовки» (можно делать несколько «подтасовок» применительно как к одному и тому же, так и к разным турам):

Прибавить к результатам всех участников по одному из туров одно и то же положительное число.
Умножить результаты участников по одному из туров на некоторый коэффициент, больший 1.
При этом должна сохраниться правдоподобность результатов, которая заключается в том, что никто из участников не должен получить больше 100 баллов за каждый из туров.

Определите список участников, которые в результате таких фальсификаций могут оказаться победителями олимпиады (то есть в сумме за два тура иметь не меньше баллов, чем каждый из остальных участников).

Входные данные
Во входном файле записано сначала число участников N (1 ≤ N ≤ 1000), затем N пар чисел — результаты каждого участника за 1-й и за 2-й туры (результат участника за тур — это вещественное число от 0 до 100) не более, чем с 3 знаками после десятичной точки.

Выходные данные
В выходной файл выведите сначала количество участников, которые смогут стать победителями олимпиады, а затем в возрастающем порядке их номера.
 

Примеры

№	Входные данные	Выходные данные
1	4 45 90 70 80 0 0 75 75	2 2 4

There is an urban myth that Peter the Great wanted to make a rectangular channel-grid engineering masterpiece not only from Vasilyevskiy island, but also from Kotlin island (where the town of Kronstadt is located nowadays).

The following mathematical model was (allegedly) presented to the tsar. The island is considered a rectangular grid h cells high and w cells wide. Each cell is dry land initially but can become water.

Technologies of those days allowed engineers to dig a channel across the entire island. In that case an entire row or an entire column of cells became water. If some of these cells already were water, their status did not change.
Your task is to propose a plan of the island which has exactly n connected components of dry land cells.

Input
The only line of the input contains three integers h, w, and n — grid’s height, width and the desired number of connected components (1 ≤ h, w ≤ 100; 1 ≤ n ≤ 10⁹ )

Output
If there is no valid plan containing n connected components, output a single word “Impossible”. Otherwise output h lines of length w depicting the plan. Dot (‘.’) represents a dry land cell, hash (‘#’) represents a water cell.
 

Input	Output
3 5 4	..#.. ##### ..#..
2 1 1	# .
5 3 10	Impossible