• محدودیت زمان: ۱۰ ثانیه (برای تمامی زبان‌های برنامه‌نویسی)
• محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبان‌های برنامه‌نویسی)

در این مسئله، $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