Binary Tree Green Coloring

Consider a binary tree represented by a sequence S of characters chosen from ({0,1,2}), following the rules:

[ S = \begin{cases} 0 & \text{if the tree has no children (a leaf)} \ 1S_1 & \text{if the tree has one child, where } S_1 \text{ is the sequence for its subtree} \ 2S_1S_2 & \text{if the tree has two children, where } S_1 \text{ and } S_2 \text{ are the sequences for its left and right subtrees, respectively} \end{cases} ]

For example, the binary tree in the figure below can be represented by the sequence

[ S = \texttt{21200110} ]

Each node of the tree is to be painted in one of three colors: red, green, or blue. The coloring must follow these rules:

1. A node and its child (or children) must be painted in different colors.
2. If a node has two children, then the two children must also be painted in different colors.

Your task is: Given the binary tree sequence S, determine the maximum and minimum number of nodes that can be painted green in any valid coloring of the tree.

Note: All formulas are written in (\LaTeX) format.

inputFormat

The input consists of a single line containing the binary tree sequence S. The sequence is a non-empty string composed solely of the characters '0', '1', and '2'.

outputFormat

Output two integers separated by a space: the maximum number of nodes that can be green and the minimum number of nodes that can be green in any valid coloring of the tree.

sample

0

1 0