SPOJ in Armenian

Մինչև Էդուարդը գնացել էր խանութ առևտուր անելու տան համար , N չարաճճի երեխաներ սև գույնով ներկել էին Էդուարդի տան սպիտակ ցանկապատը: Էդուարդի տան ցանկապատը իրենից ներկայացնում է X և Y կողմերով ուղղանկյուն: Երեխաները ներկել էին ցանկապատը ենթաուղղանկյուններով, այսինքն ամեն մեկը ընտրել էր (x1, y1) , (x2, y2) (x1 ≤ x2 և y1 ≤ y2) կորդինատներ և ներկել այդ տարածքը: Հասնելով տուն Էդուարդը բարկացավ, բայց որոշ ժամանակ անց Էդուարդի մտքով անցավ հետաքրքիր խնդիր:

Քանի եղանակով կարող ենք ընտրել W x H կողմերով ուղղանկյուն ցանկապատի վրա այնպես, որ բոլոր կետերը այդ ուղղանկյան մեջ լինեն սպիտակ գույնի:

Էդուարդը շատ արագ լուծեց այդ խնդիրը և հիմա ձեզ առաջարկում է լուծել այդ խնդիրը D տարբեր ուղղանկյունների համար (իրարից անկախ):

Մուտքային տվյալներ

Առաջին տողում տրված են 4 ամբողջ թվեր՝ X, Y, N, D:

1 ≤ X,Y ≤ 2000 , 0 ≤ N ≤ 10^6, 1 ≤ D ≤ 100 000

Հաջորդ N տողերից յուրաքանչյուրում տրված է x1, x2, y1, y2 ամբողջ թվերը , որտեղ

 0 ≤ x1  < x2 ≤ X , 0 ≤ y1 < y2 ≤ Y, (x1, y1)-ը երեխայի ներկած ուղղանկյան ներքևի ձախ անկյան կորդինատներն է, իսկ (x2, y2)-ը ՝ աջ վերևի անկյան:

Հաջորդ D տողերից յուրաքանչյուրում տրված է w, h թվերը, 0 < w ≤ X, 0 < h ≤ Y:

Ելքային տվյալներ

Ելքում արտածել D հատ թիվ ՝ յուրաքանչյուր հարցման պատասխանը:

Օրինակ

Մուտք
7 5 3 9
1 2 0 1
5 7 2 5
0 1 2 4
7 1
3 5
5 3
2 2
3 3
4 4
4 5
6 2
1 1

Ելք
1
1
0
13
5
1
0
0
26