+ محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی) + محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی) ---------- در این مسئله، $N$ گربه (با شماره‌های $1$ تا $N$) و $M$ موش (با شماره‌های $1$ تا $M$) روی یک خط هستند. هر گربه و هر موش می‌خواهد از نقطه‌ای به سمت نقطه‌ای دیگر (شاید همان نقطه) روی این خط حرکت کند. طبیعتاً، گربه‌ها هم می‌خواهند موش‌ها را بخورند. هر گربه و هر موش با سرعت ثابت $1$ حرکت می‌کند. برای هر $i$ معتبر، $i$-امین گربه در ابتدا در نقطه‌ی $a_i$ خواب است. در زمان $s_i$، این گربه بیدار می‌شود و به سمت نقطه‌ی نهایی $b_i$ با سرعت ثابت و بدون هیچ پرشی حرکت می‌کند (بنابراین در زمان $e_i = s_i + |a_i-b_i|$ به این نقطه می‌رسد). پس از رسیدن به نقطه‌ی $b_i$، دوباره به خواب می‌رود. برای هر $i$ معتبر، $i$-امین موش در ابتدا در نقطه‌ی $c_i$ پنهان شده است. در زمان $r_i$، این موش از پنهانی در می‌آید و به سمت نقطه‌ی نهایی $d_i$ به همان صورتی که گربه‌ها حرکت می‌کنند - با سرعت ثابت و بدون هیچ پرشی - حرکت می‌کند و در زمان $q_i = r_i + |c_i-d_i|$ (اگر خورده نشود) به این نقطه می‌رسد. پس از رسیدن به نقطه‌ی $d_i$، دوباره پنهان می‌شود. اگر یک گربه و یک موش یکدیگر را ببینند (یعنی در یک نقطه و در یک زمان قرار بگیرند)، گربه موش را می‌خورد و موش ناپدید می‌شود و نمی‌تواند توسط گربه‌ای دیگر خورده شود. یک گربه‌ی خوابیده نمی‌تواند موشی را بخورد و یک موش پنهان نمی‌تواند خورده شود - به صورت دقیق‌تر، گربه‌ی $i$ تنها در صورتی می‌تواند موش $j$ را بخورد که در زمان $t$ با هم برخورد کنند به طوری که $s_i \le t \le e_i$ و $r_j \le t \le q_j$ برقرار باشد. وظیفه‌ی شما این است که پیدا کنید کدام موش‌ها توسط کدام گربه‌ها خورده می‌شوند. تضمین می‌شود که دو گربه به طور همزمان با یک موش برخورد نمی‌کنند. # ورودی + خط اول ورودی شامل یک عدد صحیح $T$ است که تعداد سناریوها را نشان می‌دهد. توضیحات مربوط به $T$ سناریو در ادامه آمده است. + خط اول هر سناریو شامل دو عدد صحیح $N$ و $M$ است که با یک فاصله از هم جدا شده‌اند (در ابتدا $N$ می‌آید و سپس $M$). + $N$ خط در ادامه آمده است. برای هر $i$ ($1 \le i \le N$)، خط $i$-ام از این خطوط شامل سه عدد صحیح $a_i$، $b_i$ و $s_i$ است که با یک فاصله از هم جدا شده‌اند. + $M$ خط دیگر در ادامه آمده است. برای هر $i$ ($1 \le i \le M$)، خط $i$-ام از این خطوط شامل سه عدد صحیح $c_i$، $d_i$ و $r_i$ است که با یک فاصله از هم جدا شده‌اند. # خروجی برای هر سناریو، $M$ خط چاپ کنید. برای هر $i$ معتبر، خط $i$-ام از این خطوط باید شامل یک عدد صحیح باشد: شماره گربه‌ای که موش $i$-ام را می‌خورد و یا $-1$ اگر هیچ گربه‌ای این موش را نخورده است. # محدودیت‌ها + $1 \le T \le 10$ + $0 \le N \le 1,000$ + $1 \le M \le 1,000$ + $1 \le a_i, b_i, s_i \le 10^9$ برای هر $i$ معتبر + $1 \le c_i, d_i, r_i \le 10^9$ برای هر $i$ معتبر + همه موقعیت‌های اولیه و نهایی همه‌ی گربه‌ها و موش‌ها متمایز هستند. البته درمورد هر موش خاص موقعیت شروع و پایان آن می‌تواند یکسان باشد. و درمورد هر گربه‌ی خاص موقعیت شروع و پایان آن می‌تواند یکسان باشد. # مثال ## ورودی نمونه ۱ ``` 1 8 8 2 8 2 12 18 2 22 28 4 32 38 4 48 42 2 58 52 3 68 62 1 78 72 3 3 6 3 13 19 3 21 25 3 31 39 3 46 43 4 59 53 2 65 61 4 79 71 2 ``` ## خروجی نمونه ۱ ``` 1 2 3 4 5 6 7 8 ```

حل سؤال در بانک سؤالات