题目描述

背景

在中世纪，骑士们率领着庞大的农民军队。当他们需要攻占城堡时，他们会整齐地排列在城堡的墙前，并将抓钩抛过城墙。如果抓钩没有直线抛出，很容易导致两个抓钩交叉，使得两名农民无法攀爬城墙。因此，每位骑士都会让农民们进行大量训练，以避免这种情况在战斗中发生。

由于最近的亚瑟爵士（Sir Arthur）和克莱尔夫人（Madam Claire）的婚姻（ACM），两支农民军队需要合并。

传统上，亚瑟爵士的农民穿着蓝色衣服，克莱尔夫人的农民穿着红色衣服。在共同训练时，两支军队会在城堡的墙前混合排列。在亚瑟爵士的命令下，他们会同时抛出抓钩。由于他们的完美训练，同一军队内的抓钩永远不会交叉，但蓝色农民抛出的抓钩可能会与红色农民抛出的抓钩交叉。

出于统计目的，亚瑟爵士现在需要找出有多少对抓钩发生了交叉，以便衡量两支军队的融合程度。

问题

给定蓝色和红色农民的位置以及他们抛出抓钩的位置，计算有多少对蓝色和红色农民的抓钩发生了交叉。

如果有$n$名蓝色农民和$m$名红色农民，农民站立的队列位置编号为$1$到$n + m$。城堡墙上的位置也编号为$1$到$n + m$，其中墙上的位置$i$与队列中的位置$i$正对。一个从队列位置$i$抛出到墙上位置$j$的抓钩与另一个从队列位置$k$抛出到墙上位置$l$的抓钩交叉，当且仅当满足以下条件之一：

1. $(i < k$ 且 $j \geq l)$
2. $(i > k$ 且 $j \leq l)$

同一颜色的抓钩永远不会交叉，且队列中不会有两位农民站在同一位置。然而，不同颜色的抓钩可能会抛到墙上的同一位置，此时它们也会被视为交叉。

输入格式

第一行包含测试场景的数量。

每个测试场景的第一行是两个整数$n$和$m$，分别表示蓝色和红色农民的数量（$1 \leq n, m \leq 30\,000$）。

接下来的$n$行描述蓝色农民，随后$m$行描述红色农民。每行包含两个整数$i$和$j$，表示农民在队列中的位置$i$和抛出抓钩的墙上位置$j$（$1 \leq i, j \leq n + m$）。

输出格式

对于每个测试场景，首先输出一行"Scenario #i:"，其中$i$是场景编号（从1开始）。接下来输出一行，包含交叉的抓钩对数，并在每个场景结束后输出一个空行。

示例输入

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

示例输出

Scenario #1:
2

Scenario #2:
6

来源

TUD Programming Contest 2004, Darmstadt, Germany