Tienes \(n\) intervalos cerrados \([s_i, e_i]\) en cualquier orden. Fusiona todos los que se intersectan (dos intervalos que comparten aunque sea un punto, como \([1, 4]\) y \([4, 5]\), se fusionan) hasta que no quede ningún par que se intersecte.

Entrada

La primera línea tiene \(n\) \((1 \le n \le 10^5)\) y siguen \(n\) líneas con \(s_i\) y \(e_i\) \((0 \le s_i \le e_i \le 10^9)\).

Salida

La cantidad de intervalos resultantes en una línea, y luego cada intervalo en su propia línea, ordenados por inicio.

Ejemplo 1

Entrada

4
1 3
2 6
8 10
15 18

Salida

3
1 6
8 10
15 18

Ejemplo 2

Entrada

2
1 4
4 5

Salida

1
1 5

Basado en el problema 56 de LeetCode, Merge Intervals, adaptado a entrada y salida estándar; enunciado redactado para este juez. Es parte de la lista Grind 75 de Yangshun Tay.