სახანძრო საგუშაგო

დროის ლიმიტი: 7 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 16, ეტაპი 1


ბაიტლენდის ქალაქ, ბაიტლებდში ქუჩების საკმაოდ მარტივი განლაგება აქვთ - ჩრდილოეთიდან სამხრეთით ან აღმოსავლეთიდან დასავლეთით. მარტივი შესამჩნევია ისიც, რომ თითოეული ჰორიზონტალური და ვერტიკალური ქუჩა ერთმანეთს კვეთენ მხოლოდ ერთ წერტილში. ამასთან, გზაჯვარედინებით გამოყოფილი ქუჩის პატარა მონაკვეთების სიგრძე არის 1 კმ.

ბაიტლენდში გვხვდება არაერთი ისტორიული შენობა, რომელთაგან თითოეული განლაგებულია გზაჯვარედინებზე. მერია ძალიან მოტივირებული და მონდომებულია დაიცვას თავიანთი უნიკალური ღირსშესანიშნაობები, ამ მიზნით , გადაწყვიტეს ქალაქში ორი სახანძრო-სამაშველო სადგურის მოწყობა. სახანძრო გუნდი პასუხისმგებელი იქნება მათთან ახლოს მდებარე შენობის დაცვაში, ღირსშესანიშნაობები რომლებიც თანაბრად იქნება დაშორებული ორივე სადგურიდან, შესაბამისად - ორივე დაიცავს.

შენობები ბაიტლენდში საკმაოდ მყარია, მანძილი საგუშაგოდან ღირსშესანიშნაობამდე არის უმოკლესი მარშუტის სიგრძე გზების გავლით.

ქალაქის მერიამ უკვე არადგინა რამდენი პროექტი საგუშაოგების განსალაგებლად, თქვენ უნდა დაეხმაროთ მათ დეტალების განსაზღვრაში და უთხრათ რამდენი შენობის დაცვა შეუძლია პირველ საგუშაგოს, მეორეს ან ორივეს ერთად.

 შემომავალი პარამეტრები:

სტანდარტული შემომავალი პარამეტრების პირველი ხაზი შეიცავს ერთმანეთისგან ცარიელი სიმბოლოთი გამოყოფილ მთელ რიცხვებს: n, m, z და p (1 ⩽ n,m ⩽ 1 000 000 000, 1 ⩽ z,p ⩽ 100 000). შესაბამისი მიმდევრობით, ეს რიცხვები წარმოადგენს: ჰორიზონტალური ქუჩების რაოდენობას, ვერტიკალური ქუჩების რაოდენობას, დაცული შენობების და მერიის მიერ წარმოდგენილი პროექტების რაოდენობებს.

ქუჩები ჩრდილოეთიდან სამხრეთის მიმართულებით დანომრილია 1 დან n-მდე, ხოლო ქუჩები აღმოსავლეთიდან-დასავლეთით 1 დან m-მდე, რაც გვაძლევს საშუალებას თითოეულ გზაჯვარედინს შესაბამისი (x,y) კოორდინატი მივანიჭოთ.

ყოველი შემდეგი ხაზი, წარმოადგენს ამ კოოდინატების კომბინაციას x i და y i ,გამოყოფილს ცარიელი სიმბოლოთი(1 ⩽ x and ⩽ n,1 ⩽ y and ⩽ m), და თითოეული განსაღვრავ მე-i-ურე შენობის მდებარეობას. (ერთი და იმავე კოორდინატზე არ გვხვდება 1-ზე მეტი შენობა).

ყოველი p ხაზი, რომელიც 4 მთელი რიცხვისგან წარმოდგება (xj,1, yj,1, xj,2, yj,2; 1 ⩽ x j, 1 , x j, 2 ⩽ n,1 ⩽ y j, 1 , y j, 2 ⩽ m, (x j, 1 , y j, 1 ) = (x j, 2 , y j, 2 )) და გამოყოფილია ცარიელი სიმბოლოთი, წარმოადგეს მერიის მიერ წარდგენილ  2 სახანძრო პუნქტის განლაგების გეგმას. საიდანაც რიცხვების პირველი და მეორე წყვილი შესაბამისად წარმოადგენს სახაძრო პუნქტების კოორდინატებს. (x j, 1 , y j, 1 ) და (x j, 2 , y j, 2 ) , სადაც  (1 ⩽ j ⩽ p).

გამომავალი პარამეტრები:

პროგრამამ უნდა დაბეჭდოს შესაბამისი შედეგების p რაოდენობის ხაზი. ყოველი მე-j-იურე ხაზი, რომელიც მოიცავს: პირველი პუნქტის დაცვის ქვეშ მყოფი შენობების რაოდენობას, მეორე სახანძრო პუნქტის დაცვის ქვეშ მყოფი შენობების რაოდენობას, და იმ შენობების რაოდენობას რომელზეც ორივე ერთდროულადაა პასუხისმგებელი. რიცხვები გამოყოფილია ცარიელი სიმბოლოთი.




მაგალითები

შესატანი მონაცემები
6 5 6 1 1 2 6 5 5 1 3 3 3 4 4 1 2 3 4 3 დაკოპირება
გამოსატანი მონაცემები
1 3 2 დაკოპირება