თამაში

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

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

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

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

წყარო: IBSU, 2015, ზამთრის ოლიმპიადა, IX-X


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

·      NxM ზომის უჯრებიანი დაფა. დაფის თითოეული უჯრა ან თავისუფალია, ან გადაადგილებისათვის ბლოკირებულია;

·      Q რაოდენობის სათამაშო ბარათი. თითოეული ბარათი შეიცავს სასტარტო უჯრების A სიმრავლის, დამატებით ბლოკირებადი უჯრების B სიმრავლის და საბოლოო უჯრების C სიმრავლის აღწერას. A, B და C სიმრავლეები არაცარიელია, წყვილ-წყვილად არათანამკვეთია და შეიცავენ თავისუფალ უჯრებს;

·      ერთი ცალი სათამაშო ფირფიტა.

თამაშის წესები ძალიან მარტივია. მოთამაშეები მიმდევრობით გაათამაშებენ სათამაშო ბარათებს. როგორც კი გაიხსნება მორიგი ბარათი, მოთამაშემ უნდა გამოთვალოს, თუ რამდენი კარგი ისეთი (ai,bj,ck) უჯრათა სამეული არსებობს, სადაც  ai ϵ A, bj ϵ B, ck ϵ C. უჯრათა სამეული კარგია, თუ შესაძლებელია ფირფიტის გადაადგილება სასტარტო ai უჯრიდან საბოლოო ck უჯრაში ისე, რომ არ გავიაროთ bj უჯრაზე. ფირფიტის გადადგილების წესები ასეთია:

1.      ფირფიტის გადაადგილება შეიძლება მხოლოდ ქვემოთ და მარჯვნივ დაფის ფარგლებში;

2.      ბლოკირებულ უჯრებზე გავლა არ შეიძლება;

3.      ფირფიტის გადაადგილების დროს bj უჯრაც ბლოკირებულად ითვლება.

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

შესატანი მონაცემები: სტანდარტული შეტანის პირველ სტრიქონში მოცემულია ორი მთელი დადებითი N და M რიცხვი (1≤N,M≤150) დაფის ზომები (სტრიქონებისა და სვეტების რაოდენობა შესაბამისად). მომდევნო N რაოდენობის სტრიქონით, რომელთაგან თითოეულში M რაოდენობის სიმბოლოა, აღწერილია დაფა ზემოდან ქვემოთ, მარცხნიდან მარჯვნივ. სიმბოლო ‘.’ შეესაბამება ცარიელ უჯრას, ხოლო სიმბოლო ‘#’ კი - ბლოკირებულს. სტრიქონები გადანომრილია 1-დან N-მდე, ხოლო სვეტები - 1-დან M-მდე.

შემდეგი სტრიქონი შეიცავს მთელ Q რიცხვს (1≤Q≤100 000) – სათამაშო ბარათების რაოდენობას.

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

გარანტირებულია, რომ არცერთი სიმრავლე ცარიელი არ არის, ყველა სიმრავლის ყველა უჯრა თავისუფალია და არცერთი უჯრა არ ეკუთვნის ერთ ბარათზე მოცემული სიმრავლეებიდან ერთზე მეტს. გარანტირებულია, რომ ჯამური ზომა ყველა იმ სიმრავლეებისა, რომლებსაც შეიცავს ყველა სათამაშო ბარათი, არ აღემატება 300 000-ს. დამატებით გარანტირებულია, რომ უჯრათა ყველა სამეულების (კარგისაც და არაკარგისაც) ჯამური რაოდენობა ყველა ბარათზე ერთად: Qtotal 2·107.

შეტანის იმ სტრიქონებში, სადაც რიცხვებია ჩაწერილი, ისინი ერთმანეთისაგან თითო ჰარითაა გამოყოფილი.

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

შეფასება:

ტესტების 32%-ში  N100,  Qtotal ≤ 1 000;

ტესტების 28%-ში  N100,  Qtotal ≤ 1 000 000.




მაგალითები

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

შენიშვნა

მოტანილ მაგალითში სათამაშო კომპლექტი შეიცავს ორ ბარათს. პირველი ბარათის ყველა სამეულში ფირფიტა გადაადგილებას იწყებს 
ზედა მარცხენა უჯრაში და მოძრაობას ამთავრებს ქვედა მარჯვენა უჯრაში. რთული არ არის დავინახოთ, რომ ამის გაკეთება შესაძლებელია
მხოლოდ მაშინ, თუ B სიმრავლის სამი ელემენტიდან ბლოკირებას გავუკეთებთ მეორე სტრიქონის პირველ უჯრას, ანუ კარგი სამეული იქნება:
(1,1) – (2,1) – (5,6).
მეორე ბარათზე კარგი სამეულებია: (1,2) - (3,1) - (5,6),     (2,1) - (3,1) - (5,6),     (2,1) - (3,1) - (5,1).