Problema C - Comprar Pixels

Alex Tew é um estudante britânico de 21 anos sem meios financeiros para poder continuar os seus estudos na Universidade. Para conseguir angariar o dinheiro necessário teve um ideia pioneira e muito inovadora: resolveu criar um página onde colocava à venda 1,000,000 de pixels, ao preço de 1 dólar cada um. Quem quiser contribuir, compra um bloco rectangular de pixels e pode colocar lá a imagem que quiser, publicitando por exemplo uma empresa. Alex compromete-se a usar uma parte do dinheiro para deixar a página online vários anos e em troca quem compra os pixels pode ganhar o seu espaço num site que fica para história da internet. Esta simples ideia correu o mundo e em pouco tempo Alex conseguiu o ambicionado milhão de dólares.

Procurando imitar este sucesso, decidiste também colocar uma série de pixels à venda. A tua página terá à venda um enorme rectângulo de pixeis inicialmente vazios e num dado momento qualquer pessoa pode comprar um rectângulo de pixels adjacentes, desde ainda estejam todos livres. Para ajudar, queres automatizar o processo de, dadas as dimensões do rectângulo a comprar, sugerir um espaço livre. A ideia é mostrar ao comprador o espaço o mais possível em cima e à esquerda onde cabe o rectângulo de pixels a comprar.

Imagina por exemplo que estás a vender um rectângulo de 10 linhas por 15 colunas e que já vendeste os três rectangulos coloridos da figura:

Se alguém quiser comprar um quadrado de lado 4, existem vários sítios para o colocar. Se considerarmos, como pedido, que devemos escolher o que está mais acima e, em caso de empate, o que fica mais à esquerda, vemos que a sugestão seria colocá-lo na posição indicada a cinzento:

Já se o rectângulo a comprar fosse de 6 linhas por 7 colunas, seria impossível colocá-lo.

Será que consegues criar um programa para ajudar neste processo de decisão?

O Problema

Dado as dimensões inicias de um rectângulo global de pixels L por C pixels (indicando o número de linhas e colunas), dadas as dimensões e posições de R rectângulos mais pequenos (já comprados) e dadas as dimensões N_L por N_C pixels do rectângulo a comprar, a tua tarefa é descobrir se existe um sítio livre onde é possível colocar o rectângulo a comprar (sem o rodar). Caso seja possível, deves indicar qual o sítio mais acima (e em caso de empate o mais à esquerda) onde o deves colocar.

Input

Na primeira linha do input vem um único número inteiro K indicando o número de casos a considerar (1 ≤K≤10).

Seguem-se exactamente K casos de teste, cada um constituído pelas seguintes linhas:

• Uma primeira com dois números inteiros L e C indicando as dimensões em pixels do rectângulo global disponível para vender, indicando respectivamente o número de linhas e colunas (1≤L,C≤1 000 000).
• Uma segunda linha com dois números inteiros N_L por N_C indicando respectivamente o número de linhas e colunas do rectângulo que se deseja comprar (1≤N_L≤L e 1≤N_C≤C).
• Uma terceira linha contendo um único inteiro R indicando o número de rectângulos já comprados (0≤R≤500).
• Seguem-se exactamente R linhas, cada uma contendo 4 inteiros Y₁, X₁, Y₂ e X₂, separados por espaços únicos, indicando que existe um rectângulo comprado com linhas entre Y₁ e Y₂ (inclusive) e colunas entre X₁ e X₂ (inclusive) (1≤Y₁≤Y₂≤L e 1≤X₁≤X₂≤C). Estes rectângulos não estão por nenhuma ordem em específico e é garantido que não se intersectam.

Para esclarecer qualquer dúvida relativa ao input nota que o primeiro caso de exemplo corresponde às figura mostradas na introdução do problema.

Output

O output é constituído exactamente por K linhas, cada uma contendo a resposta para o respectivo caso (na mesma ordem em que aparecem no input).

Cada uma das respostas deve conter:

• Caso seja possível colocar o rectângulo (sem o rodar), dois números inteiros Y X separados por um espaço indicando a coordenada superior esquerda da posição onde o rectângulo deve ser colocado (relembra que deves escolher a posição o mais acima possível e em caso de empate o mais à esquerda possível).
• Caso seja impossível colocar o rectângulo, a mensagem "Impossivel" (sem as aspas e sem acentos).

Nota sobre a avaliação

Para um conjunto de casos de teste valendo 60% dos pontos, o rectângulo global tem dimensões inferiores ou iguais a 1000x1000.
 

Exemplo de Input

3
10 15
4 4
3
2 2 5 4
6 8 8 12
2 9 3 13
10 15
6 7
3
2 2 5 4
6 8 8 12
2 9 3 13
10 10
2 2
2
1 1 3 3
1 4 1 10

Exemplo de Output

1 5
Impossivel
2 4