Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

These days, Chef has been playing a game.

The game is played on a grid with $N$ rows (numbered $1$ through $N$) and $N$ columns (numbered $1$ through $N$); let's denote the cell in row $r$ and column $c$ by $(r, c)$. $2M$ cells $(X_{1}, Y_{1}), (X_{2}, Y_{2}), \ldots, (X_{2M}, Y_{2M})$ in the grid are marked.

Chef wants to add exactly $M$ paths between pairs of distinct marked cells in such a way that no two paths intersect. A path from cell $(X_{i}, Y_{i})$ to cell $(X_{j}, Y_{j})$ is a sequence of distinct cells $(U_{1}, V_{1}), (U_{2}, V_{2}), \ldots, (U_{L}, V_{L})$ such that $(X_{i}, Y_{i})$ is the first cell and $(X_{j}, Y_{j})$ the last cell in this sequence and for each valid $i$, cells $(U_{i}, V_{i})$ and $(U_{i+1}, V_{i+1})$ share a side. Two paths intersect if there is some cell which is in both paths.

However, this seems too easy to Chef, so he added weights to all cells. Let's denote the weight of cell $(r, c)$ by $V_{r, c}$. You should find $M$ paths as described above such that the sum of weights of all cells in all paths is as large as possible.

------  Input ------
The first line of the input contains two space-separated integers $N$ and $M$.
$2M$ lines follow. For each $i$ ($1 ≤ i ≤ 2M$), the $i$-th of these lines contains two space-separated integers $X_{i}$ and $Y_{i}$.
$N$ more lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains $N$ space-separated integers $V_{i, 1}, V_{i, 2}, \ldots, V_{i, N}$.

------  Output ------
Print $M$ lines. Each of these lines should contain an integer $L$, followed by a space and $2L$ space-separated integers $U_{1}, V_{1}, U_{2}, V_{2}, \ldots, U_{L}, V_{L}$ describing one of your chosen paths. The paths may not intersect and each path must begin and end at distinct marked cells.

------  Constraints ------
$500 ≤ N ≤ 1,000$
$500 ≤ M ≤ 1,000$
$1 ≤ X_{i}, Y_{i} ≤ N$ for each valid $i$
$|V_{i, j}| ≤ 10^{9}$ for each valid $i, j$
$(X_{1}, Y_{1}), (X_{2}, Y_{2}), \ldots, (X_{2M}, Y_{2M})$ are pairwise distinct

------  Example Input ------

4 2
1 1
2 2
3 3
4 4
1 -1 -1 -1
1 1 1 1
1 1 1 1
-1 -1 -1 1

------  Example Output ------

5 1 1 2 1 3 1 3 2 3 3
5 4 4 3 4 2 4 2 3 2 2

------  Scoring ------
The score for each test case (and therefore each test file) is $(S / (10^{9} \cdot N^{2}) + 1)^6$, where $S$ is the sum of weights of cells in all paths in your solution. The score of a submission is the sum of its scores for all test files. For the example output, the score would be $(10 / (16 \cdot 10^{9}) + 1)^6 \doteq 1$.

If your output is invalid, the verdict of your submission will be Wrong Answer.

Test Generation Process
There are twenty test cases. During the contest, the displayed score will account for exactly four test files, i.e. your score reflects your submission's performance on 20% (4/20) of the test files. However, if your program gets a non-AC verdict on any test file, your submission's verdict will be non-AC. In other words, an AC verdict denotes that your program runs successfully on all the test files. After the end of the contest, your score will be changed to include the sum of your program's scores over the other sixteen test files.

The pseudocode used for generating all tests is given below. Assume that the function rand(l, r) generates a uniformly random integer between $l$ and $r$ (both inclusive).

N := rand(500, 1000)
M := rand(500, 1000)
for i in 1..2M:
	X[i] := rand(1, N)
	Y[i] := rand(1, N)
	while (X[j], Y[j]) == (X[i], Y[i]) for some j smaller than i:
		X[i] := rand(1, N)
		Y[i] := rand(1, N)
for x in 1..N:
	for y in 1..N:
		V[x][y] := rand(-1000000000, 1000000000)

Difficulty: VERY_HARD

Starter code:

Solutions:
import copy
import heapq
from collections import defaultdict
(n, m) = map(int, input().split())
maze = [['_' for i in range(n)] for i in range(n)]
pairs = []
for _ in range(2 * m):
	(x, y) = map(int, input().split())
	maze[x - 1][y - 1] = '*'
	pairs.append([x - 1, y - 1])
