Башни

Башней называется выражение вида a₀^{a₁a₂...a_k}, где k ≥ 1, т.е. последовательное возведение в степень чисел a₀, ..., a_k. Отметим, что операция возведения в степень выполняется справа налево, т.е. выражение a^bc вычисляется как a^(bc).

Аня недавно изучила алгоритмы сортировок, и теперь она умеет сортировать целые числа, вещественные числа, и даже строки. Узнав об этом, Андрюша предложил ей написать программу для сортировки башен. Как же это сделать?

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

Входные данные

В первой строке входного файла INPUT.TXT задается число башен N (1 ≤ N ≤ 50000). Далее следуют N строк, каждая из которых содержит одну башню в формате k_i a_i0 a_i1 ... a_iki, здесь все числа разделены пробелами. Каждое из a_ij - целое число в пределах от 1 до 99, кроме того, 1 ≤ k_i ≤ 9.

Известно, что среди башен во входном файле нет равных. Заметьте, что значения у башен могут быть весьма велики - например, даже число 2²²²² = 2⁶⁵⁵³⁶ не помещается ни в какой вещественный тип.

Выходные данные

В выходной файл OUTPUT.TXT выведите перестановку номеров башен b₁, b₂, ... , b_N в таком порядке, что если взять сначала башню с номером b₁, потом с номером b₂, и т.д., то они окажутся расположенными в порядке возрастания.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]