성벽 위의 갈고리

중세 시대에 기사들은 수많은 소작농으로 이루어진 군대를 이끌었다. 성을 공격할 때 소작농들은 성벽 앞에 한 줄로 늘어서서 갈고리를 벽 너머로 던진다. 갈고리를 똑바로 던지지 못하면 두 갈고리가 서로 교차할 수 있고, 그러면 그 두 소작농은 벽을 오를 수 없게 된다. 그래서 잘 훈련된 소작농의 갈고리는 서로 교차하지 않는다.

최근 아서 경과 클레어 부인의 결혼(ACM)으로 두 소작농 군대를 합치게 되었다. 아서 경의 소작농은 파란색, 클레어 부인의 소작농은 빨간색 옷을 입는다. 함께 훈련할 때 두 군대는 성벽 앞에서 뒤섞이고, 명령이 떨어지면 모두 갈고리를 던진다. 훈련 덕분에 같은 색 갈고리끼리는 절대 교차하지 않지만, 파란색 갈고리와 빨간색 갈고리는 교차할 수 있다.

두 군대가 얼마나 잘 섞였는지 재기 위해, 갈고리가 교차하는 서로 다른 색 소작농 쌍(파란색–빨간색)이 몇 개인지 세어라.

파란색 소작농은 $n$명, 빨간색 소작농은 $m$명이다. 소작농이 서 있는 줄의 위치는 $1$부터 $n + m$까지 번호가 매겨지고, 성벽의 위치도 $1$부터 $n + m$까지 번호가 매겨진다. 벽의 위치 $i$는 줄의 위치 $i$의 바로 맞은편이다. 줄의 위치 $i$에서 벽의 위치 $j$로 던진 갈고리는, 위치 $k$에서 $l$로 던진 갈고리와 다음 조건을 만족할 때 교차한다.

$(i < k \text{ 이고 } j \ge l) \quad\text{또는}\quad (i > k \text{ 이고 } j \le l).$

어떤 두 소작농도 줄에서 같은 위치에 서지 않으며, 같은 색 갈고리끼리는 절대 교차하지 않는다. 서로 다른 색 갈고리 두 개는 같은 벽 위치로 던져질 수 있으며, 이 경우에도 교차하는 것으로 본다.

첫 번째 줄에는 시나리오의 수가 주어진다.

각 시나리오는 두 정수 $n$과 $m$이 주어지는 줄로 시작한다. 각각 파란색 소작농과 빨간색 소작농의 수이다 ($1 \le n, m \le 30000$).

이어서 파란색 소작농을 나타내는 $n$개의 줄, 그다음 빨간색 소작농을 나타내는 $m$개의 줄이 주어진다. 각 줄에는 두 정수 $i$와 $j$가 주어진다 ($1 \le i, j \le n + m$). 해당 소작농은 줄의 위치 $i$에 서 있으며 벽의 위치 $j$로 갈고리를 던졌다.

각 시나리오마다 Scenario #i: 형식의 줄을 출력한다. 여기서 i는 $1$부터 시작하는 시나리오 번호이다. 이어서 갈고리가 교차하는 서로 다른 색 소작농 쌍의 개수를 한 줄에 출력한다. 연속한 두 시나리오 사이에는 빈 줄을 하나 출력한다.