value = [[0 for _ in range(n)] for _ in range(n)]
normalized_value = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	temp = list(map(int, input().split()))
	for j in range(n):
		value[i][j] = temp[j]
		normalized_value[i][j] = 1000000000 if value[i][j] < 0 else 1
inf = float('inf')
normalized_value_inf = copy.deepcopy(normalized_value)
for i in pairs:
	normalized_value_inf[i[0]][i[1]] = inf

def shortest(maze, start, end):
	(sr, sc) = start
	(er, ec) = end
	if sr <= er:
		relative_row = sr
	else:
		relative_row = er
	if sc <= ec:
		relative_column = sc
	else:
		relative_column = ec
	column = abs(sc - ec) + 1
	row = abs(sr - er) + 1
	dis = [[float('inf') for _ in range(column)] for _ in range(row)]
	parent = defaultdict(list)
	dis[sr - relative_row][sc - relative_column] = maze[sr][sc]
	dx = [-1, 0, 1, 0]
	dy = [0, 1, 0, -1]
	st = []
	heapq.heappush(st, [0, sr - relative_row, sc - relative_column])
	while st:
		k = heapq.heappop(st)
		for i in range(4):
			if i == 0:
				x = k[1] - 1
				y = k[2]
			elif i == 1:
				x = k[1]
				y = k[2] + 1
			elif i == 2:
				x = k[1] + 1
				y = k[2]
			else:
				x = k[1]
				y = k[2] - 1
			if x >= 0 and x <= row - 1 and (y >= 0) and (y <= column - 1):
				if dis[x][y] > dis[k[1]][k[2]] + maze[x + relative_row][y + relative_column]:
					dis[x][y] = dis[k[1]][k[2]] + maze[x + relative_row][y + relative_column]
					heapq.heappush(st, [dis[x][y], x, y])
					parent[x, y] = [k[1], k[2]]
	if dis[er - relative_row][ec - relative_column] == float('inf'):
		return False
	else:
		paths = [[er, ec]]
		a = [er - relative_row, ec - relative_column]
		while True:
			if a == [sr - relative_row, sc - relative_column]:
				break
			a = parent[tuple(a)]
			paths.append([a[0] + relative_row, a[1] + relative_column])
		return paths[::-1]

def shortest_relative(maze, start, end, extra):
	(sr, sc) = start
	(er, ec) = end
	if sr <= er:
		relative_row = sr - extra
		if relative_row <= 0:
			relative_row = 0
	else:
		relative_row = er - extra
		if relative_row <= 0:
			relative_row = 0
	if sc <= ec:
		relative_column = sc - extra
		if relative_column <= 0:
			relative_column = 0
	else:
		relative_column = ec - extra
		if relative_column <= 0:
			relative_column = 0
	column = abs(sc - ec) + 1 + 2 * extra
	if sc < ec:
		if sc - extra < 0:
			column -= extra - (sc - 0)
		if ec + extra > n - 1:
			column -= extra - (n - ec - 1)
	else:
		if ec - extra < 0:
			column -= extra - (ec - 0)
		if sc + extra > n - 1:
			column -= extra - (n - sc - 1)
	row = abs(sr - er) + 1 + 2 * extra
	if sr < er:
		if sr - extra < 0:
			row -= extra - (sr - 0)
		if er + extra > n - 1:
			row -= extra - (n - er - 1)
	else:
		if er - extra < 0:
			row -= extra - (er - 0)
		if sr + extra > n - 1:
			row -= extra - (n - sr - 1)
	dis = [[float('inf') for _ in range(column)] for _ in range(row)]
	parent = defaultdict(list)
	dis[sr - relative_row][sc - relative_column] = maze[sr][sc]
	st = []
	heapq.heappush(st, [0, sr - relative_row, sc - relative_column])
	while st:
		k = heapq.heappop(st)
		for i in range(4):
			if i == 0:
				x = k[1] - 1
				y = k[2]
			elif i == 1:
				x = k[1]
				y = k[2] + 1
			elif i == 2:
				x = k[1] + 1
				y = k[2]
			else:
				x = k[1]
				y = k[2] - 1
			if x >= 0 and x <= row - 1 and (y >= 0) and (y <= column - 1):
				if dis[x][y] > dis[k[1]][k[2]] + maze[x + relative_row][y + relative_column]:
					dis[x][y] = dis[k[1]][k[2]] + maze[x + relative_row][y + relative_column]
					heapq.heappush(st, [dis[x][y], x, y])
					parent[x, y] = [k[1], k[2]]
	if dis[er - relative_row][ec - relative_column] == float('inf'):
		return False
	else:
		paths = [[er, ec]]
		a = [er - relative_row, ec - relative_column]
		while True:
			if a == [sr - relative_row, sc - relative_column]:
				break
			a = parent[tuple(a)]
			paths.append([a[0] + relative_row, a[1] + relative_column])
		return paths[::-1]

