المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۱۳:سوال ۷

زوج‌های جوان

تعدادی زوج جوان را در جدولی $m\times n$ در یک روز بهاری زندانی کرده‌ایم. همه‌ی افراد در این جدول در هر روز دقیقا یک حرکت می‌کنند. نه کم‌تر، نه بیش‌تر! یک حرکت بدین صورت تعیین می‌شود که یا یک خانه به سمت راست و یا یک خانه به سمت بالا می‌رویم. البته مجاز به خروج از جدول نیستیم. علاوه بر این تعدادی پل هوایی یک‌طرفه بین بعضی از خانه‌های جدول وجود دارد. یک حرکت می‌تواند از ابتدای پل هوایی به انتهای آن باشد. همیشه از خانه‌ی بالا و سمت راست جدول به خانه‌ی پایین و سمت چپ جدول پل هوایی وجود دارد.

برنامه‌ی شما باید تشخیص دهد که کدام زوج‌های جوان می‌توانند به فیض وصال برسند. در متون کهن آمده است که فیض وصال در شرایط ویژه‌ای حاصل می‌آید: وقتی یک زوج هم‌زمان به یک خانه‌ی جدول برسند.

ورودی

در سطر اول فایل ورودی به ترتیب $m$ و $n$ و $k$ تعداد ازواج می‌آید. ($1\leq m,n \leq 10^7$)

در $k$ سطر بعد، در هر سطر محل یک زوج در زمان شروع آمده است. محل یک زوج با چهار عدد $a$، $b$، $c$ و $d$ مشخص می‌شود. $a$ نمایان‌گر سطر و $b$ نمایان‌گر ستون زوجه و $c$ نمایش‌گر سطر و $d$ نمایش‌گر ستون زوج مربوطه می‌باشد.

زان پس $l$ تعدادپل‌های هوایی می‌آید. پس از آن نیز مختصات دو سر پل‌ها در $l$ سطر می‌آید. دو عدد اول سطر و ستون ابتدای پل و دو عدد بعدی سطر و ستون انتهای آن می‌باشد. ($0\leq l,k \leq 10^6$)

خروجی

در سطر $i$ ام بنویسید که زوج $i$ ام به فیض می‌رسد یا خیر.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3 4 2
1 1 1 4
2 3 3 2
2
3 4 1 1
3 3 2 2
Yes
Yes

ابزار صفحه