Конструктив

Little Lidia likes playing with numbers. Today she has a positive integer n, and she wants to decompose it to the product of positive integers.

Because Lidia is little, she likes to play with numbers with little difference. So, all numbers in decomposition should differ by at most one. And of course, the product of all numbers in the decomposition must be equal to n. She considers two decompositions the same if and only if they have the same number of integers and there is a permutation that transforms the first one to the second one.
Write a program that finds all decompositions, which little Lidia can play with today.

Input
The only line of the input contains a single integer n (1 ≤ n ≤ 10¹⁸).

Output
In first line output the number of decompositions of n, or −1 if this number is infinite. If number of decompositions is finite, print all of them one per line. In each line first print number ki of elements in decomposition. Then print ki integers in this decomposition in any order. Don’t forget that decompositions which are different only in order of elements are considered the same.
 

Input	Output
12	3 1 12 3 2 3 2 2 4 3
1	-1

In the second example 1 can be represented as product of any number of ones.

There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and o are used to express vowel sounds, while letters b and p are the consonants (e.g. bad, pot).

Some letters can be used to express both vowel and consonant sounds: for example, y may be used as a vowel (e.g. silly) or as a consonant (e.g. yellow). The letter w, usually used as a consonant (e.g. wet) could produce a vowel after another vowel (e.g. growth) in English, and in some languages (e.g. Welsh) it could be even the only vowel in a word.
In this task, we consider y and w as vowels, so there are seven vowels in English alphabet: a, e, i, o, u, w and y, all other letters are consonants.

Let’s define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is 2, the consonant fencity of a string dEsTrUcTiOn is 3 and the consonant fencity of string StRenGtH is 5.

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

Input
The only line of the input contains non-empty original string consisting of no more than 10⁶ lowercase English letters.

Output
Output the only line: the input string changed to have maximum consonant fencity.
 

Input	Output
consonants	CoNsoNaNts
destruction	dEsTrUcTiOn
strength	StRenGtH

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

Принцип работы транспортного средства Деда Мороза(в дальнейшем ПепеЛАЦ(Пепе Летающий агрегат Цвайхандер)) такой:
на расстоянии одного километра друг от друга в точках (0, 0) и (1, 0) были построены две станции управления пепелацами A и B. С помощью них можно мгновенно переместить любой пепелац, повернув его на 90 градусов по или против часовой стрелки относительно точки A или B. Расстояние от пепелаца до соответствующей станции при этом не меняется. Следующее перемещение можно делать как относительно той же станции, так и относительно другой.

Например, если повернуть пепелац, находящийся в точке (3, 1) на 90 градусов против часовой стрелки относительно станции A, то он переместится в точку (−1, 3), если его затем повернуть на 90 градусов по часовой стрелке относительно станции B, то он переместится в точку (4, 2), если затем повернуть его вокруг станции B по часовой стрелке еще раз, он переместиться в точку (3, −3).
Деду Морозу необходимо добраться из точки (x1, y1) в точку (x2, y2). Помогите зайцам Деда Мороза составить маршрут, чтобы ему меньше пришлось ходить по заснеженному лесу.
Поскольку перемещения мгновенные и абсолютно бесплатные(магия же), то минимизировать количество перемещений не надо.

Формат входного файла
Входной файл содержит четыре целых числа — x1, y1, x2 и y2, они не превышают 104 по
абсолютной величине.

Формат выходного файла
Выведите в выходной файл последовательность перемещений с использованием станций управления, которая перемещает пепелац из точки (x1, y1) как можно ближе к точке (x2, y2).
Поворот по часовой стрелке относительно станции A обозначается как «+A», поворот против часовой стрелки относительно станции A обозначается как «-A», соответствующие повороты относительно станции B обозначаются как «+B» и «-B». Выводите по одному перемещению на строке. Выведенная последовательность не обязана быть минимальной по количеству перемещений, но должна содержать не более 106 действий.

Примеры

Ввод	Вывод
3 1 3 -3	-A    +B +B
0 0 3 0	-B +B

 (с) Павел Колодкин, 12И

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

Имя сервера представляет собой строку, содержащую от одной до пяти частей включительно. Каждая часть представляет собой непустую строку, состоящую из строчных букв латинского алфавита. Части разделены точкой. Примеры корректных имен сервера: «a», «ab.cd», «abacaba», «a.b.c.d.e».

Имя раздела представляет собой строку, которая может быть либо пустой, либо содержать от одной до пяти частей включительно. Каждая часть начинается с символа «/», после которого следует одна или несколько строчных латинских букв. Примеры корректных имен разделов: «», «/a», «/aba», «/a/b/c/d/e». Адрес формируется приписыванием имени раздела в конец имени сервера. Например, корректными адресами являются строки: «a», «aba/d/f/g/h», «a.b», «aba.caba/def/g», «c.d.e.f.g/a/b/c/d/e».

Для ограничения доступа к некоторым адресам сети Меганет организаторы чемпионата подготовили несколько фильтров. Фильтр, как и адрес, состоит из двух частей: фильтра сервера и фильтра раздела.

Фильтр сервера состоит из имени сервера, перед которым может также идти строка «*.». Если фильтр сервера представляет собой только имя сервера, то этому фильтру соответствует только сервер, имеющий точно такое же имя. Если фильтр сервера представляет собой строку «*.S », где S — имя сервера, то ему соответствуют сервера, удалением нуля или более начальных частей от имени которых можно получить строку S.

Аналогично, фильтр раздела представляет собой имя раздела, после которого может идти строка «/*». Фильтру раздела, который представляет собой просто имя раздела R, соответствуют только разделы, в точности совпадающие с R. Если фильтр раздела представляет собой строку «R/*», то ему соответствуют все разделы, удалением от имен которых нуля или более конечных частей можно получить строку R. Адрес соответствует фильтру, если его имя сервера соответствует фильтру сервера, а его имя раздела соответствует фильтру раздела.

Примеры фильтров и соответствующих им адресов приведены в таблице ниже.

ab.c/d/e	ab.c/d/e
*.a	a             ax.a         efg.a
*.a/b/c	a/b/c       x.a/b/c      e.fg.a/b/c
x.yz/a/*	x.yz/a      x.yz/a/b/c    x.yz/a/xyz
*.a/*	a             x.a                   e.fg.a a/b/c    x.a/ddd/c           e.fg.a/b/c/g/haha/i
*.a/b/c/*	a/b/c                           x.a/b/c                           e.fg.a/b/c a/b/c/xxx                   e.fg.a/b/c/d/e/f

Требуется написать программу, которая по заданному набору фильтров и списку адресов определяет для каждого адреса, какому числу фильтров соответствует этот адрес.

Пример:
Ввод:
2 0
a.bb/c
bb/c/d
4
a.bb
bb/c/d
a.bb/c/d
bb/c

Вывод:
0
1
0
0


Вывод:
4 0
*.bb/c
*.bb/c/*
bb/c/*
bb/c/*
6
bb
bb/c
bb/c/d
a.bb
a.bb/c
a.bb/c/d

Вывод:
0
4
3
0
2
1