Symmetric Folding

A folded manual consists of a series of creases. The manual originally has N creases arranged in order, numbered 1, 2, ..., N from top to bottom. These creases divide the paper into N+1 strips of equal width. Each crease is of one of two types:

• v indicating that the paper is folded forward (with the crease protruding inward);
• ^ (ASCII 94) indicating that the paper is folded backward (with the crease protruding outward).

Folding is performed along one of the creases. Suppose you choose to fold along crease k (1 ≤ k ≤ N). Denote the creases above crease k as the left part (with k-1 creases) and those below as the right part (with N-k creases). However, the fold is valid only if for every integer d with 1 ≤ d ≤ min(k-1, N-k) it holds that the crease at position k-d and the crease at position k+d are opposites (i.e. one is v and the other is ^). Note that if k = 1 or k = N, the fold is automatically valid.

After a valid fold along crease k, the paper is folded and only one side's crease sequence is retained to represent the new folded state. Specifically, if the left side has more creases than the right side, then the new crease sequence is the left part; if the right side has more creases then it is the right part. If both sides have equal counts, you may choose either of them (the crease pattern is rotationally symmetric in 3D).

For a manual that has only one crease (i.e. a sequence of v or ^), folding it will overlay all the (1+1) strips and the manual is said to be folded neatly.

If you fold along every crease sequentially (i.e. one by one) the manual can eventually be folded neatly, but this is not considered aesthetically pleasing. Kanan prefers fewer folds and, moreover, each fold should be as symmetric as possible. For every fold, define its asymmetry cost as the absolute difference between the number of creases on the two sides being folded.

Your task is: given a crease sequence, determine the minimum number of folds needed to neatly fold the manual, and among all strategies that use the minimum number of folds, find the smallest total asymmetry cost (the sum of the asymmetry costs incurred at each fold).

Input Constraints: The crease sequence is a non-empty string consisting solely of the characters v and ^.

Note: Even a manual with only one crease (e.g. v or ^) must be folded once to be considered neatly folded.

inputFormat

The input consists of a single line containing a string S, representing the crease sequence. The characters in S are either v or ^.

outputFormat

Output two space‐separated integers: the minimum number of folds needed and the minimum total asymmetry cost among all strategies that achieve that fold count.

sample

v

1 0