- محدودیت زمان: ۱۰ ثانیه (برای تمامی زبانهای برنامهنویسی)
- محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبانهای برنامهنویسی)
در این مسئله، \(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