题目描述

一棵二叉树可以用如下规则表示成一个由 $0$、$1$、$2$ 组成的字符序列，我们称之为二叉树编码 $S$：

$$S=\begin{cases} 0 & \text{表示该节点没有子节点}\\ 1S_1 & \text{表示该节点有一个子节点，}S_1\text{为其子树的编码}\\ 2S_1S_2 & \text{表示该节点有两个子节点，}S_1\text{ 和 }S_2\text{ 分别为左右子树的编码} \end{cases}$$

例如，一棵二叉树可以用编码 $S=\texttt{21200110}$ 来表示。

现在要对这棵二叉树的每个节点染色。每个节点可以染成红、绿、蓝三种颜色之一，且必须满足：

• 一个节点与其子节点的颜色不同；
• 如果该节点有两个子节点，则这两个子节点的颜色也不同。

给定二叉树编码，求这棵树中最多和最少分别有多少个点可以被染成绿色。

输入格式

输入只有一行，一个字符串 $s$，表示二叉树编码。

输出格式

输出只有一行，包含两个整数，依次表示最多和最少有多少个点可以被染成绿色。

样例

1122002010

5 2

提示

对于全部的测试点，保证 $1 \le |s| \le 5 \times 10^5$，$s$ 中只含字符 0、1、2。