[HomeTrainingProblemsContestsC Language]  [LoginRegister] 
Problems Status Rank 
Problem 1105
Rectangles
Time Limit: 2000ms
Memory Limit: 65536kb Description
You are developing a software for painting rectangles on the screen. The software supports drawing several rectangles and filling some of them with a color different from the color of the background. You are to implement an important function. The function answer such queries as what is the colored area if a subset of rectangles on the screen are filled.
Input
The input consists of multiple test cases. Each test case starts with a line containing two integers N(1 ≤ N ≤ 20) and M(1 ≤ M ≤ 100000), indicating the number of rectangles on the screen and the number of queries, respectively.The ith line of the following N lines contains four integers X_{1},Y_{1},X_{2},Y_{2} (0 ≤ X_{1} < X_{2} ≤ 1000, 0 ≤ Y_{1} < Y_{2} ≤ 1000), which indicate that the lowerleft and upperright coordinates of the ith rectangle are (X_{1}, Y_{1}) and (X_{2}, Y_{2}). Rectangles are numbered from 1 to N. The last M lines of each test case describe M queries. Each query starts with a integer R(1 ≤ R ≤ N), which is the number of rectangles the query is supposed to fill. The following list of R integers in the same line gives the rectangles the query is supposed to fill, each integer of which will be between 1 and N, inclusive. The last test case is followed by a line containing two zeros. Output
For each test case, print a line containing the test case number(beginning with 1).For each query in the input, print a line containing the query number (beginning with 1) followed by the corresponding answer for the query. Print a blank line after the output for each test case. Sample Input
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 Sample Output
Case 1: Query 1: 4 Query 2: 7 Case 2: Query 1: 2 Source
2008 Asia Regional, Hefei, Preliminary
