and Bengali as well.
There are N$N$ cats (numbered 1$1$ through N$N$) and M$M$ rats (numbered 1$1$ through M$M$) on a line. Each cat and each rat wants to move from some point to some (possibly the same) point on this line. Naturally, the cats also want to eat the rats when they get a chance. Both the cats and the rats can only move with constant speed 1$1$.
For each valid i$i$, the i$i$-th cat is initially sleeping at a point a_i$a_i$. At a time s_i$s_i$, this cat wakes up and starts moving to a final point b_i$b_i$ with constant velocity and without any detours (so it arrives at this point at the time e_i = s_i + |a_i-b_i|$e_i = s_i + |a_i-b_i|$). After it arrives at the point b_i$b_i$, it falls asleep again.
For each valid i$i$, the i$i$-th rat is initially hiding at a point c_i$c_i$. At a time r_i$r_i$, this rat stops hiding and starts moving to a final point d_i$d_i$ in the same way as the cats ― with constant velocity and without any detours, arriving at the time q_i = r_i + |c_i-d_i|$q_i = r_i + |c_i-d_i|$ (if it does not get eaten). After it arrives at the point d_i$d_i$, it hides again.
If a cat and a rat meet each other (they are located at the same point at the same time), the cat eats the rat, the rat disappears and cannot be eaten by any other cat. A sleeping cat cannot eat a rat and a hidden rat cannot be eaten ― formally, cat i$i$ can eat rat j$j$ only if they meet at a time t$t$ satisfying s_i \le t \le e_i$s_i \le t \le e_i$ and r_j \le t \le q_j$r_j \le t \le q_j$.
Your task is to find out which rats get eaten by which cats. It is guaranteed that no two cats will meet a rat at the same time.

-----Input-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
- The first line of each test case contains two space-separated integers N$N$ and M$M$.
- N$N$ lines follow. For each i$i$ (1 \le i \le N$1 \le i \le N$), the i$i$-th of these lines contains three space-separated integers a_i$a_i$, b_i$b_i$ and s_i$s_i$.
- M$M$ more lines follow. For each i$i$ (1 \le i \le M$1 \le i \le M$), the i$i$-th of these lines contains three space-separated integers c_i$c_i$, d_i$d_i$ and r_i$r_i$.

-----Output-----
For each test case, print M$M$ lines. For each valid i$i$, the i$i$-th of these lines should contain a single integer ― the number of the cat that will eat the i$i$-th rat, or -1$-1$ if no cat will eat this rat.

-----Constraints-----
- 1 \le T \le 10$1 \le T \le 10$
- 0 \le N \le 1,000$0 \le N \le 1,000$
- 1 \le M \le 1,000$1 \le M \le 1,000$
- 1 \le a_i, b_i, s_i \le 10^9$1 \le a_i, b_i, s_i \le 10^9$ for each valid i$i$
- 1 \le c_i, d_i, r_i \le 10^9$1 \le c_i, d_i, r_i \le 10^9$ for each valid i$i$
- all initial and final positions of all cats and rats are pairwise distinct

-----Example Input-----
2
8 7
2 5 1
1 4 1
9 14 10
20 7 9
102 99 1
199 202 1
302 299 3
399 402 3
6 3 1
10 15 10
100 101 1
201 200 1
300 301 5
401 400 5
1000 1010 1020
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

-----Example Output-----
1
4
5
6
7
8
-1
1
2
3
4
5
6
7
8

Source: codechef | Difficulty: VERY_HARD
Tags: Implementation

Constructive algorithms


Solutions:
def sort(array):
	new_array = []
	for (i, num) in enumerate(array):
		start = 0
		last = i
		while start != last:
			mid = (start + last) // 2
			if new_array[mid][0] > num[0]:
				end = mid
			else:
				start = mid + 1
		new_array.insert(start, num)
	return new_array
