Evinizi Alın#5703
Siz ev almaq istəyirsiniz və bu məqsədlə yeni fəaliyyətə başlamış bir daşınmaz əmlak inkişaf şirkəti ilə əlaqə saxlamısınız. Siz onların ilk alıcısı olduğunuz üçün xüsusi bir təklif alırsınız.
Şirkətin eni W və hündürlüyü H olan düzbucaqlı formalı bir torpaq sahəsi var. Onlar torpağı ölçmək üçün koordinat sistemindən istifadə edirlər. (0, 0) nöqtəsi torpağın sol alt küncüdür və torpağın alt kənarından x məsafədə, sol kənarından isə y məsafədə olan hər hansı bir nöqtə koordinat sistemində (x, y) kimi göstərilir.
Şirkət artıq bu torpaq sahəsində bəzi evlər tikib. Bütün evlər düzbucaqlı formadadır və kənarları torpağın kənarlarına paraleldir. Bir evin yeri dörd tam ədəd x_1, y_1, x_2, y_2 ilə müəyyən edilir. Burada (x_1, y_1) evin sol alt küncü, (x_2, y_2) isə sağ üst küncüdür.
Xüsusi təklif ondan ibarətdir ki, siz dəqiq bir ev olan və istənilən miqdarda bitişik açıq sahə olan hər hansı bir düzbucaqlı sahəni seçə bilərsiniz. Açıq sahəni almağa kifayət qədər pulunuz olmaya bilər və yalnız bir evin yerləşdiyi sahəni almağı seçə bilərsiniz. Əgər kifayət qədər pulunuz varsa, evinizin qarşısında bağçılıq üçün açıq sahə saxlaya bilərsiniz!
Amma bəzi məhdudiyyətlər var. Onların torpağın qalan hissəsindən gələcəkdə istifadəsini asanlaşdırmaq üçün yalnız düzbucaqlı formalı bir sahə seçə bilərsiniz və kənarları əsas torpağın kənarlarına paralel olmalıdır. Seçdiyiniz sahənin küncləri tam ədədlərdən ibarət koordinatlar olmalıdır. Bu (3, 2) ola bilər, amma (3.5, 2) ola bilməz. Bir evin bir hissəsinin sahənin içində, digər hissəsinin isə sahənin xaricində olduğu bir sahə seçə bilməzsiniz. Bir evdən çox olan və heç bir ev olmayan bir sahə seçə bilməzsiniz. Yuxarıda göstərilən qaydalara uyğun olaraq torpağınızı neçə yolla seçə bilərsiniz?
Giriş bir tam ədəd T (T təxminən 500), test hallarının sayından başlayacaq. Hər bir test halı iki tam ədəd W və H (1 ≤ W, H ≤ 1000000000), torpağın eni və hündürlüyü ilə başlayır və növbəti sətir torpaq sahəsindəki evlərin sayını göstərən bir tam ədəd N (1 ≤ N ≤ 50) ehtiva edir. Növbəti N sətirin hər biri evin yerini təsvir edən dörd tam ədəd x_1, y_1, x_2, y_2 (0 ≤ x_{1 }< x_2 ≤ W və 0 ≤ y_1 < y_2 ≤ H) ehtiva edəcək. Qeyd edək ki, heç bir ev digər evlə üst-üstə düşə bilməz və verilmiş bütün koordinatlar qeyri-mənfi tam ədədlər olacaq.
Hər bir giriş üçün "Case #: W" formasında bir sətir çap edin, burada '#' hal nömrəsi ilə əvəz olunacaq və W torpağınızı neçə yolla seçə biləcəyinizlə əvəz olunacaq. Burada W çox böyük ola bilər, buna görə də W sayını 1000000007 modulunda çap etməlisiniz.
Nümunə 1