Problem
खजाना शिकारी वस्या एक प्राचीन कालकोठरी के नक्शे पर आया था। कालकोठरी एक NM आकार की भूलभुलैया (1NM100, NM100) है। भूलभुलैया की प्रत्येक कोशिका या तो खाली और पार करने योग्य होती है, या इसमें एक दीवार होती है। आप केवल एक सेल से दीवार से सटे सेल में जा सकते हैं (उदाहरण के लिए, प्रत्येक सेल में 4 से अधिक आसन्न सेल नहीं हो सकते हैं)।
कोशिकाओं में से एक में एक खजाना है जिसे वासिया प्राप्त करना चाहता है। भूलभुलैया में K प्रवेश द्वार हैं जहाँ से Vasya अपनी यात्रा शुरू कर सकता है।
यह निर्धारित करना आवश्यक है कि किस प्रवेश द्वार से वास्या को अपनी यात्रा शुरू करने की आवश्यकता है ताकि खजाने की यात्रा की दूरी कम से कम हो। यदि ऐसे कई इनपुट हैं, तो इनपुट को सबसे छोटी संख्या के साथ प्रिंट करें।
इनपुट
पहली पंक्ति में 2 संख्याएँ N और M हैं, जो भूलभुलैया के आयामों को परिभाषित करती हैं। भूलभुलैया का वर्णन इस प्रकार है: एन लाइनें प्रत्येक एम वर्णों के साथ। 0 का अर्थ है कि सेल मुक्त है; 1 कि पिंजरे में एक दीवार है। प्रतीक * एक खजाने के साथ एक सेल को दर्शाता है (भूलभुलैया में वास्तव में ऐसा ही एक सेल है)।
(N+2)वीं पंक्ति में संख्या K (1<=K<= NxM) होती है -- भूलभुलैया के प्रवेश द्वारों की संख्या। अगला, K लाइनों में इनपुट के निर्देशांक होते हैं। इस प्रकार, i-th लाइन में संख्या xi और yi होती है, जिसका अर्थ है कि i-th इनपुट xi-th लाइन और yi-th कॉलम (1xiN1yiM) में स्थित है। यह गारंटी है कि इनपुट के निर्देशांक जोड़े में भिन्न हैं, और यह कि सभी इनपुट खाली कक्षों में स्थित हैं। कोई भी प्रवेश द्वार खजाने के पिंजरे में नहीं है।
आउटपुट
एक संख्या प्रदर्शित करना आवश्यक है - वांछित इनपुट संख्या (संख्या 1 से शुरू होती है)। यदि खजाने तक नहीं पहुंचा जा सकता है, तो -1 प्रिंट करें।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
1 |
| 2 |
<टीडी>
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
-1 |