• محدودیت زمان: ۷ ثانیه
• محدودیت حافظه: ۵۱۲ مگابایت

---

جدولی \(n \times m\) داریم که برخی از خانه‌های آن مسدود شده‌اند. می‌دانیم که سطرهای این جدول از بالا به پایین با ۱ تا \(n\) و ستون‌های این جدول از چپ به راست با ۱ تا \(m\) شماره‌گذاری شده‌اند.

حال فرض کنید مربعی بر روی این جدول داریم و می‌خواهیم آن را به مکان دیگری از جدول انتقال دهیم. برای این کار در هر حرکت می‌توانیم مربع را یک واحد به سمت چپ یا راست یا بالا یا پایین انتقال دهیم، به‌طوری که از جدول خارج نشود و هیچ خانه مسدودی وارد آن نشود. مربع \(A\) را از مربع \(B\) دسترس‌پذیر می‌گوییم اگر بتوانیم با تعدادی حرکت بر روی \(A\)، آن را به \(B\) برسانیم.

حال در ورودی \(q\) پرسش آمده است. در هر پرسش دو خانه متفاوت از جدول برای شما مشخص شده‌اند و شما باید بزرگترین \(k\) را خروجی دهید که مربع \(k \times k\) با گوشه پایین چپ خانه اول، از مربع \(k \times k\) با گوشه پایین چپ خانه دوم، دسترس‌پذیر باشد و همچنین هیچ‌کدام از دو مربع مورد‌نظر دارای خانه مسدود نباشند. دقت کنید که \(k\) ممکن است صفر نیز باشد.

ورودی

در خط اول ورودی به شما سه عدد \(n\) و \(m\) و \(q\) داده می‌شود.

در \(i\)امین خط از \(n\) خط بعدی، یک رشته به طول \(m\) متشکل از . و‍ * آمده است که \(j\)امین عنصر آن، نشان‌دهنده مسدود بودن یا نبودن خانه واقع در تقاطع سطر \(i\)ام و ستون \(j\)ام می‌باشد. اگر این عنصر * باشد، نشان‌دهنده مسدود بودن خانه مورد‌نظر و در غیر این صورت نشان‌دهنده خالی بودن آن می‌شود.

در \(i\)امین خط از \(q\) خط بعدی، چهار عدد \(x\) و \(y\) و \(x_2\) و \(y_2\) آمده‌ است که به ترتیب نشان‌دهنده شماره سطر خانه اول، شماره ستون خانه اول، شماره سطر خانه دوم و شماره ستون خانه دوم می‌باشد. تضمین می‌شود هیچ یک از دو خانه داده شده، مسدود نمی‌باشد. \[1 \le n, m \le 2\ 000\] \[1 \le q \le 1\ 000\ 000\] \[1 \le x, x_2 \le n\] \[1 \le y, y_2 \le m\]

خروجی

در خط \(i\)ام خروجی، پاسخ پرسش \(i\)ام را چاپ کنید.

مثال

ورودی نمونه ۱

4 4 3
....
....
....
....
2 3 3 2
1 1 1 2
4 1 4 2

خروجی نمونه ۱

2
1
3

ورودی نمونه ۲

6 7 3
.......
..****.
*......
***...*
.*.....
*.*.*.*
3 2 4 5
5 4 4 5
6 2 1 1

خروجی نمونه ۲

1
2
0