Начиная с давних времен наука алхимии изучались и практиковались. Практика делает алхимиков способными трансмутировать материалы в другие формы. Материалы подлежащие трансмутации требуют рисования круга на земле. Малоизвестный факт о трансмутирующих кругах - они могут находиться внутри других кругов трансмутации. Путем активации определенных конфигураций в правильном порядке могут быть созданы более мощные трансмутации. Неправильное включение кругов может оказать сильное воздействие на тело алхимика.

Молодой алхимик по имени Николас Фламель хотел бы узнать пути алхимии. Он нарисовал несколько конфигураций трансмутационных кругов на земле. Когда круг активирован, он горит ярко-красным и представляет элемент огня. Сама активация не создает дополнительной энергии. Секрет заключается в том, что активируется внешняя трансмутационная окружность. Когда это происходит, все уже активные круги в области активированного круга быстро меняются на соответствующие обратные элементы. Огонь меняется на холодный синий цвет, представляющий воду. Круги, которые были синими и представляли воду, снова зажигают огненный красный цвет. Такое изменение может либо создавать, либо поглощать энергию из трансмутации. Остерегайтесь, энергия может в любой момент стать отрицательной, временно истощая жизненную силу алхимика (заклинание при этом продолжает стабильно работать).

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

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

Первая строка содержит количество тестов t, от 1 до 100 включительно. Для каждого множества трансмутационных кругов первая строка содержит количество этих кругов n (1 ≤ n ≤ 2000). Следующие n строк содержат целые числа x y r a b. Первые три числа задают координаты и радиус окружности, последние два описывают количество выделяемой энергии при переходе от огня к воде (A) и от воды к огню (B) (-10000 ≤ x, y ≤ 10000, 1 ≤ r ≤ 10000, -500 ≤ a, b ≤ 500).

Никакие две окружности не пересекаются и не касаются.

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

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