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

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