時間制限:2000ミリ秒
メモリ制限:65536KB
問題
あなたは画面に長方形を表示するソフトウェアを開発している。そのソフトウェアは、複数の長方形を描画し、それらのいくつかを背景と違う色で塗りつぶす機能をサポートしている。あなたは、そのソフトウェアの重要な機能を実装することになっている。その機能は、「スクリーンの中で、背景と違う色で塗られた部分」の面積を求めるものである。
入力
入力は複数のテストケースを含む。各テストケースの最初の行は、2つの自然数N(1<=N<=20)とM(1<=M<=100000)を含む。Nは画面に描画される長方形の数を示し、Mは面積を求める要求の数を表す。
i+1行目(1<=i<=N)は、それぞれ4つの整数X1,Y1,X2,Y2(0<=X1<X2<=1000,0<=Y1<Y2<=1000)を含む。これは、長方形iの左上の点が(X1,Y1)で、右下の点が(X2,Y2)であることを示す。
最後のM行は、それぞれ各質問の情報を表す。行の最初には整数R(1<=R<=N)があり、その後にR個の整数、Q1,Q2,…,QRが続く。これは、その質問が、「長方形Q1,Q2,…,QRを塗りつぶしたときの色のついている部分の面積」を求める質問であることを示している。
最後のテストケースの後には、2つの0のみを含む行が続く。
出力
各テストケースに対して、テストケース番号(1から始まる)を表す行を出力せよ。
また、各質問に対して、質問番号(各テストケースごとに、1から始まる)を出力し、その後にその質問の答えを出力せよ。各テストケースの最後に、空行を出力せよ。
出力の形式は、出力例を参考にせよ。
入力の例
2 2
0 0 2 2
1 1 3 3
1 1
2 1 2
2 1
0 1 1 2
2 1 3 2
2 1 2
0 0
出力の例
Case 1:
Query 1: 4
Query 2: 7
Case 2:
Query 1: 2
出典
2008 Asia Hefei Regional Contest Online by USTC