tests = int(input())
for _ in range(tests):
	(n, m) = [int(j) for j in input().split()]
	(cats, rats) = [[[0] * 3 for _ in range(n)], [[0] * 3 for _ in range(m)]]
	for i in range(n):
		cats[i] = [int(j) * 2 for j in input().split()]
	for i in range(m):
		rats[i] = [int(j) * 2 for j in input().split()]
	(right_cats, left_cats, right_rats, left_rats) = [[], [], [], []]
	for i in range(n):
		(start, end, time) = cats[i]
		if end > start:
			right_cats.append([start - time, time, end - start + time, i])
		else:
			left_cats.append([start + time, time, start - end + time, i])
	for i in range(m):
		(start, end, time) = rats[i]
		if end > start:
			right_rats.append([start - time, time, end - start + time, i])
		else:
			left_rats.append([start + time, time, start - end + time, i])
	cat_number = [[-1, -1] for _ in range(m)]
	for rat in left_rats:
		(point, start, end, index) = rat
		for cat in left_cats:
			if point == cat[0]:
				time_of_collision = max(cat[1], start)
				if time_of_collision <= end and time_of_collision <= cat[2]:
					if cat_number[index][0] == -1 or time_of_collision < cat_number[index][1]:
						cat_number[index][0] = cat[3] + 1
						cat_number[index][1] = time_of_collision
		for cat in right_cats:
			time_of_collision = (point - cat[0]) // 2
			if time_of_collision >= start and time_of_collision <= end and (time_of_collision >= cat[1]) and (time_of_collision <= cat[2]):
				if cat_number[index][0] == -1 or time_of_collision < cat_number[index][1]:
					cat_number[index][0] = cat[3] + 1
					cat_number[index][1] = time_of_collision
	for rat in right_rats:
		(point, start, end, index) = rat
		for cat in right_cats:
			if point == cat[0]:
				time_of_collision = max(cat[1], start)
				if time_of_collision <= end and time_of_collision <= cat[2]:
					if cat_number[index][0] == -1 or time_of_collision < cat_number[index][1]:
						cat_number[index][0] = cat[3] + 1
						cat_number[index][1] = time_of_collision
		for cat in left_cats[::-1]:
			time_of_collision = (cat[0] - point) // 2
			if time_of_collision >= start and time_of_collision <= end and (time_of_collision >= cat[1]) and (time_of_collision <= cat[2]):
				if cat_number[index][0] == -1 or time_of_collision < cat_number[index][1]:
					cat_number[index][0] = cat[3] + 1
					cat_number[index][1] = time_of_collision
	for i in range(m):
		print(cat_number[i][0])


class A:

	def __init__(self):
		(a, b, si) = map(int, input().split())
		self.ei = si + abs(a - b)
		self.v = 1 if b >= a else -1
		self.eaten = (-1, 10 ** 10)
		self.a = a
		self.b = b
		self.si = si

	def collide(self, z):
		if self.si > z.ei or self.ei < z.si:
			return False
		if self.v == z.v:
			if self.si > z.si:
				(self, z) = (z, self)
			if z.a == self.a + self.v * (z.si - self.si):
				return z.si
			else:
				return False
		if self.v == -1:
			(self, z) = (z, self)
		t = (z.a - self.a + z.si + self.si) / 2
		return t if self.si <= t <= self.ei and z.si <= t <= z.ei else False

def main():
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		cats = [A() for i in range(n)]
		for i in range(m):
			rat = A()
			for j in range(n):
				time = rat.collide(cats[j])
				if time:
					if time < rat.eaten[1]:
						rat.eaten = (j + 1, time)
			print(rat.eaten[0])
main()


class CatsRats:

	def __init__(self):
		(self.ai, self.bi, self.t_start) = map(int, input().split())
		self.t_end = self.t_start + abs(self.ai - self.bi)
		self.direction = get_direction(self.ai, self.bi)
		self.eaten_time = 10 ** 10
		self.eaten_by_cat = -1

	def will_collide(self, o2):
		if o2.t_start > self.t_end or o2.t_end < self.t_start:
			return False
		if self.direction == o2.direction:
			if self.t_start > o2.t_start:
				(self, o2) = (o2, self)
			if self.t_start + self.direction * (o2.ai - self.ai) == o2.t_start:
				return o2.t_start
		else:
			if self.direction == -1:
				(self, o2) = (o2, self)
			t_meet = (o2.ai - self.ai + o2.t_start + self.t_start) / 2
			if self.t_start <= t_meet <= self.t_end and o2.t_start <= t_meet <= o2.t_end:
				return t_meet
		return False

def get_direction(x, y):
	if x > y:
		return -1
	return 1
T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	cats = [CatsRats() for i in range(N)]
	for j in range(M):
		rat = CatsRats()
		for i in range(N):
			cat = cats[i]
			eaten_time = rat.will_collide(cat)
			if eaten_time:
				if eaten_time < rat.eaten_time:
					rat.eaten_time = eaten_time
					rat.eaten_by_cat = i + 1
		print(rat.eaten_by_cat)


class Animal:

	def __init__(self):
		(start, end, starting_time) = map(int, input().split())
		self.ending_time = starting_time + abs(start - end)
		self.velocity = 1 if end >= start else -1
		self.eaten_by = (-1, 10 ** 10)
		self.start = start
		self.end = end
		self.starting_time = starting_time

	def will_collide(self, z):
		if self.starting_time > z.ending_time or self.ending_time < z.starting_time:
			return False
		if self.velocity == z.velocity:
			if self.starting_time > z.starting_time:
				(self, z) = (z, self)
			if z.start == self.start + self.velocity * (z.starting_time - self.starting_time):
				return z.starting_time
			else:
				return False
		if self.velocity == -1:
			(self, z) = (z, self)
		t = (z.start - self.start + z.starting_time + self.starting_time) / 2
		return t if self.starting_time <= t <= self.ending_time and z.starting_time <= t <= z.ending_time else False

def main():
	for _ in range(int(input())):
		(no_cats, no_rats) = map(int, input().split())
		Cats = [Animal() for i in range(no_cats)]
		for i in range(no_rats):
			rat = Animal()
			for j in range(no_cats):
				time = rat.will_collide(Cats[j])
				if time:
					if time < rat.eaten_by[1]:
						rat.eaten_by = (j + 1, time)
			print(rat.eaten_by[0])
main()