Once Opened, You Can't Stop

A monkey that escaped from a zoo is about to eat several new flavors of Pringles in order. For each flavor, the monkey must choose an integer addiction-stress value inside the range assigned to that flavor.

Whenever the stress value changes, the monkey's expected lifespan decreases by the absolute difference between the previous value and the new value. For example, changing the value from 5 to 3 or to 7 decreases the expected lifespan by 2 years.

Before eating the first flavor, the monkey may choose any initial stress value for free. Given N flavors that must be eaten in the input order, minimize the total decrease in expected lifespan and output one stress value chosen for each flavor.

The first line contains the number of flavors N. (1 <= N <= 100,000)

Each of the next N lines contains two integers s_i and e_i. For the i-th flavor, the addiction-stress value must be at least s_i and at most e_i. (1 <= s_i <= e_i <= 200)

The flavors must be eaten in the order given by the input.

Print the minimum possible decrease in expected lifespan on the first line.

Then print N more lines. The i-th of these lines must contain the addiction-stress value chosen for the i-th flavor. If several choices achieve the minimum, you may print any one of them.