Divine Lights

In an old temple, there are NN lamps, numbered from 11 to NN. Each lamp is initially either on or off.

A priest performs a ceremony lasting NN days. On day ii of the ceremony, the priest toggles every lamp except lamp ii: lamps that are on are turned off, and lamps that are off are turned on. The lamps remain in their resulting states until the next day.

Given the initial state of each lamp, determine the minimum and maximum numbers of lamps that are on at the end of a day during the ceremony. The initial states of the lamps must not be considered.

Input

The input consists of a single line that contains a string of NN characters (1≤N≤2×1051 \leq N \leq 2 \times 10^{5}). The ii-th character is “1” if lamp ii is initially on, and “0” if it is initially off.

Output

Output a single line with two integers representing the minimum and maximum numbers of lamps that are on at the end of a day during the ceremony, in that order.

Examples

Input

1011

Output

1 3

Explanation

In this sample N = 4 and the initial states of the lamps are given by “1011”. At the end of each day of the ceremony their states are:

  • Day 1: “1100” (2 lamps on)

  • Day 2: “0111” (3 lamps on)

  • Day 3: “1010” (2 lamps on)

  • Day 4: “0100” (1 lamp on)

Thus, among the N days considered, the minimum number of lamps that are on is 1, and the maximum is 3.

Input

11

Output

0 1

Explanation

Here N = 2 and the initial states of the lamps are given by “11”. At the end of day 1 the states of the lamps are “10”, and at the end of day 2 they are “00”. The minimum is 0 and the maximum is 1. Note that initially two lamps are on, but the initial states must not be considered.