Prefix와 Suffix

문자열 $S = S_1 S_2 \dots S_{|S|}$가 주어진다. $|S|$는 $S$의 길이이고, $S_i$는 $i$번째 글자다.

• $S$의 부분 문자열 $S[i..j]$ ($1 \le i \le j \le |S|$)는 $S_i S_{i+1} \dots S_j$다.
• 길이가 $l$ ($1 \le l \le |S|$)인 $S$의 Prefix는 $S[1..l]$이다.
• 길이가 $l$ ($1 \le l \le |S|$)인 $S$의 Suffix는 $S[|S|-l+1..|S|]$이다.

$S$의 Prefix이면서 동시에 Suffix인 문자열을 모두 찾고, 각각이 $S$의 부분 문자열로 몇 번 등장하는지 세는 프로그램을 작성하시오. 등장 위치는 서로 겹쳐도 된다.

첫째 줄에 문자열 $S$가 주어진다. ($1 \le |S| \le 100\,000$)

첫째 줄에 $S$의 Prefix이면서 동시에 Suffix인 문자열의 개수 $K$를 출력한다.

이어지는 $K$개의 줄에는 $l_i$와 $c_i$를 공백으로 구분해 출력한다. 길이가 $l_i$인 Prefix가 길이가 $l_i$인 Suffix와 같고, 그 문자열이 $S$의 부분 문자열로 $c_i$번 등장한다는 뜻이다.

$l_i$가 증가하는 순서로 출력한다.