PGU

در دانشگاه خلیج فارس مسابقه‌ای بین قوی‌ترین گروه به نام الف و ضعیف‌ترین گروه به نام ب برقرار می‌باشد. تیم داوران در ابتدای کار از لوح مسابقه که شامل چند معادله می‌باشد، تعدادی را انتخاب کرده و به تیم الف می‌دهد. علاوه بر آن‌ها دو عدد ‎$M$‎ و ‎$N$ ($1\leq N‎, ‎M$)‎ را نیز به آن‌ها می‌دهند.

تیم الف همه معادلات را به دلخواه خود به نامعادله تغییر می‌دهد. سپس داوران دو عدد تصادفی ‎$A$‎ و ‎$B$‎ در بازه‌ی ‎$[-2^{31}‎, ‎2^{31}-1]$‎ تولید می‌کنند. در صورتی که دو عدد ‎$A$‎ و ‎$B$‎ حتی در یک نامعادله‌ی محصول کار تیم الف صدق نکرد، بازی تمام می‌شود.

در صورتی که دو عدد ‎$A$‎ و ‎$B$‎ در نامعادلات صدق بکنند اگر ‎$A$‎ در بازه‌ی بسته‌ی ‎$[0‎, ‎M]$‎ و ‎$B$‎ در بازه‌ی بسته‌ی ‎$[0‎, ‎N]$‎ باشد، تیم الف برنده، و در غیر این‌صورت (‎$A$‎ یا ‎$B$‎ در بازه‌ی مورد نظر نباشند) تیم ب برنده خواهد شد.

به منظور سادگی فرض کنید معادلات به صورت خطی و در حالت کلی به شکل ‎$xA+yB=c$‎ باشند که ‎$x,y\in\{1,-1\}$‎ و ‎$c\in Z$‎. تیم الف می‌خواهد با داشتن معادلات انتخابی داوران و دو عدد ‎$M$‎ و ‎$N$‎ جهت نامعادلات را به صورتی تعیین کند که امکان برنده شدن تیم ب وجود نداشته باشد و همچنین احتمال برنده شدن خود (تیم الف) را بیشینه کند.

• هر ورودی شامل دو بخش می‌باشد.
• بخش نخست توصیف معادلات در لوح مسابقه می‌باشد.
  • این بخش با یک عدد ‎$L$‎ که تعداد معادلات در لوح را نشان می‌دهد شروع می‌شود.
  • در ‎$L$‎ سطر بعدی در سطر ‎$i$‎ام (با شروع از ‎۱‎) سه عدد ‎$x$‎، ‎$y$‎، و ‎$c$‎ آمده است که معادله‌ی ‎$i$‎ام را مشخص می‌کنند.
• در بخش دوم ‎$k$‎ مسابقه با استفاده از بخش نخست توصیف شده است.
  • سطر اول بخش دوم شامل عدد ‎$k$‎ می‌باشد.
  • سپس ‎$k$‎ مسابقه در ادامه توصیف شده‌اند.
  • مسابقه‌ی ‎$i$‎ام در دو سطر توصیف می‌شود.
    • سطر اول شامل سه عدد ‎$M$‎، ‎$N$‎، و ‎$T$‎ می‌باشد.
    • سطر دوم شامل ‎$2T$‎ عدد $p_j$ (‎ $p_j < p_j+1$‎ و ‎$1\leq j\leq 2T$‎ و ‎$1\leq p_j\leq L$‎) می‌باشد.
    • اعداد ‎$p_j$‎ معادلات مسابقه‌ی ‎$i$‎ام را نشان می‌دهد که شامل معادلاتی می‌باشد که اندیسشان در ‎$S=\cup_{1\leq l\leq T} [p_{2l-1}‎, ‎p_{2l}]$ ‎ ($[p_a,p_b]$ بازه‌ی بسته ‎$p_b$‎ و‎$p_a$‎ را نشان می‌دهد) باشد.
• ‎$2 \leq L \leq 100000$‎ و ‎$1 \leq k \le 10$‎

در خروجی به ازای هر مسابقه در یک سطر احتمال برنده شدن تیم الف (با توجه به شرایط مساله) ضربدر ‎$2^{65}$‎ کرده، سپس گرد کنید و بنویسید. (فرض کنید همیشه جوابی با احتمال بیش از صفر برای تیم الف وجود دارد.)

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

• سوال قبل