410513: GYM104031 C Роллер

C. Роллерограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Кеша любит кататься на роликовых коньках. Он полагает (и в этом с ним согласны большинство роллеров), что кататься по асфальту значительно приятнее, нежели по плитке. Однако, к огорчению роллеров, местные власти постепенно меняют асфальт на плитку.

Один из тротуаров, по которому нравится кататься Кеше, можно описать последовательностью латинских символов $$$A$$$ и $$$T$$$. Символ $$$A$$$ соответствует участку из асфальта единичной длины, а символ $$$T$$$ соответствует участку из плитки единичной длины.

В ближайшее время местные власти планируют заменить асфальт на плитку ровно на двух участках (на большее не хватает финансов). Местные власти справедливо полагают, что чем короче будет непрерывная последовательность асфальтовых участков, тем до меньшей скорости будут разгоняться на этом отрезке тротуара роллеры. Поэтому они хотят выбрать два асфальтовых участка таким образом, чтобы после замены максимальная суммарная длина последовательно расположенных асфальтовых участков на тротуаре была минимально возможной.

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

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

В первой строке содержится последовательность латинских символов $$$A$$$ и $$$T$$$, содержащая не менее $$$2$$$ и не более $$$4 \cdot 10^5$$$ символов.

Гарантируется, что в последовательности содержится не менее двух символов $$$A$$$.

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

Выведите три целых числа — наибольшую длину из расположенных подряд участков с асфальтом после оптимальной замены, а так же номера участков, на которых следует заменить асфальт плиткой. Разделяйте числа пробелом или переводом строки.

Если существует несколько вариантов ответа — выведите любой из вариантов.

Система оценки

Во всех подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов.

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

Подзадача	Баллы за тест	Ограничения	Необходимые	Информация
	(баллы		подзадачи	о проверке
	за подзадачу)
1	2 (до 10)	длина строки не превышает $$$10$$$	нет	полная
2	2 (до 10)	длина строки не превышает $$$100$$$	1	полная
3	2 (до 20)	длина строки не превышает $$$1000$$$	2	полная
4	2 (до 6)	в строке содержатся только символы $$$A$$$	2	полная
5	2 (до 6)	все символы $$$A$$$, содержащиеся в строке,	4	полная
		образуют одну непрерывную
		последовательность
6	2 (до 6)	все символы $$$T$$$, содержащиеся в строке,	4	полная
		образуют одну непрерывную
		последовательность
7	2 (до 6)	символы $$$A$$$, содержащиеся в строке,	3, 5, 6	полная
		образуют не более двух
		непрерывных последовательностей
8	2 (до 36)	любые символьные последовательности,	7	полная
		удовлетворяющие условиям задачи

ПримерыВходные данные

TTAAATAAAAT

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

2
8
4

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

TTTAAAAAAATTTAAAAAATTAAAAAAAT

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

6
7
25

Примечание

Поясним приведённые примеры.

В первом примере одной из оптимальных замен является замена асфальта на участках $$$4$$$ и $$$8$$$. После изменений тротуар будет иметь вид $$$TTA[T]ATA[T]AAT$$$ (в скобках указаны участки с заменой). Легко увидеть, что наибольшее количество расположенных подряд участков с асфальтом равно $$$2$$$ (участки $$$9$$$ и $$$10$$$).

Обратим внимание, что в первом примере это не единственная оптимальная замена. Например, замены $$$3$$$ $$$8$$$ привели бы к тротуару $$$TT[T]AATAA[T]AT$$$, в котором наибольшее количество расположенных подряд участков с асфальтом так же равно $$$2$$$ (участки $$$4$$$ и $$$5$$$; $$$7$$$ и $$$8$$$).

Во втором примере после замен $$$7$$$ и $$$25$$$ тротуар примет вид $$$TTTAAA[T]AAATTTAAAAAATTAAA[T]AAAT$$$. Легко увидеть, что наибольшее количество расположенных подряд участков с асфальтом равно $$$6$$$ (участки с $$$14$$$ до $$$19$$$).