Вася, Петя и Миша изучают основы робототехники с помощью робота, который способен перемещаться на плоскости в четырех разных направлениях (вверх, вниз, влево, вправо). Программа для робота задается в виде последовательности команд, соответствующих направлению движения. При исполнении каждой команды робот перемещается в указанном направлении на 10 сантиметров. Команды могут быть обозначены, например, с помощью латинских букв U, D, L, R. Тогда, некоторая программа может быть записана, например, в следующем виде: UDLRUUDLLRULLR.
Ребята написали программу для робота и хотят определить, какой объем памяти необходим для ее хранения в случае кодирования программы различными способами. Известно, что программа содержит 30 команд. Вася предложил кодировать каждую команду одинаковым минимально возможным для всех команд числом бит. Петя внимательно посмотрел на программу и заметил, что вся программа может быть разбита на идущие подряд последовательности из двух символов, причем всего в программе встречается 8 различных последовательностей из двух команд и предложил кодировать пары подряд идущих команд одинаковым минимально возможным для всех встречающихся пар числом бит.
Миша также пристально посмотрел на программу и отметил, что программа может быть разбита на непересекающиеся последовательности команд таким образом, что в программе 4 раза встречаются последовательности из четырех одинаковых команд, 3 раза – последовательности из трех одинаковых команд, 2 раза – последовательности из двух одинаковых команд и еще остается одна команда, причем команды, из которых состоят соседние последовательности, всегда различаются. Миша предложил записывать программу как последовательность пар чисел: код команды и число повторов этой команды (в случае одной команды все равно будут записаны два числа – код команды и единица). При этом для кодирования команды Миша использует одинаковое для всех команд минимально возможное число бит. Для кодирования числа повторов команды Миша также использует одинаковое для всех чисел, обозначающих количество повторов, минимально возможное число бит.
Определите, сколько бит позволяет сэкономить кодирование данной программы способами Пети и Миши по сравнению со способом Васи. В ответе укажите через пробел два целых положительных числа: сначала разницу в битах между способами Пети и Васи, далее разницу в битах между способами Миши и Васи.