题目内容

给出一个由 A、B、C 三种字符构成的字符串 t，其长度记为 m。需要确定两个整数位置 u、v，并满足 1 ≤ u < v < m，以此将 t 切分为 t[1..u]、t[u+1..v]、t[v+1..m] 三个非空且连续的部分。

当每一部分所含的 A 数量都相同，同时每一部分所含的 B 数量也都一致时，称位置对 (u,v) 符合要求；各部分中的 C 数量无需相等。

请在所有符合要求的位置对中，选出字典序最小的 (u,v)。字典序的判定规则是先看位置对第一项，若相等再比较第二项；若不存在符合要求的位置对，则输出 -1 -1。

输入描述

输入一行字符串 t，其中只会出现大写字符 A、B、C。

输出描述

输出两个整数 u、v，对应字典序最小的合法切分位置；无解时输出 -1 -1。

数据范围

3 ≤ m ≤ 200000。

样例

输入：

ABBAAB

输出：

2 4

说明：切分后得到 AB、BA、AB。三个部分的 A 数均为 $1$，B 数也均为 $1$。首个切点最小时，第二切点取 4，因此得到字典序最小解 (2,4)。