روز
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
روز
ساعت
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ساعت
دقیقه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
دقیقه
ثانیه
۹۰۱۲۳۴۵۶۷۸۹۰۹۰۱۲۳۴۵۶۷۸۹۰
ثانیه
  • محدودیت زمان: ۷ ثانیه
  • محدودیت حافظه: ۵۱۲ مگابایت

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

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

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

ورودی

در خط اول ورودی به شما سه عدد nn و mm و qq داده می‌شود.

در iiامین خط از nn خط بعدی، یک رشته به طول mm متشکل از . و‍ * آمده است که jjامین عنصر آن، نشان‌دهنده مسدود بودن یا نبودن خانه واقع در تقاطع سطر iiام و ستون jjام می‌باشد. اگر این عنصر * باشد، نشان‌دهنده مسدود بودن خانه مورد‌نظر و در غیر این صورت نشان‌دهنده خالی بودن آن می‌شود.

در iiامین خط از qq خط بعدی، چهار عدد xx و yy و x2x_2 و y2y_2 آمده‌ است که به ترتیب نشان‌دهنده شماره سطر خانه اول، شماره ستون خانه اول، شماره سطر خانه دوم و شماره ستون خانه دوم می‌باشد. تضمین می‌شود هیچ یک از دو خانه داده شده، مسدود نمی‌باشد. 1n,m2 0001 \le n, m \le 2\ 000 1q1 000 0001 \le q \le 1\ 000\ 000 1x,x2n1 \le x, x_2 \le n 1y,y2m1 \le y, y_2 \le m

خروجی

در خط iiام خروجی، پاسخ پرسش iiام را چاپ کنید.

مثال

ورودی نمونه ۱

4 4 3
....
....
....
....
2 3 3 2
1 1 1 2
4 1 4 2
Plain text

خروجی نمونه ۱

2
1
3
Plain text

ورودی نمونه ۲

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

خروجی نمونه ۲

1
2
0
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.