We called string $$$t$$$ a Quasi-template of string $$$s$$$, if and only if $$$t$$$ is a substring of $$$s$$$ and there exists at least one pair of integers $$$(l,r)$$$ satisfying：

• $$$1 \le l \le r \le |s|$$$ (string is $$$1$$$- indexd).
• $$$s[1 \ldots l-1]$$$ is a suffix of $$$t$$$ and $$$s[r+1 \ldots |s|]$$$ is a prefix of $$$t$$$.
• $$$\forall i \in [l,r]$$$, there exists at least one pair of integers $$$(L,R)$$$ satisfying $$$1 \le L \le i \le R \le n$$$ and $$$s[L \ldots R] = t$$$.

Given string $$$s$$$, you need to find:

• How many distinct Quasi-template does $$$s$$$ have ?
• The shortest Quasi-template of $$$s$$$. If there are multiple, output the smallest one.

$$$1 \le |s| \le 2 \cdot 10^5$$$.