Програмчлалын олимпиадын бодлогын архив

А нэгж өргөнтэй, В нэгж урттай цагаан өнгийн тэгш өнцөгт дээр төрөл бүрийн өнгөтэй N тооны тэгш өнцөгтийг, талууд нь анхны цагаан тэгш өнцөгтийн талтай параллель байхаар тавьжээ. Үүний үр дүнд төрөл бүрийн өнгөтэй мужууд үүссэн бол өнгө тус бүр ямар талбайтай муж үүсгэж буйг тооцоолох програм бич. Үүнд тус, тусдаа байгаа боловч өнгө нь ижил мужийг нэг муж гэж үзнэ. Цагаан цаасыг тэгш өнцөгт координатын систем гэж үзвэл тооллын эх нь цагаан цаасны зүүн доор байна.

Input

Оролтын файлын эхний мөрөнд цагаан цаасны хэмжээг заах А, В (1 ≤ A, B ≤ 10000) тоонууд, өнгөт тэгш өнцөгтийн тоог заах N (1 ≤ N ≤ 1000) тоо байна. Дараагийн N тооны мөрөнд, мөр бүрд 5 бүхэл тоо байна. Энэ нь тавьж буй тэгш өнцөгтийн зүүн доод, баруун дээд оройн координатууд ба уг тэгш өнцөгтийн өнгө болно. Хамгийн олондоо 2500 ялгаатай өнгө байна. Цагаан өнгө нь 1 кодтой.

Output

Гаралтын файлд өнгө бүр ямар талбайтай муж үүсгэж буйг гаргана. Эхлээд өнгөний код хоосон зайгаар тусгаарлаад уг кодтой хэдий хэрийн талбай байгааг гаргана. Хоосон талбайтай өнгийг гаргахгүй.

Example

Input:
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4


Output:
1 91
2 84
3 187
4 38