Matt Damonnak, a híres űrbotanikusnak, már 2017-ben sikerült, az informatikaverseny résztvevőinek köszönhetően, burgonyát termelnie a Marson.

Úgy döntött, hogy az idén egy újabb burgonyaültetvényt létesít, és ehhez kéri a segítségeteket. A Marson egy \(N \times M\) méretű termőföld áll a rendelkezésére, amelyet \(N \cdot M\) egységmezőre bontott fel. Minden mezőn egy bizonyos számú burgonya ültethető el, viszont a talaj különleges összetétele miatt az \(i\)-dik sorban nem lehet összesen kevesebb, mint \(a_i\), és több, mint \(b_i\) burgonya (minden \(i = 1,2,\ldots,N\)-re). Ehhez hasonlóan a \(j\) oszlopban nem lehet összesen kevesebb, mint \(c_j\), és több, mint \(d_j\) burgonya (minden \(j = 1,2,\ldots,M\)-re).

Segítsetek Matt Damonnak megtalálni azt a burgonyaelrendezést, amellyel maximalizálhatja a hozamot, azaz határozzátok meg, hogyan tud legtöbb burgonyát elültetni.

A bemenet leírása

A szabványos bemenet első sorában \(N\) és \(M\), két egész szám áll, amelyek a földterület méretét jelölik.

A további \(N\) sor mindegyikében \(a_i\) és \(b_i\) egész számok találhatók, amelyek az \(i\)-dik sorra vonatkozó korlátozásokat jelölik.

A további \(M\) sor mindegyikében \(c_i\) és \(d_i\) egész számok találhatók, amelyek az \(j\)-dik oszlopra vonatkozó korlátozásokat jelölik.

A kimenet leírása

A szabványos kimenet első sorában meg kell adni, hogy Matt Damon legtöbb hány burgonyát tud elültetni.

A második sorban a \(K\) számot kell kiíratni ‒ azon mezők számát, amelyekre burgonyát kell ültetni.

A további \(K\) sorban három egész számot (\(x\), \(y\) és \(n\)) kell kiíratni, amelyekre érvényes, hogy \(1 \leq x \leq N\), \(1 \leq y \leq M\), \(n \geq 0\). Ezek a számok azt jelölik, hogy az \(x\) sor és az \(y\) oszlop metszetén található mezőre \(n\) darab burgonyát kell elültetni.

A burgonyák elrendezésének meg kell felelnie a feladat szövegében leírt feltételeknek. Amennyiben több megoldás létezik, bármelyiket kiírathatod közülük.

1. példa

Bemenet

2 2
1 2
1 1
1 3
0 0

Kimenet

3
2
1 1 2
2 1 1

A példa magyarázata

Az alábbi táblázatban egy lehetséges burgonyaelrendezés látható, amely eleget tesz a korlátozásoknak, és a legnagyobb hozamot eredményezi (a táblázatban található \(x-y\) alakú kifejezések a burgonyák számára vonatkozó alsó és felső határokat jelölik az adott sorban/oszlopban).

​
## 2. példa

Bemenet

2 3
2 2
2 2
1 2
1 2
1 2

Kimenet

4
4
1 1 1
1 3 1
2 2 1
2 3 1

A példa magyarázata

Az alábbi táblázatban egy lehetséges burgonyaelrendezés látható, amely eleget tesz a korlátozásoknak, és a legnagyobb hozamot eredményezi.

Korlátozások

• \(1 \leq N, M \leq 50000\).
• \(0 \leq а_i \leq b_i \leq 10^9\)
• \(0 \leq c_i \leq d_i \leq 10^9\)
• Biztosan létezik olyan burgonyaelrendezés, amely minden feltételt kielégít.

A tesztpéldák hat diszjunkt csoportba vannak sorolva:

• A \(10\) pontot érő tesztpéldákban: \(N=M, a_i \leq c_i \leq b_i \leq d_i\).

• A \(10\) pontot érő tesztpéldákban: \(a_i = b_i, c_i = d_i\).

• A \(15\) pontot érő tesztpéldákban: \(a_i = b_i\).

• A \(15\) pontot érő tesztpéldákban: \(N = 1\).

• A \(30\) pontot érő tesztpéldákban: \(a_i = c_i = 0\).

• A \(20\) pontot érő tesztpéldákban: nincsenek további korlátozások.