Заходят как-то n Дэнчиков в бар, и каждый заказывает по коктейлю из фруктовых соков.

В каждом коктейле может быть от 1 до 3 различных сортов соков. В баре есть три сорта: яблочный, банановый и ананасовый. У каждого Дэнчика есть свой любимый вид коктейля. Коктейль однозначно задаётся тем, какие сорта соков в него входят. Разумеется, каждый Дэнчик заказал по одному своему любимому коктейлю.

Бармен может выставить все n бокалов в один длинный ряд и наливать сок в отрезок последовательных стаканов. Бар очень популярен, поэтому бармен хочет обслужить Дэнчиков как можно быстрее. Для этого он хочет расставить бокалы в таком порядке, что количество «наливаний» будет минимально. За одно «наливание» можно налить один сорт сока в отрезок последовательных стаканов.

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

Дэнчиков слишком много, поэтому бармен сам не может понять, в каком порядке ему следует расставить бокалы. А можете ли вы?

В первой строке вводится целое число n (1 ≤ n ≤ 10⁵).

Затем в n строках описаны заказы Дэнчиков. Каждый заказ описывается одной строкой длины от 1 до 3 из заглавных латинских букв A, B, P. В i-й строке перечислены сорта соков, входящих в i-й заказ (A = Apple = Яблочный, B = Banana = Банановый, P = Pineapple = Ананасовый). Буквы внутри строки следуют именно в таком порядке, то есть строка получается из строки "ABP" вычёркиванием некоторого (возможно, нулевого) числа букв.

В первой строке выведите минимальное количество «наливаний».

Во второй строке выведите номера бокалов в том порядке, в котором их нужно расставить в ряд. Считайте, что заказы и соответствующие им бокалы пронумерованы от 1 до n в том порядке, в котором они даны на входе.

Если оптимальных расстановок несколько, выведите любую.