Hard Optimization

You are given a set of n segments on a line [L_i; R_i]. All 2n segment endpoints are pairwise distinct integers.

The set is laminar — any two segments are either disjoint or one of them contains the other.

Choose a non-empty subsegment [l_i, r_i] with integer endpoints in each segment (L_i ≤ l_i < r_i ≤ R_i) in such a way that no two subsegments intersect (they are allowed to have common endpoints though) and the sum of their lengths (∑_{i=1}^n r_i - l_i) is maximized.

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^3) — the number of segments.

The i-th of the next n lines contains two integers L_i and R_i (0 ≤ L_i < R_i ≤ 10^9) — the endpoints of the i-th segment.

All the given 2n segment endpoints are distinct. The set of segments is laminar.

Output

On the first line, output the maximum possible sum of subsegment lengths.

On the i-th of the next n lines, output two integers l_i and r_i (L_i ≤ l_i < r_i ≤ R_i), denoting the chosen subsegment of the i-th segment.

Example

Input

4 1 10 2 3 5 9 6 7

Output

7 3 6 2 3 7 9 6 7

Note

The example input and the example output are illustrated below.

inputFormat

Input

The first line contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^3) — the number of segments.

The i-th of the next n lines contains two integers L_i and R_i (0 ≤ L_i < R_i ≤ 10^9) — the endpoints of the i-th segment.

All the given 2n segment endpoints are distinct. The set of segments is laminar.

outputFormat

Output

On the first line, output the maximum possible sum of subsegment lengths.

On the i-th of the next n lines, output two integers l_i and r_i (L_i ≤ l_i < r_i ≤ R_i), denoting the chosen subsegment of the i-th segment.

Example

Input

4 1 10 2 3 5 9 6 7

Output

7 3 6 2 3 7 9 6 7

Note

The example input and the example output are illustrated below.

样例

4
1 10
2 3
5 9
6 7

7
3 6
2 3
7 9
6 7

</p>