To celebrate Python 2's death, Roger challenges you to find all occurrences of a string ~T~ in ~S~. Of course, you may only use Python 3.

Input Specification

The first line contains a string ~S~.

The second line contains a string ~T~.

Both strings will only contain lowercase letters. You may assume ~1 \le |T| \le |S| \le 10^6~.

Output Specification

Let ~A~ be the sum of all 1-indexed occurrences of ~T~ in ~S~ and let ~B~ be the xor of all 1-indexed occurrences of ~T~ in ~S~.

Print two lines. Print ~A~ on the first line and ~B~ on the second line.

Scoring

If your solution is incorrect, it earns zero marks.

Let ~L~ be the length of the shortest correct solution to this problem. If your program has length strictly less than ~L~, it earns 99% of full credit. Otherwise, it earns ~0.98 \left(\frac{L}{L'}\right)^3~ of the available marks, where ~L'~ is the length of your program. You will receive feedback on the length of your program explicitly.

The scoring is intentionally designed to make it easy to see who has the best solutions, when the problem may need to be rejudged or have data augmented, and to keep people from copying other people's solutions.

Sample Input

dmojdmoj
dmoj

Sample Output

6
4