Tienes \(n\) intervalos cerrados \([s_i, e_i]\) que no se intersectan y vienen ordenados por su inicio, y un intervalo nuevo \([a, b]\). Insértalo y fusiona lo que haga falta para que la lista siga ordenada y sin intersecciones. Dos intervalos que comparten aunque sea un punto (como \([1, 3]\) y \([3, 4]\)) se fusionan.

Entrada

La primera línea tiene \(n\) \((0 \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,\ e_i < s_{i+1})\). La última línea tiene \(a\) y \(b\) \((0 \le a \le b \le 10^9)\).

Salida

La cantidad de intervalos resultantes en una línea, y luego cada intervalo (inicio y fin) en su propia línea, en orden.

Ejemplo 1

Entrada

2
1 3
6 9
2 5

Salida

2
1 5
6 9

Ejemplo 2

Entrada

5
1 2
3 5
6 7
8 10
12 16
4 8

Salida

3
1 2
3 10
12 16

Ejemplo 3

Entrada

0
5 7

Salida

1
5 7

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