Недавно Маше подарили шахматную доску высотой \(n\) и шириной \(m\).
Строки на шахматном поле нумеруются от \(1\) до \(n\) снизу вверх. Столбцы нумеруются от \(1\) до \(m\) слева направо. Поэтому, каждую клетку можно задать координатами \((x,y)\), где \(x\) — номер столбца, а \(y\) — номер строки (не перепутайте).
Назовём прямоугольником с координатами \((a,b,c,d)\) такой прямоугольник, у которого левая нижняя точка имеет координаты \((a,b)\), а правая верхняя — \((c,d)\).
Шахматная доска окрашена в чёрный и белый цвета следующим образом:
Пример шахматного поля. Маша была очень рада подарку и, поэтому, пригласила своих друзей Максима и Дениса, чтобы похвастаться им. Парни решили сделать ей приятное — подарить банку белой и банку чёрной краски, чтобы если старая доска испортится, можно было перекрасить. Когда они пришли к Маше, случилось неприятное: сначала Максим зацепился за порог и пролил белую краску на прямоугольник \((x_1,y_1,x_2,y_2)\). Затем после него Денис пролил чёрную краску на прямоугольник \((x_3,y_3,x_4,y_4)\).
Пролить краску цвета \(color\) на некий прямоугольник, означает сделать все клетки, которые принадлежат данному прямоугольнику, цвета \(color\). Покраски клеток накладываются друг на друга (если на какую-то клетку сначала пролили белую краску, а потом чёрную, то её цвет будет чёрным).
Маша была просто в шоке! Она прогнала гостей и решила узнать насколько испорчен подарок. Для этого ей почему-то надо знать количество клеток белого и чёрного цвета. Помогите ей найти эти числа!
Выходные данные
Выведите \(t\) строк, каждая из которых содержит по два числа — количество клеток белого и чёрного цвета после разлива краски соответственно.
Примечание
Объяснение к примерам:
Первое изображение каждой иллюстрации показывает, как поле выглядело до того, как краски были пролиты. Второе изображение каждой иллюстрации показывает, как поле выглядело после того, как Максим пролил белую краску (прямоугольник, на который пролилась краска, выделен красным). Третье изображение на каждой иллюстрации показывает, как поле выглядело после того, как Денис пролил черную краску (прямоугольник, на который пролилась краска, выделен красным).
В первом тесте краска на поле менялась следующим образом:
Во втором тесте краска на поле менялась следующим образом:
В третьем тесте краска на поле менялась следующим образом:
В четвёртом тесте краска на поле менялась следующим образом:
В пятом тесте краска на поле менялась следующим образом:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 2
1 1 2 2
1 1 2 2
3 4
2 2 3 2
3 1 4 3
1 5
1 1 5 1
3 1 5 1
4 4
1 1 4 2
1 3 4 4
3 4
1 2 4 2
2 1 3 3
|
0 4
3 9
2 3
8 8
4 8
|