def get_cloest_pair(a):

	def dist(a1, a2):
		(x1, y1) = a1
		(x2, y2) = a2
		return pow(pow(x1 - x2, 2) + pow(y1 - y2, 2), 0.5)
	pairs = []
	while a:
		first = a.pop(0)
		temp = 0
		minimum = float('inf')
		for j in range(len(a)):
			b = dist(first, a[j])
			if b < minimum:
				temp = j
				minimum = b
		pairs.append([first, a[temp]])
		a.pop(temp)
	return pairs
pairs2 = pairs[:]
pairs2.sort()
pairs2 = get_cloest_pair(pairs2)
solutions = []
remain_pairs = []
count = 0
for i in range(m):
	(p1, p2) = pairs2[i]
	normalized_value_inf[p1[0]][p1[1]] = normalized_value[p1[0]][p1[1]]
	normalized_value_inf[p2[0]][p2[1]] = normalized_value[p2[0]][p2[1]]
	path = shortest(normalized_value_inf, p1, p2)
	if path != False:
		for j in path:
			normalized_value_inf[j[0]][j[1]] = inf
		solutions.append(path)
	else:
		count += 1
		l = 10
		while path == False:
			path = shortest_relative(normalized_value_inf, p1, p2, l)
			l += 10
		for j in path:
			normalized_value_inf[j[0]][j[1]] = inf
		solutions.append(path)
all_cost = []
for i in range(len(solutions)):
	curr_cost = 0
	for j in solutions[i]:
		(x, y) = j
		curr_cost += value[x][y]
	all_cost.append([i, curr_cost])
