SPOJ Brasil

Compadre Roberto teve uma agradável surpresa: recebeu um telefonema de sua irmã dizendo que eles eram os únicos herdeiros das terras dos seus tios. Logo em seguida recebeu um fax com a descrição dos terrenos. Todos eram retangulares, e pela largura e comprimento de cada um concluiu que herdou uma grande área de terra no triângulo mineiro! Não tardou e Compadre Roberto já estava lá para tomar posse dos terrenos.

Chegando lá, uma surpresa nada agradável... os terrenos eram sobrepostos!! Ninguém conseguiu explicar como isso aconteceu, mas boa parte das terras dos seus tios não pertenciam a apenas um, mas a dois ou mais! Isso nunca foi problema para eles, que cuidavam de tudo como uma grande família, sem se preocupar exatamente que pedaço era de quem. Tampouco é problema para Compadre Roberto e sua irmã, que agora são os únicos donos. Mas é frustrante descobrir que o terreno não era tudo o que pensava...

A figura abaixo mostra um exemplo com 3 terrenos. Os terrenos são descritos com quatro números inteiros X, Y, L, C, indicando que o canto sudoeste do terreno (na figura, o canto inferior esquerdo) está na coordenada (X,Y) e ele tem largura L e comprimento C (todos os valores dados em Km). A descrição dos 3 terrenos mostrados é: Terreno A: 1 2 2 4; Terreno B: 2 0 3 3; Terreno C: 0 4 4 1. A figura da esquerda mostra os terrenos, e a da direita o terreno total resultado da sobreposição.

Quando Compadre Roberto recebeu o fax, achava que esses terrenos tinham 2 * 4 + 3 * 3 + 4 * 1 = 21 Km² no total. Agora sabe que são 18 Km²...

Ele gostaria de saber quantos Km² os terrenos realmente contêm. E com as muitas sobreposições precisa da sua ajuda. Além disso precisa cercar o terreno, então gostaria de saber também quantos Km de cerca são necessários. No exemplo acima a cerca tem 24 Km de comprimento.

Observações

A junção dos terrenos nem sempre forma uma região contígua e sem “buracos”. Casos como os mostrados na figura abaixo podem acontecer. Então nem sempre será possível cercar o terreno herdado com uma única cerca contígua, pode ser necessário usar mais de uma.

Entrada

Há vários casos de teste.

A primeira linha de um caso de teste contém um número inteiro N que é o número de terrenos herdados (N ≤ 20). As N linhas seguintes contém cada uma a descrição de um terreno no formato X Y L C conforme descrito no enunciado ( 0 ≤ X, Y ≤ 1000, e 1 ≤ L, C ≤ 500).

A entrada termina quando N = 0

Saída

Para cada caso de teste da entrada seu programa deve produzir uma linha na saída contendo dois valores A e P, que são a área (em Km²) e o perímetro (em Km) total da união dos terrenos descritos no caso de teste.

Exemplos

Entrada:
3
1 2 2 4
2 0 3 3
0 4 4 1
5
1 2 1 1
1 2 5 1
2 5 4 2
4 0 1 6
1 0 2 4
4
0 0 1 4
0 3 4 1
3 0 1 4
1 0 2 1
0

Saída:
18 24
23 36
12 24