题目描述

给出一个字符串 $s$ ，求出 $s$ 中重复出现过的子串中最长的子串，并求出最长子串的首字母的位置，如果出现多组重复出现的最长子串，只输出按字母序从小到大，第一个最长的相同子串的位置（字典码最小的）。

例如：字符串 $s$ 为：aabcdttabcdettaabcftt ，它的最长重复出现的子串有两个 abcd 和 aabc 长度都为 $4$ ，这两字符串均为 $s$ 的最长重复出现的子串，但输出时只需输出 aabc 第一次出现的位置，因为 aabc 的字典码小于 abcd。

输入

输入为一行，为一个字符串 $s$ ，保证 $s$ 中有重复出现的子串且字符串长度小于 $100$ 。

输出

为两行，第一行为最长重复出现的子串，第二行为此子串第一次出现的位置。

样例

aabcdttabcdettaabcftt

aabc
1

来源

字符串