====== 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}$‎ کرده، سپس گرد کنید و بنویسید.
(فرض کنید همیشه جوابی با احتمال بیش از صفر برای تیم الف وجود دارد.)


===== محدودیت‌ها =====


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 \\ 1 1 5 \\ 1 1 15 \\ 1 -1 5 \\ 1 -1 -5 \\ 1 \\ 10 10 1 \\ 1 4 | 100‎ |

</WRAP>



  * [[سوال ۸|سوال قبل]]