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

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

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

ورودی

سطر اول ورودی شامل دو عدد طبیعی $n$، تعداد لیزر‌های موزه، و $q$، تعداد پرسش‌های آقای مهندس، است.

در هر کدام از $n$ سطر بعدی به ترتیب

$t\in {$-$,$|}

و دو عدد طبیعی $x$ و $y$ آمده است که به معنای وجود یک لیزر در مختصات $(x,y)$ است. متغیر $t$ نشان‌دهنده‌ی وضعیت لیزر در حالت ابتدایی (دقیقه‌ی صفر) است. در صورتی که - باشد، لیزر در ابتدای کار افقی (راستای محور xها) و در صورتی که | باشد، عمودی (راستای محور yها) است.

در هر کدام از $q$‌ سطر بعدی به ترتیب چهار عدد طبیعی $x_s$ و $y_s$ و $x_g$ و $y_g$

آمده است که $(x_s,y_s)$ مختصات ابتدایی دزد و $(x_g,y_g)$ مختصات جواهر را نشان می‌دهد.

تضمین می‌شود که هیچ دو لیزری در یک راستای افقی و یا عمودی نیستند.

تضمین می‌شود که به ازای تمامی پرسش‌ها، مکان اولیه‌ی دزد و مکان جواهر، با هیچ‌کدام از لیزر‌ها در یک راستای افقی یا عمودی نیستند. تضمین می‌شود تمامی اعداد ورودی در بازه‌ی $[-10^9,10^9]$ قرار دارند.

$$1\le n,q\le 100\ 000$$

خروجی

خروجی شامل $q$ سطر است که سطر $i$-ام پاسخ به پرسش $i$-ام آقای مهندس است.

زیرمسئله‌ها

مثال

ورودی نمونه ۱

3 3 
- 3 1 
| 1 3 
- 5 5 
2 2 4 4 
2 2 0 0 
2 2 6 6 

خروجی نمونه ۱

0
1 
1

ورودی نمونه ۲

4 3
- 1 1 
- 3 3 
- 5 5 
- 7 7 
-1 -1 2 2 
2 4 4 2 
2 4 4 4 

خروجی نمونه ۲

1
1
0

۲۴امین دوره‌ المپیاد کامپیوتر - آزمون پنجم - ۱۳۹۳/۰۶/۱۵