← 返回题目列表

Codeforces · 1080/C

C. 玛莎和两个朋友

中文机器翻译题面 查看原题

最近,玛莎收到了一个高度为 $$$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 \le t \le 10^3$$$) — 测试用例的数量。

它们中的每一个都按以下格式描述:

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n,m \le 10^9$$$) — 棋盘的大小。

第二行包含四个整数 $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \le x_1 \le x_2 \le m, 1 \le y_1 \le y_2 \le n$$$) — 矩形的坐标,白色油漆洒在上面。

第三行包含四个整数 $$$x_3$$$, $$$y_3$$$, $$$x_4$$$, $$$y_4$$$ ($$$1 \le x_3 \le x_4 \le m, 1 \le y_3 \le y_4 \le n$$$) — 矩形的坐标,黑色颜料洒在上面。

输出

输出 $$$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

输出 #1

0 4
3 9
2 3
8 8
4 8

注意

示例说明:

每个插图的第一张图片显示了染料溢出之前田地的样子。每个插图的第二张图片显示了马克西姆损坏的白色染料后田野的样子(染料溢出的矩形以红色突出显示)。每幅插图中的第三张图片显示了丹尼斯破坏黑色染料后田野的样子(染料溢出的矩形以红色突出显示)。

第一次测试中,场上油漆变化如下:

第二次测试中,场上油漆变化如下:

第三次测试中,场上油漆变化如下:

第四次测试中,场上油漆变化如下:

第五次测试中,场上油漆变化如下: