More Things to Do

Limits: 2 sec., 256 MiB

As you already know, Zenyk has a lot of tasks to do. In total, he has \(N\) tasks, \(i\)-th of them will last from the time \(l_i\) to \(r_i\). Note that the tasks can overlap or intersect in any way.

This time, Zenyk decided that he could move some of the tasks to tomorrow. Zenyk does not like much when tasks overlap, so he wants to break more such tasks between different days. Suppose \(intersect(a, b)\) is the length of the intersection of the tasks \(a\) and \(b\). For example, \(intersect([2,7], [4,10])=3\), \(intersect([4,7] , [2,10])=3\), \(intersect([2,4] , [7,10])=0\). Suppose the set of tasks that Zenyk performs today is \(A\), tomorrow — \(B\).

Then Zenyk wants to maximize \[C = \sum_{a\in A} \sum_{b \in B} {intersect(a, b)}\].

Help him with this.

Input

The first line contains a single integer \(N\). In the following \(N\) lines, there are given 2 integers \(l_i\) and \(r_i\).

Output

In the first line, print the maximum value of \(C\). In the second line, print \(N\) numbers \(0\) or \(1\). \(1\) means that Zenyk will do the task today, \(0\) — tomorrow.

Constraints

\(1 \le N \le 10^5\),

\(0 \le l_i < r_i \le 10^9\).

Samples