$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$ را بنویسید. در غیر این‌صورت فقظ شماره سرباز درغگو را بنویسید.

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

• سوال بعد
• سوال قبل