Description
A skyline is the outline formed by a group of buildings against the sky. The ACM city in Second Life, which has been built with a beautiful skyline that's visible to anyone that approaches it, sold the rights to place advertisement at the approaches to the city to a company as long as it does so while preserving the shape of the city's skyline. The company wants to accept all requests for advertising that are of rectangular shape and can be fully placed, with sides parallel to edges of the skyline as shown shaded in the example below, within the interior of the skyline.
Each skyline of the ACM city is formed by N buildings, all with a width of one (1) but with different heights. The height of each building is between 0 and 1000, inclusive and the number of buildings N is between 1 and 400, inclusive. The example below shows a skyline with six (6) buildings, and an advertisement of size 3 by 5 (shown in gray) placed parallel to the sides of the skyline. Note that an advertisement may be rotated by 90o so that it can fit into the skyline. That is, advertisement of size 5 by 3 can be placed within the skyline by rotating it first. It is ``Second Life" after all.
Your task is to write a program to read the descriptions of a number of skylines and advertising requests, and decide for each request whether it should be accepted or rejected. Each request is to be checked independently as only one advertisement will be displayed at any time.
Input
The first line of the input contains a single integer C between 1 and 1000, inclusive, which is the number of cases that follow. Each case starts with a description of the skyline of the city from one approach that consists of two lines:
- The first line contains an integer N , 1 ≤ N ≤ 400 , that is the number of buildings in the skyline
- The second line contains the heights of the buildings
followed by a sequence of advertising requests. Each request consists of two integers on a single line, separated by a single space, which describe the length of the two sides of the rectangle that contains the advertisement. Both lengths are between 1 and 1000, inclusive. A request of two zeros separated by a single space (0 0) terminates the case.
Output
For each skyline the output starts with a line that contains the case number starting with the value of one (1), followed by a ``:", as shown in the Sample Output below, and then followed by a sequence of decisions of ``Accept" or ``Reject", on a separate line, for each request.