Тернарные веса
В древней Элладе существовал небольшой остров в Средиземном море, известный как Тернария. Он располагался недалеко от Спарты, но из-за гористой местности спартанцы не могли его завоевать, и он оставался независимым государством до великого землетрясения 729 года до нашей эры, когда остров ушел под воду. Тернария обладала замечательной цивилизацией, и некоторые современные историки считают, что она могла быть прототипом мифической Атлантиды. Тернария известна своими значительными вкладами в науку и математику, многие из которых были переняты греками, а затем римлянами. Например, тернарийцы первыми использовали стандартный вес в фунтах, который мы применяем и сегодня. В тернарийской математике все вычисления производились в системе с основанием 3. (Историки предполагают, что это было сделано в честь короля Тернара, который потерял два пальца на каждой руке в битве со спартанцами.)
Тернарийские торговые весы были стандартом на протяжении многих веков. Они славились своей точностью и простотой использования. Именно тернарийцы первыми создали весы с чашами для взвешивания на каждой стороне и с опорой посередине. Объект, который нужно было взвесить, помещался на левую чашу весов, а гири размещались на обеих чашах, пока не достигалось равновесие. Это может показаться странным по современным стандартам, так как обычно на современных весах гири кладут только на правую чашу. Однако современный метод требует больше гирь. Тернарийский метод требует только одну гирю для каждой степени трех фунтов, например, одну гирю в 1 фунт, одну гирю в 3 фунта, одну гирю в 9 фунтов и так далее.
Предположим, вы взвешиваете тернарийскую курицу весом в 2 фунта (известную своим сочным белым мясом). Вы помещаете курицу на левую чашу. Поместите гирю в 3 фунта на правую чашу. Это слишком тяжело, поэтому вы добавляете гирю в 1 фунт к курице на левую чашу, чтобы достичь равновесия. Обратите внимание, что разница между суммой гирь на правой чаше и суммой гирь на левой чаше равна весу объекта.
Рассмотрим другой пример: взвешивание тернарийской тыквы весом в 21 фунт. Используя тернарийскую систему, вы помещаете гири в 27 фунтов и 3 фунта на правую чашу и гирю в 9 фунтов на левую чашу (вместе с объектом), снова достигая равновесия.
Напишите программу, которая принимает на вход вес объекта в десятичной системе и выводит гири, которые нужно разместить на обеих чашах.
Входные данные
Первая строка содержит целое число 1 ≤ n ≤ 100, указывающее количество тестовых случаев. В каждой из следующих n строк содержится целое число 0 ≤ x ≤ 10^9, представляющее вес объекта, помещенного на левую чашу.
Выходные данные
Для каждого тестового случая программа должна вывести две строки. Первая строка должна содержать "left pan:" за которым следует пробел и перечисление гирь, которые нужно поместить в левую чашу в порядке убывания. Вторая строка должна содержать "right pan:" за которым следует пробел и перечисление гирь, которые нужно поместить в правую чашу в порядке убывания. Между каждой парой тестовых случаев напечатайте пустую строку.