You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

  向疯狂戴夫投递简历后，你成为了智慧树管理员，这棵树保存了每个地区的资源数据。每个结点代表一个区域，通过二叉树的结构连接这些区域，结点上的数值表示该区域的资源储量。

Description

  你需要通过与这棵智慧树的互动，获得区域资源的最大化信息，才能合理安排资源调度。为了与智慧树交互，你需要完成以下任务：

1. 高度测量：你需要测量智慧树的高度，以便于确认是否需要施肥。

2. 资源调度：你需要找到资源最丰富的路径（从根结点到叶子结点的某条路径，且资源量最大）。

3. 特殊区域探查：找到所有非叶子结点，且其结点值大于任意直接子结点值的结点。

Format

Input

  输入包含一行整数，表示智慧树的层序遍历（按行从上到下、从左到右），-1 表示该结点为空。

Output

  第一行一个整数，表示智慧树的高度。

  第二行一个整数，表示资源最丰富路径的结点值之和。

  第三行一个整数，表示特殊区域的结点值之和。

Samples

10 5 20 4 -1 15 25 -1 -1 -1 -1 -1 13 -1 22

4
77
45

Notes

  如图所示，橙色路径就是资源量最大的路径，由蓝色圈出的结点就是所有的特殊区域。

Limitation

  高度 $h \leq 20$, 节点值 $0 < v \leq 1000$。输入保证是一棵二叉树。