Перед вами прямоугольная таблица высоты \(2\) и ширины \(10^9\), состоящая из единичных клеток. На таблице расположено \(n\) прямоугольников, причём границы прямоугольников проходят по границам клеток. \(i\)-й прямоугольник покрывает все клетки в строках с \(u_i\) по \(d_i\) включительно и столбцах с \(l_i\) по \(r_i\) включительно (\(1 \le u_i \le d_i \le 2\); \(1 \le l_i \le r_i \le 10^9\)). Данные прямоугольники могут произвольным образом пересекаться, вкладываться и совпадать.
Вам нужно каждый прямоугольник либо удалить, либо заменить на любой свой непустой подпрямоугольник. Во втором случае подпрямоугольник должен целиком содержаться в исходном прямоугольнике, а его границы всё также должны проходить по границам клеток. При этом разрешается, чтобы подпрямоугольник совпал с исходным прямоугольником.
Требуется, чтобы никакие два (неудаленных) прямоугольника после замены не имели общих клеток, а суммарная площадь, покрытая новыми прямоугольниками, была как можно больше.
Рисунок для первого набора входных данных. Сверху изображены данные прямоугольники, снизу — изменённые. Прямоугольник номер \(4\) был удалён. Выходные данные
Для каждого набора входных данных сначала выведите целое число \(s\) — максимальную возможную площадь, покрытую новыми прямоугольниками. Далее в \(n\) строках выведите ваше решение для покрытия такой площади.
В \(i\)-й из этих строк выведите четыре целых числа \(u'_i, l'_i, d'_i, r'_i\). Если вы удаляете \(i\)-й прямоугольник, выведите \(u'_i = l'_i = d'_i = r'_i = 0\). Иначе эти числа обозначают новые координаты клеток в левом верхнем и правом нижнем углу \(i\)-го прямоугольника соответственно. Они должны удовлетворять следующим неравенствам: \(u_i \le u'_i \le d'_i \le d_i\); \(l_i \le l'_i \le r'_i \le r_i\).
Если существует несколько решений, выведите любое из них.
Примечание
На рисунке в условии задачи изображен первый набор входных данных.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
5
1 2 2 4
2 4 2 8
1 4 2 7
1 2 1 2
1 9 1 10
2
1 1 1 10
1 5 1 15
2
1 1 1 10
1 1 1 10
5
1 3 1 7
1 3 1 8
1 1 1 4
1 2 1 7
1 10 1 11
2
1 1 2 10
1 5 1 8
2
1 5 2 10
1 2 1 7
2
1 5 2 10
2 2 2 15
5
2 6 2 7
1 4 2 5
1 5 1 9
1 7 2 10
1 2 1 6
|
15
1 2 2 4
2 5 2 8
1 5 1 7
0 0 0 0
1 9 1 10
15
1 1 1 10
1 11 1 15
10
1 1 1 10
0 0 0 0
10
0 0 0 0
1 8 1 8
1 1 1 4
1 5 1 7
1 10 1 11
20
1 1 2 10
0 0 0 0
15
1 5 2 10
1 2 1 4
20
1 5 1 10
2 2 2 15
16
2 6 2 6
2 4 2 5
0 0 0 0
1 7 2 10
1 2 1 6
|