题目描述

本题为 BalticOI 2019 Day2 T2. Necklace 一题的特殊数据版本，内存限制为 3 MB。

Jill 和 Jane 是姐妹，去年圣诞节他们每个人都得到了一串彩色珠子。我们可以将每种颜色描述为小写英文字母（$\texttt{a}\ldots \texttt{z}$），并将每串珠子描述为一个单词。

女孩们想从他们的珠子中创造项链。他们可以从自己的那串珠子的两端移除一些珠子（可能为零），然后连接剩余部分的两端，将其变成项链。生成的项链可以旋转和翻转。

姐妹们希望他们的项链看起来完全一样，并且尽可能长。她们项链可以达到的最大长度是多少？

输入格式

输入包含两行，每行一个字符串，分别描述了 Jill 和 Jane 的一串彩珠。

输出格式

输出第一行应该包含一个正整数，代表项链的长度。测试数据保证存在长度为正整数的项链。

第二行包含两个正整数，分别代表 Jill 和 Jane 得到的项链在原来彩珠串中的起始位置，如果有多种合法方案，任意输出一种即可。每一串彩珠从左到右从 $0$ 开始编号。

zxyabcd
yxbadctz

4
3 2

数据范围与提示

评分标准

如果你的程序得到的项链合法（即两条项链等价），且长度与可能的最长项链长度相等，你将得到该测试点全部的分数。

如果你的程序得到的项链合法，且长度达到了最长项链长度的一半，你将得到该测试点 $20\%$ 的分数。

请注意，你在一个子任务上的得分，等于你在该子任务所有测试点的最低得分。

子任务

请注意，本题只评测最后一个子任务，空间限制均为 3 MB。

设输入中每个字符串的长度上限为 $N$ ，则有 $N = 3000$。