====== Soldiers ======

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

گروهبان این سربازان، برای بررسی میزان هوشیاری آن‌ها، از برخی آنان خواسته تا روی یک برگه ابتدا شماره خودشان و سپس تعداد کلاه‌هایی که می‌بیند (شامل کلاه خودش در صورت وجود) را بنویسد. می‌دانیم در بین پرسش شوندگان دقیقا یک نفر (نه کم‌تر و نه بیش‌تر) دروغ گفته است؛ یعنی تعداد کلاه‌هایی که روی کاغذ برای ما نوشته متفاوت با تعداد کلاه‌هایی بوده است که او می دیده. و البته با شناخت قبلی گروهبان تنها به برخی از پرسش شدگان (و نه همه‌ی آن‌ها) مظنون است و مطمئن است سرباز دروغگو بین یکی از این مظنونین است. 

اکنون گروهبان از شما می‌خواهد تا با دریافت کاغذ و لیست مظنونین، مشخص کنید که آیا سرباز دروغگو به صورت یکتا قابل تشخیص است یا خیر؛ و اگر هست کدام سرباز است.
===== ورودی =====
  * هر ورودی شما چند سناریو است. در سطر اول ورودی تعداد این سناریوها ($t$) آمده است و در ادامه این سناریوها پشت‌سرهم می‌آیند.
  * برای هر سناریو ابتدا مقدار $n$ (تعداد سربازان) و سپس $k$ (تعداد پرسش شدگان) در یک سطر درج می‌گردد.
  * سپس در $k$ سطر بعدی، در سطر اطلاعات مربوط به یک پرسش‌شونده به صورت $n_i~a_i~s_i$ می‌آید که $n_i$ (اولین عدد سطر) شماره سرباز است. $a_i$ پاسخ سرباز به ماست (تعداد کلاه‌هایی که ادعا می‌کند دیده). و نهایتا $s_i$ برابر $1$ است اگر این سرباز مظنون به درغگو بودن است و $0$ است اگر مظمئن هستیم سرباز راستگو است. 
  * $1\leq k \leq n \leq 3000$
  * شماره سربازان بین $1$ تا $n$ است و جواب هر سرباز نیز بین $0$ تا $n$ است.
  * می‌دانیم در بین پرسش شدگان حداقل یک مظنون وجود دارد.
  * تمام ورودی‌ها بر اساس یک حالت واقعی قرار دادن کلاه و دروغ  گفتن دقیقا یک نفر، شکل گرفته‌اند.

===== خروجی =====

  * خروجی شما $t$ سطر است؛ هر سطر جواب بک سناریو (به ترتیب).
  * برای هر سناریو در صورتی که سرباز دروغگو را نمی‌توان الزاما به صورت یکتا از بین مظنونین پیدا کرد تنها مقدار $0$ را بنویسید. در غیر این‌صورت فقظ شماره سرباز درغگو را بنویسید.

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


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

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

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3‎ \\ 6 3 \\ 1 2 1 \\ 2 2 1 \\ 3 2 1 \\ 2 2 \\ 1 0 1 \\ 2 2 1 \\ 5 3 \\ 2 2 1 \\ 5 5 0 \\ 4 3 1 | 1 \\ 0 \\ 4  |

</WRAP>



  * [[سوال ۱۱|سوال بعد]]
  * [[سوال ۹|سوال قبل]]