for step in range(1, 3):
	for i in all_cost:
		if i[0] + step > m - 1:
			continue
		s1 = [solutions[i[0]][0][0], solutions[i[0]][0][1]]
		e1 = [solutions[i[0]][-1][0], solutions[i[0]][-1][1]]
		s2 = [solutions[i[0] + step][0][0], solutions[i[0] + step][0][1]]
		e2 = [solutions[i[0] + step][-1][0], solutions[i[0] + step][-1][1]]
		for j in solutions[i[0]]:
			normalized_value_inf[j[0]][j[1]] = normalized_value[j[0]][j[1]]
		for j in solutions[i[0] + step]:
			normalized_value_inf[j[0]][j[1]] = normalized_value[j[0]][j[1]]
		normalized_value_inf[s2[0]][s2[1]] = inf
		normalized_value_inf[e1[0]][e1[1]] = inf
		new_path1 = shortest(normalized_value_inf, s1, e2)
		if new_path1 == False:
			new_path2 = False
		else:
			for k in new_path1:
				normalized_value_inf[k[0]][k[1]] = inf
			normalized_value_inf[s1[0]][s1[1]] = inf
			normalized_value_inf[e2[0]][e2[1]] = inf
			normalized_value_inf[s2[0]][s2[1]] = normalized_value[s2[0]][s2[1]]
			normalized_value_inf[e1[0]][e1[1]] = normalized_value[e1[0]][e1[1]]
			new_path2 = shortest(normalized_value_inf, s2, e1)
			for k in new_path1:
				normalized_value_inf[k[0]][k[1]] = normalized_value[k[0]][k[1]]
		normalized_value_inf[e1[0]][e1[1]] = inf
		normalized_value_inf[e2[0]][e2[1]] = inf
		normalized_value_inf[s1[0]][s1[1]] = normalized_value[s1[0]][s1[1]]
		normalized_value_inf[s2[0]][s2[1]] = normalized_value[s2[0]][s2[1]]
		new_path3 = shortest(normalized_value_inf, s1, s2)
		if new_path3 == False:
			new_path4 = False
		else:
			for k in new_path3:
				normalized_value_inf[k[0]][k[1]] = inf
			normalized_value_inf[s1[0]][s1[1]] = inf
			normalized_value_inf[s2[0]][s2[1]] = inf
			normalized_value_inf[e1[0]][e1[1]] = normalized_value[e1[0]][e1[1]]
			normalized_value_inf[e2[0]][e2[1]] = normalized_value[e2[0]][e2[1]]
			new_path4 = shortest(normalized_value_inf, e1, e2)
			for k in new_path3:
				normalized_value_inf[k[0]][k[1]] = normalized_value[k[0]][k[1]]
		original_cost = all_cost[i[0]][1] + all_cost[i[0] + step][1]
		if new_path1 != False and new_path2 != False and (new_path3 != False) and (new_path4 != False):
			cost1 = 0
			for j in new_path1:
				cost1 += value[j[0]][j[1]]
			cost2 = 0
			for j in new_path2:
				cost2 += value[j[0]][j[1]]
			cost1_cost2 = cost1 + cost2
			cost3 = 0
			for j in new_path3:
				cost3 += value[j[0]][j[1]]
			cost4 = 0
			for j in new_path4:
				cost4 += value[j[0]][j[1]]
			cost3_cost4 = cost3 + cost4
			if cost1_cost2 > cost3_cost4 and cost1_cost2 > original_cost:
				solutions[i[0]] = new_path1
				solutions[i[0] + step] = new_path2
				all_cost[i[0]] = [i[0], cost1]
				all_cost[i[0] + step] = [i[0] + step, cost2]
				for k in new_path1:
					normalized_value_inf[k[0]][k[1]] = inf
				for k in new_path2:
					normalized_value_inf[k[0]][k[1]] = inf
			elif cost3_cost4 > cost1_cost2 and cost3_cost4 > original_cost:
				solutions[i[0]] = new_path3
				solutions[i[0] + step] = new_path4
				all_cost[i[0]] = [i[0], cost3]
				all_cost[i[0] + step] = [i[0] + step, cost4]
				for k in new_path3:
					normalized_value_inf[k[0]][k[1]] = inf
				for k in new_path4:
					normalized_value_inf[k[0]][k[1]] = inf
			else:
				for j in solutions[i[0]]:
					normalized_value_inf[j[0]][j[1]] = inf
				for j in solutions[i[0] + step]:
					normalized_value_inf[j[0]][j[1]] = inf
		elif new_path1 != False and new_path2 != False:
			cost1 = 0
			for j in new_path1:
				cost1 += value[j[0]][j[1]]
			cost2 = 0
			for j in new_path2:
				cost2 += value[j[0]][j[1]]
			cost1_cost2 = cost1 + cost2
			if cost1_cost2 > original_cost:
				solutions[i[0]] = new_path1
				solutions[i[0] + step] = new_path2
				all_cost[i[0]] = [i[0], cost1]
				all_cost[i[0] + step] = [i[0] + step, cost2]
				for k in new_path1:
					normalized_value_inf[k[0]][k[1]] = inf
				for k in new_path2:
					normalized_value_inf[k[0]][k[1]] = inf
			else:
				for j in solutions[i[0]]:
					normalized_value_inf[j[0]][j[1]] = inf
				for j in solutions[i[0] + step]:
					normalized_value_inf[j[0]][j[1]] = inf
		elif new_path3 != False and new_path4 != False:
			cost3 = 0
			for j in new_path3:
				cost3 += value[j[0]][j[1]]
			cost4 = 0
			for j in new_path4:
				cost4 += value[j[0]][j[1]]
			cost3_cost4 = cost3 + cost4
			if cost3_cost4 > original_cost:
				solutions[i[0]] = new_path3
				solutions[i[0] + step] = new_path4
				all_cost[i[0]] = [i[0], cost3]
				all_cost[i[0] + step] = [i[0] + step, cost4]
				for k in new_path3:
					normalized_value_inf[k[0]][k[1]] = inf
				for k in new_path4:
					normalized_value_inf[k[0]][k[1]] = inf
			else:
				for j in solutions[i[0]]:
					normalized_value_inf[j[0]][j[1]] = inf
				for j in solutions[i[0] + step]:
					normalized_value_inf[j[0]][j[1]] = inf
		else:
			for j in solutions[i[0]]:
				normalized_value_inf[j[0]][j[1]] = inf
			for j in solutions[i[0] + step]:
				normalized_value_inf[j[0]][j[1]] = inf
for i in solutions:
	print(len(i), end=' ')
	for j in i:
		print(*[k + 1 for k in j], end=' ')
	print()