O deus dos mares, Poseidon, está furioso. As K Ilhas Errantes (numeradas de 1 a K), rochas mágicas que vagam pelo Mar Egeu, estão causando naufrágios constantes. Para acalmar os mares, Zeus ordenou que as ilhas sejam fixadas permanentemente em uma grade divina de tamanho K x K.

Nesta grade, cada ilha deve ocupar exatamente uma célula. As células que não contêm ilhas representam o mar aberto e devem ser marcadas com o número 0.

No entanto, as ilhas possuem vontades antigas e só aceitam ser posicionadas se respeitarem certas hierarquias geográficas. Os Oráculos de Delfos consultaram os ventos e lhe entregaram dois pergaminhos sagrados:

• O Pergaminho de Bóreas (Vento Norte): Contém profecias sobre qual ilha exige estar mais ao Norte (linhas superiores) que outra.

• O Pergaminho de Zéfiro (Vento Oeste): Contém profecias sobre qual ilha exige estar mais ao Oeste (colunas à esquerda) que outra.

Sua missão, como o Arquiteto do Olimpo, é construir o mapa final. Se as profecias forem contraditórias (criarem um ciclo impossível), o caos reinará e você deve informar que a tarefa é impossível.

A Prioridade Divina: Como a disposição das ilhas pode ter múltiplas soluções válidas, Zeus decretou uma regra de ouro para manter a ordem: sempre que houver mais de uma ilha disponível para ser colocada em uma posição (ou seja, todas as ilhas que deveriam estar ao Norte ou a Oeste dela já foram posicionadas), você deve escolher a ilha com o menor número identificador (a mais antiga).

Entrada

A entrada é composta por diversas linhas:

A primeira linha contém um inteiro K ($2 \le K \le 400$), representando o número de ilhas e a dimensão da grade.

A segunda linha contém um inteiro L, representando a quantidade de restrições de latitude (linhas). As próximas L linhas contêm, cada uma, dois inteiros acima e abaixo, indicando que a ilha acima deve estar em uma linha superior à da ilha abaixo.

A linha seguinte contém um inteiro C, representando a quantidade de restrições de longitude (colunas). As próximas C linhas contêm, cada uma, dois inteiros esquerda e direita, indicando que a ilha esquerda deve estar em uma coluna à esquerda da ilha direita.

Saída

Se for possível construir o mapa, imprima K linhas. Cada linha deve conter K números inteiros separados por espaço, representando a grade. Use 0 para espaços vazios.

Se não for possível satisfazer todas as condições, imprima apenas a palavra “IMPOSSIVEL”.

Exemplos

Exemplo 1:

Entrada:

3  
2  
1 2  
3 2  
2  
2 1  
3 2  

Saída:

0 0 1  
3 0 0  
0 2 0  

Exemplo 2:

Entrada:

3  
3  
1 2  
2 3  
3 1  
0  

Saída:

IMPOSSIVEL

Exemplo 3:

Entrada:

4  
0  
0  

Saída:

1 0 0 0  
0 2 0 0  
0 0 3 0  
0 0 0 4