قلمرو پادشاهی APIO مورد حمله‌ی نینجاها قرار گرفته است. نینجاها خیلی قوی هستند، چون وقتی می‌جنگند، در سایه‌ها پنهان می‌شوند و مردم دیگر نمی‌توانند آن‌ها را ببینند. کل قلمرو پادشاهی تسخیر شده است به‌جز قلعه‌ی APIO که پادشاه در آن زندگی می‌کند. در مقابل قلعه‌ی APIO، یک خط از $N$ بوته قرار دارد. بوته‌ها از $1$ تا $N$ شماره‌گذاری شده‌اند و $K$ نینجا در زیر دقیقاً $K$ بوته پنهان شده‌اند. در قلعه‌ی APIO، $M$ نگهبان هستند. نگهبان $i$اُم دنباله‌ای از بوته‌ها را از بوته‌ی شماره‌ی $A_i$ تا بوته‌ی شماره‌ی $B_i$ زیر نظر دارد. حال، هر نگهبان به پادشاه گزارش می‌دهد که آیا در زیر بوته‌هایی که او زیر نظر دارد نینجایی وجود دارد یا نه. چون شما یکی از خادمان پادشاه هستید، باید بر اساس گزارش‌های نگهبانان به او بگویید که در زیر کدام بوته «یقیناً یک نینجا پنهان است». در این‌جا، وقتی می‌گوییم در زیر یک بوته «یقیناً یک نینجا پنهان است» که در هر وضعیت ممکن قرارگرفتن نینجاها که با گزارش‌های نگهبانان تناقضی ندارد، یک نینجا در زیر آن بوته پنهان باشد.

برنامه‌ای بنویسید که اطلاعات نگهبانان و گزارش‌هایشان را از ورودی بگیرد، و همه‌ی بوته‌هایی را مشخص کند که در زیرشان «یقیناً یک نینجا پنهان است».

• خط اول ورودی شامل سه عدد صحیح $N$، $K$ و $M$ با فاصله از هم می‌باشد که $N$ تعداد بوته‌ها، $K$ تعداد نینجاهای پنهان، و $M$ تعداد نگهبانان است.
• $M$ خط بعد، اطلاعات نگهبانان و گزارش‌هایشان را بیان می‌کند. خط $i$اُم از این خط‌ها، شامل سه عدد صحیح $A_i$، $B_i$، و $C_i$ با فاصله از هم می‌باشد ($A_i \leq B_i$) که مشخص می‌کند که نگهبان شماره‌ی $i$، از بوته‌ی شماره‌ی $A_i$ تا بوته‌ی شماره‌ی $B_i$ را زیر نظر دارد. عدد صحیح $C_i$ یکی از دو مقدار $0$ یا $1$ را دارد. اگر $C_i=0$، هیچ نینجایی در زیر بوته‌های شماره‌ی $A_i$ تا شماره‌ی $B_i$ وجود ندارد. اگر $C_i=1$، حداقل یک نینجا در زیر بوته‌های شماره‌ی $A_i$ تا شماره‌ی $B_i$ وجود دارد.
• برای هر ورودی، تضمین شده است که حداقل یک وضعیت قرارگرفتن نینجاها وجود دارد که با گزارش‌های نگهبانان تناقضی ندارد.
• تعداد بوته‌ها $1 \leq N \leq 10^5$
• تعداد نینجاهای پنهان $1 \leq K \leq N$
• تعداد نگهبانان $1 \leq M \leq 10^5$
• در $10$ درصد از تست‌ها $N\leq 20$ و $M \leq 100$.
• در $50$ درصد از تست‌ها $N\leq 1000$ و $M \leq 1000$.

اگر بوته‌ای وجود دارد که در زیر آن «یقیناً یک نینجا پنهان است»، شماره‌ی بوته‌هایی که در زیرشان «یقیناً یک نینجا پنهان است» را در خروجی بنویسید. شماره‌ی بوته‌ها باید به ترتیب صعودی نوشته شوند، و هر خط خروجی باید فقط شامل یک شماره باشد. پس، اگر $X$ بوته وجود دارند که در زیرشان «یقیناً یک نینجا پنهان است»، خروجی از $X$ سطر تشکیل می‌شود. اگر هیچ بوته‌ای وجود ندارد که در زیرش «یقیناً یک نینجا پنهان است»، رشته‌ی «$-1$» را در خروجی بنویسید.

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

در نمونه‌ی اول، دو وضعیت ممکن قرارگرفتن نینجاها وجود دارد که شرایط داده‌شده را رعایت می‌کنند؛ ۳ نینجا که در زیر بوته‌های ۱، ۳، و ۵ پنهان‌اند، و ۳ نینجا که در زیر بوته‌های ۲، ۳، و ۵ پنهان‌اند. چون در هر وضعیت قرارگرفتن ممکن، یک نینجا در زیر بوته‌های ۳ و ۵ پنهان است، باید اعداد ۳ و ۵ را خروجی دهیم. ولی در مورد بوته‌ی شماره‌ی ۱، گرچه یک وضعیت ممکن قرارگرفتن نینجاها وجود دارد که یک نینجا در زیر بوته‌ی ۱ پنهان باشد، ولی یک وضعیت ممکن قرارگرفتن نینجاها هم وجود دارد که در زیر بوته‌ی ۱ نینجایی پنهان نیست. پس، عدد ۱ را نباید خروجی دهیم. به‌دلیل مشابه، عدد ۲ را هم نباید خروجی دهیم.

در نمونه‌ی دوم، هیچ بوته‌ای وجود ندارد که در زیرش «یقیناً یک نینجا پنهان است». پس باید «$-1$» را خروجی دهیم.  

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