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

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

• سطر اول ورودی شامل دو عدد طبیعی $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)$ مختصات جواهر را نشان می‌دهد.
• تضمین می‌شود که هیج دو لیزری در یک راستای افقی و یا عمودی نیستند.
• تضمین می‌شود که به ازای تمامی پرسش‌ها، مکان اولیه‌ی دزد و مکان جواهر، با هیچ‌کدام از لیزر‌ها در یک راستای افقی یا عمودی نیستند.
• $1 \leq n, q \leq 2 * 10^5$
• تمام اعداد ورودی در بازه $[-10^9, 10^9]$ قرار دارند.

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

• زیرمسئله اول (۱۵ نمره): $n \leq 50$
• زیرمسئله دوم (۳۵ نمره): $n \leq 1000$
• زیرمسئله سوم (۵۰ نمره): بدون محدودیت اضافی

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

• سوال بعد