Problem K
Student Counsel

Starlight Glimmer: “I am so sorry about today. I’m just so—”

Trixie: “Busy. I know. Obviously your students are more important than your friends.”

Starlight Glimmer: “That’s not—”

[knocking on door]

[door opens]

Silverstream: “Starlight~! Do you have a minute?”

Figure 1: Illustration by Kyle Coate.

Starlight Glimmer faces a dilemma. As the guidance counselor of the School of Friendship, she has to be available to attend to the needs of her students. At the same time, she doesn’t want to neglect her friendships; spending time with her friends is very important, too!

For now, Starlight wants to focus on making sure she spends enough time with Trixie and Silverstream. She’s asked for their availabilities over the next couple of days, and plans to arrange her own schedule to spend as much time with them as possible.

Trixie will be available during $N$ time intervals; the $i^\text {th}$ of these time intervals is $[L_ i, R_ i)$, which denotes that Trixie will be free from the start of minute $L_ i$, inclusive until the start of minute $R_ i$, exclusive.

Likewise, Silverstream will be available during $M$ time intervals; the $i^\text {th}$ of these time intervals is $[L’_ i, R’_ i)$, which similarly denotes that Silverstream will be free from the start of minute $L’_ i$, inclusive to the start of minute $R’_ i$, exclusive.

Now, Starlight wants to choose some set of time intervals $[l_1, r_1), [l_2, r_2), \dots , [l_ n, r_ n)$ to spend with Trixie and another set of time intervals $[l’_1, r’_1), [l’_2, r’_2), \dots , [l’_ m, r’_ m)$ to spend with Silverstream, such that the following all hold true:

1. $l_ i < r_ i$ and $l’_ i < r’_ i$ for all $i$; that is, all time intervals have positive length.

2. For every time interval $[l_ i, r_ i)$, Trixie is actually available for the entirety of that time interval; that is, Trixie is free from the start of minute $l_ i$, inclusive until the start of minute $r_ i$, exclusive.

3. For every time interval $[l’_ i, r’_ i)$, Silverstream is actually available for the entirety of that time interval; that is, Silverstream is free from the start of minute $l’_ i$, inclusive until the start of minute $r’_ i$, exclusive.

4. All $n + m$ time intervals are pairwise disjoint; that is, for any two different time intervals the length of their intersection is zero. This means that Starlight cannot spend time with both Trixie and Silverstream simultaneously, even if they are both available. It also means your output should be well-formed, so for any two different time intervals spent with Trixie (or Silverstream) the length of their intersection is also zero.

5. The total amount of time spent with Trixie and the total amount of time spent with Silverstream are equal.

She wants to make sure she gets exceptional student feedback, while at the same time not losing her friendships. To this end, she wants to maximize the total amount of time spent with Trixie and Silverstream. Can you help her plan out her schedule?

Input

The first line of input contains two integers, $N$ and $M$ ($1 \leq N, M \leq 200\, 000$), the number of time intervals Trixie and Silverstream are free, respectively.

The next $N$ lines of input contain the descriptions of the time intervals Trixie is free. In particular, the $i^\text {th}$ of these lines contains two integers $L_ i$ and $R_ i$ ($1 \leq L_ i < R_ i \leq 10^9$; $R_ i < L_{i+1}$ for all positive integers $i < N$), denoting that the $i^\text {th}$ time interval Trixie is free is $[L_ i, R_ i)$.

The next $M$ lines of input contain the descriptions of the time intervals Silverstream is free. In particular, the $i^\text {th}$ of these lines contains two integers $L’_ i$ and $R’_ i$ ($1 \leq L’_ i < R’_ i \leq 10^9$; $R’_ i < L’_{i+1}$ for all positive integers $i < M$), denoting that the $i^\text {th}$ time interval Silverstream is free is $[L’_ i, R’_ i)$.

Output

On the first line, output two integers $n$ and $m$ ($1 \leq n, m \leq 400\, 000$), the number of time intervals Starlight should spend with Trixie and Silverstream, respectively.

Then, on the next $n$ lines, output the time intervals Starlight should spend with Trixie. In particular, the $i^\text {th}$ of these lines should contain two numbers $l_ i$ and $r_ i$, denoting that the $i^\text {th}$ time interval Starlight should spend with Trixie is $[l_ i, r_ i)$. $l_ i$ and $r_ i$ should either be integers or real numbers with exactly one digit after the decimal point. You can report the $n$ intervals in any order.

Then, on the next $m$ lines, output the time intervals Starlight should spend with Silverstream. In particular, the $i^\text {th}$ of these lines should contain two numbers $l’_ i$ and $r’_ i$, denoting that the $i^\text {th}$ time interval Starlight should spend with Silverstream is $[l’_ i, r’_ i)$. $l’_ i$ and $r’_ i$ should either be integers or real numbers with exactly one digit after the decimal point. You can report the $m$ intervals in any order.

All $n+m$ time intervals should be pairwise disjoint and selecting these time intervals should result in the maximum total amount of time spent with Trixie and Silverstream. Additionally, the total amount of time spent with Trixie should be equal to the total amount of time spent with Silverstream, and Trixie and Silverstream must actually be available in the selected time intervals.

If there are multiple correct answers, you can output any of them.

The input will be such that if a solution exists that spends a total of $t$ time with Trixie and Silverstream, then a solution exists that spends a total of $\geq t$ time with Trixie and Silverstream with $n, m \leq 400\, 000$ and all $l_ i$, $r_ i$, $l’_ i$ and $r’_ i$ being either integers or real numbers with exactly one digit after the decimal point.

3 2
1 6
8 10
12 15
1 6
9 15

2 1
1 6
8 9
9 15

1 1
1 100
1 100

2 2
1 10.1
20.2 60.6
10.1 20.2
60.6 100.0