A Brief Gerrymander

The evil ruling party, the Liberatives, are re- distributing the electoral regions (ridings) in your city, and are nefariously attempting to pack certain opposition-friendly neighborhoods into as few ridings as possible. If this plan suc- ceeds, it will be the end of democracy as we know it! As a card-carrying member of the no- ble, compassionate Conservals (the main oppo- sition party), you must foil their devious plot and safeguard the future of our country. Under the new plan, the city will be divided up into a grid of rectangles by selecting certain major streets and avenues as boundaries. All streets and avenues stretch straight across the city, and are numbered starting from the south- west corner of the city. The city is bounded by four roads: 1st Street (west edge), 100th Street (east edge), 1st Avenue (south edge), 100th Avenue (north edge). Clearly these four roads must represent district boundaries; however, only a subset of the streets and avenues in between will divide districts. The Liberatives have already been able to fix the North-South (street) boundaries; however, they have been forced to allow the Conservals to select the East-West (avenue) boundaries. You know the location of all the opposition-friendly neighborhoods, which vote strongly Conserval. A neighborhood is exactly one block between adjacent streets and avenues. For instance, one neighbor- hood might lie between 47th and 48th Street and 67th and 68th Avenue. Place the avenue boundaries so that as many ridings as possible contain at least one opposition-friendly neighborhood. Input Input consists of multiple cases, each describing a city. The first line will give N, the number of Conserval neighborhoods in the city; the following N lines will contain the street and avenue number of the southwest corner of each neighborhood. The next line will contain S, the number of street boundaries, and the S street numbers that they lie on, in increasing order. The final line will consist of A (at least 2), the number of avenue boundaries you must place. Input will be terminated by a line containing ‘-1’. Output For each case, output a single line giving A followed by A distinct avenue numbers for the optimal redistriubution, in increasing order. If there are multiple such solutions, any one will do. Sample Input 2 49 49 50 50 2 1 100

2/2 3 -1 Sample Output 3 1 50 100