Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

In Chefland the ChefSanta gets a list of what children ask from him every year.
On Christmas Eve, the ChefSanta delivers the presents to the children. This year, after Santa finished delivering all the presents, he realized that he used last year’s list. Now he starts thinking about how he could fix this.
We know that

Santa has an infinite amount of every kind of present at home
Santa's reindeer can fly, so he doesn't need roads
Santa has a bag which has a maximum capacity; this capacity is given
Santa can leave an infinite amount of presents at every child's house at any moment except the end
At the end, the Santa has to go to his house, and every house should contain just the present the child from this house wished for.

Santa would like to minimize the total distance that he needs to travel to fix things. Can you help him?

You are not required to find the optimal solution. However, the better your solution is,
the more you will get points

------ Input ------ 

The first line contains T the number of test cases.
The next lines contain the descriptions of each test case.
The first line of each test case contains five space-separated integers N, G, B, X, Y, where N is the number of children in Chefland, G is the number of different presents, B is Santa's bag volume and X, Y are Santa's house coordinates.
The next line contains G integers P_{1}, ..., P_{G} denoting the volume of each present.
The i-th of the next N lines contains four space-separated integers X_{i}, Y_{i}, K_{i}, L_{i}, where X_{i}, Y_{i} are the coordinates of the i-th child's house, K_{i} is last year's present id and L_{i} is this year's present id.

------ Output ------ 

For each test case (in the order given in the input) the output consists of a sequence of commands for Santa (one command per line).
You can give the following commands to Santa:

0 — end of the communication
1 K — travel to X_{K}, Y_{K}, where K=0 means travel to Santa's house
2 K — put one of the presents of type P_{K} to the bag
3 K — take one of the presents of type P_{K} out from the bag

------ Constraints ------ 

$T = 3$
$N = 500$
$10 ≤ G ≤ 50$
$50 ≤ B ≤ 200$
$1 ≤ P_{i} ≤ 20$
$0 ≤ X, Y, X_{i}, Y_{i}  ≤ 10000$
$1 ≤  K_{i}, L_{i}  ≤ G $
$K_{i} != L_{i}$
$The coordinates of houses of all children and Santa's house are pairwise distinct.

------ Example ------ 

Input:
1
3 3 10 0 0
3 5 7
1 0 2 1 
0 1 3 2
1 1 1 3

Output:
1 1
2 2
1 3
2 1
1 2
3 2
2 3
1 3
3 3
1 1
3 1
1 0
0

------ Explanation: ------ 

start with empty bag from 0, 0

1 1            <--- score: 1

2 2            <--- doesn't affect the score, Santa's bag contains 2

1 3            <--- score: 2

2 1            <--- doesn't affect the score, Santa's bag contains 1, 2

1 2            <--- score: 3

3 2            <--- doesn't affect the score, Santa's bag contains 1

2 3            <--- doesn't affect the score, Santa's bag contains 1, 3

1 3            <--- score: 4

3 3            <--- doesn't affect the score, Santa's bag contains 1

1 1            <--- score: 5

3 1            <--- doesn't affect the score, Santa's bag became empty

1 0            <--- score: 6

0              <--- communication end

Another possible output:

start with empty bag from 0, 0

2 1            <--- doesn't affect the score, Santa's bag contains 1

1 1            <--- score: 1

3 1            <--- doesn't affect the score, Santa's bag became empty

2 2            <--- doesn't affect the score, Santa's bag contains 2

1 2            <--- score: 2.4142

3 2            <--- doesn't affect the score, Santa's bag became empty

2 3            <--- doesn't affect the score, Santa's bag contains 3

1 3            <--- score: 3.4142

3 3            <--- doesn't affect the score, Santa's bag became empty

2 1            <--- doesn't affect the score, Santa's bag contains 3

1 0            <--- score: 4.4142

0              <--- communication end

------ Scoring ------ 

The score for each test case is the (Euclidean) distance traveled by Santa. Your total score will be the sum of your scores over all the test cases in all the test files. There will be 10 official test files. During the contest you will be able to get your score on the first 2 test files. After the contest the score for the full test set will be shown.

------ Test Case Generation ------ 

When we say a number is chosen from (a,b), it means an integer number chosen randomly and uniformly between a and b inclusive.

$T is 3 (except sample)$
$N is 500 $
$G is chosen from (10, 50)$
$B is chosen from (50, 200)$
$Every coordinate is chosen uniquely from (0, 10000).$
$We choose a minP from (1, 5), and maxP from (5, 20). Every P_{i} is chosen from (minP, maxP).$
$For each i, distinct  K_{i} and L_{i}  are chosen from (1, G).$

Source: codechef | Difficulty: VERY_HARD


Solutions:
t = int(input())
while t > 0:
	(n, g, b, x, y) = map(int, input().split())
	gv = list(map(int, input().split()))
	a = []
	b = [0] * n
	for i in range(n):
		(p, q, r, s) = map(int, input().split())
		a.append((p, q, r, s))
	for i in range(n):
		print(1, i + 1)
		print(2, a[i][2])
		print(1, 0)
		print(3, a[i][2])
		print(2, a[i][3])
		print(1, i + 1)
		print(3, a[i][3])
		print(1, 0)
	print(0)
	t = t - 1


for _ in range(int(input())):
	(n, g, b, x, y) = map(int, input().split())
	a = [[0] * 7 for kk in range(n + 1)]
	p = list(map(int, input().split()))
	for i in range(n):
		q = list(map(int, input().split()))
		a[i + 1][1] = q[0]
		a[i + 1][2] = q[1]
		a[i + 1][3] = q[2]
		a[i + 1][4] = q[3]
		a[i + 1][5] = abs((q[0] - x) ** 2 + (q[1] - y) ** 2)
		a[i + 1][6] = i + 1
	bag = 0
	last = 0
	for i in range(1, n + 1):
		if a[i][3] == a[i][4]:
			continue
		else:
			print('2', end=' ')
			print(a[i][4])
			print('1', end=' ')
			print(i)
			print('3', end=' ')
			print(a[i][4])
			print('2', end=' ')
			print(a[i][3])
			print('1 0')
			print('3', end=' ')
			print(a[i][3])
	last = 0
	print('0')


for _ in range(int(input())):
	(n, g, b, x, y) = map(int, input().split())
	a = [[0] * 6 for kk in range(n + 1)]
	p = list(map(int, input().split()))
	for i in range(n):
		q = list(map(int, input().split()))
		a[i + 1][1] = q[0]
		a[i + 1][2] = q[1]
		a[i + 1][3] = q[2]
		a[i + 1][4] = q[3]
		a[i + 1][5] = abs((q[0] - x) ** 2 + (q[1] - y) ** 2)
	bag = 0
	last = 0
	for i in range(1, n + 1):
		if a[i][3] == a[i][4]:
			continue
		else:
			f = 0
			for j in range(1, n + 1):
				if a[j][3] == a[i][4]:
					f = 1
					bag = a[j][3]
					k = j
					a[j][3] = 0
					break
			if f == 0:
				k = 0
				bag = a[i][4]
				if last != k:
					print('1', end=' ')
					print(k)
					last = k
				print('2', end=' ')
				print(a[i][4])
				if last != i:
					print('1', end=' ')
					print(i)
					last = i
				print('3', end=' ')
				print(a[i][4])
				continue
			if k != last:
				print('1', end=' ')
				print(k)
				last = k
			print('2', end=' ')
			print(bag)
			if i != last:
				print('1', end=' ')
				print(i)
				last = i
			print('3', end=' ')
			print(bag)
	fin = -1
	for t in range(n, 0, -1):
		if a[t][3] != 0:
			fin = t
			break
	for t in range(1, n + 1):
		if a[t][3] != 0:
			if t != last:
				print('1', end=' ')
				print(t)
				last = t
			print('2', end=' ')
			print(a[t][3])
			if last != 0:
				print('1 0')
				last = 0
			if t != fin:
				print('3', end=' ')
				print(a[t][3])
	if last != 0:
		print('1 0')
		last = 0
	print('0')


for _ in range(int(input())):
	[n, g, b, x, y] = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	child = []
	visit = [0 for i in range(n)]
	for i in range(n):
		child.append([int(j) for j in input().split()])
	dist = 1e+18
	i = 0
	for j in range(n):
		if dist > (x - child[j][0]) ** 2 + (y - child[j][1]) ** 2:
			dist = (x - child[j][0]) ** 2 + (y - child[j][1]) ** 2
			i = j
	print(2, child[i][-1])
	c = 0
	while c < n:
		print(1, i + 1)
		c += 1
		print(3, child[i][-1])
		print(2, child[i][-2])
		visit[i] = 1
		if c == n:
			break
		lol = i
		dist = 1e+18
		for j in range(n):
			if visit[j] == 0 and child[j][-1] == child[i][-2]:
				if dist > (child[i][0] - child[j][0]) ** 2 + (child[i][1] - child[j][1]) ** 2:
					dist = (child[i][0] - child[j][0]) ** 2 + (child[i][1] - child[j][1]) ** 2
					lol = j
		if lol == i:
			print(1, 0)
			print(3, child[i][-2])
			for j in range(n):
				if visit[j] == 0:
					i = j
					print(2, child[i][-1])
					break
		else:
			i = lol
	print(1, 0)
	print(0)


class House(object):

	def __init__(self, ID, Xi, Yi, Ki, Li):
		self.ID = ID
		self.x = Xi
		self.y = Yi
		self.lastYearPresent = Ki
		self.thisYearPresent = Li
		if ID != 0:
			self.lastYearPresentWeight = weights[Ki]
			self.thisYearPresentWeight = weights[Li]
			self.hasPresentToTake = True
			self.hasPresentItWants = False
		else:
			self.hasPresentToTake = False
			self.hasPresentItWants = True
T = int(input())
for _ in range(T):
	(N, G, maxWeight, X, Y) = [int(x) for x in input().split()]
	weights = ['*'] + [int(x) for x in input().split()]
	houses = [House(0, X, Y, None, None)]
	for houseI in range(1, N + 1):
		(Xi, Yi, Ki, Li) = [int(x) for x in input().split()]
		houses.append(House(houseI, Xi, Yi, Ki, Li))
	presentsToTake = N
	presentsGiven = 0
	currentWeight = 0
	currentHouse = houses[0]
	currentSack = []
	del X, Y, houseI, Xi, Yi, Ki, Li
	while presentsToTake > 0:
		housesCanGoTo = [house for house in houses if house.hasPresentToTake]
		housesCanGoTo.sort(key=lambda newHouse: (currentHouse.x - newHouse.x) ** 2 + (currentHouse.y - newHouse.y) ** 2)
		targetHouse = housesCanGoTo[0]
		for christmasMagicI in range(min(1, len(housesCanGoTo))):
			extraGift = housesCanGoTo[christmasMagicI].thisYearPresent
		if currentWeight + targetHouse.lastYearPresentWeight <= maxWeight:
			print(1, targetHouse.ID)
			currentHouse = targetHouse
			if currentHouse.thisYearPresent in currentSack:
				print(3, currentHouse.thisYearPresent)
				presentsGiven += 1
				currentSack.remove(currentHouse.thisYearPresent)
				currentWeight -= currentHouse.thisYearPresentWeight
				currentHouse.hasPresentItWants = True
			print(2, currentHouse.lastYearPresent)
			presentsToTake -= 1
			currentSack.append(currentHouse.lastYearPresent)
			currentWeight += currentHouse.lastYearPresentWeight
			currentHouse.hasPresentToTake = False
		else:
			print(1, 0)
			currentHouse = houses[0]
			for present in currentSack:
				print(3, present)
			currentSack = []
			currentWeight = 0
	print(1, 0)
	currentHouse = houses[0]
	for present in currentSack:
		print(3, present)
	currentSack = []
	currentWeight = 0
	while presentsGiven < N:
		housesCanGoTo = [house for house in houses if not house.hasPresentItWants]
		route = []
		routeHouse = houses[0]
		while len(housesCanGoTo) > 0:
			housesCanGoTo.sort(key=lambda newHouse: (routeHouse.x - newHouse.x) ** 2 + (routeHouse.y - newHouse.y) ** 2)
			routeHouse = housesCanGoTo.pop(0)
			route.append(routeHouse)
		for targetHouse in route:
			if currentWeight + targetHouse.thisYearPresentWeight <= maxWeight:
				print(2, targetHouse.thisYearPresent)
				currentSack.append(targetHouse.thisYearPresent)
				currentWeight += targetHouse.thisYearPresentWeight
			else:
				break
		for targetHouse in route:
			if targetHouse.thisYearPresent in currentSack:
				print(1, targetHouse.ID)
				currentHouse = targetHouse
				print(3, currentHouse.thisYearPresent)
				presentsGiven += 1
				currentSack.remove(currentHouse.thisYearPresent)
				currentWeight -= currentHouse.thisYearPresentWeight
				currentHouse.hasPresentItWants = True
			else:
				print(1, 0)
				currentHouse = houses[0]
				break
	if currentHouse != houses[0]:
		print(1, 0)
	print(0)


class House(object):

	def __init__(self, ID, Xi, Yi, Ki, Li):
		self.ID = ID
		self.x = Xi
		self.y = Yi
		self.lastYearPresent = Ki
		self.thisYearPresent = Li
		if ID != 0:
			self.lastYearPresentWeight = weights[Ki]
			self.thisYearPresentWeight = weights[Li]
			self.hasPresentToTake = True
			self.hasPresentItWants = False
		else:
			self.hasPresentToTake = False
			self.hasPresentItWants = True
T = int(input())
for _ in range(T):
	(N, G, maxWeight, X, Y) = [int(x) for x in input().split()]
	weights = ['*'] + [int(x) for x in input().split()]
	houses = [House(0, X, Y, None, None)]
	for houseI in range(1, N + 1):
		(Xi, Yi, Ki, Li) = [int(x) for x in input().split()]
		houses.append(House(houseI, Xi, Yi, Ki, Li))
	for i in range(1, N + 1):
		house = houses[i]
		print(2, house.thisYearPresent)
		print(1, i)
		print(3, house.thisYearPresent)
		print(2, house.lastYearPresent)
		print(1, 0)
		print(3, house.lastYearPresent)
	print(0)


for t in range(int(input())):
	(n, gifts, vol, x, y) = map(int, input().split())
	giftVol = list(map(int, input().split()))
	wanted = [0] * (n + 2)
	curGifts = [0] * (n + 2)
	for i in range(1, n + 1):
		(a, b, c, d) = map(int, input().split())
		wanted[i] = d
		curGifts[i] = c
	for i in range(1, n + 1):
		hh = wanted[i]
		print('2', hh)
		print('1', i)
		print('3', hh)
		print('2', curGifts[i])
		print('1 0')
		print('3', curGifts[i])
	print(0)


import math

def dist(X1, Y1, X2, Y2):
	l = math.sqrt((X1 - X2) * (X1 - X2) + (Y1 - Y2) * (Y1 - Y2))
	return l

class Solver(object):

	def __init__(self, N, G, B, X, Y, P):
		self.N = N
		self.G = G
		self.B = B
		self.X = X
		self.Y = Y
		self.P = P
		self.children = []
		self.children_id = 1
		self.score = 0
		self.prev_X = 0
		self.prev_Y = 0

	def update_score_and_pos(self, new_X, new_Y):
		t = dist(self.prev_X, self.prev_Y, new_X, new_Y)
		self.score += t
		self.prev_X = new_X
		self.prev_Y = new_Y

	def add_child(self, X, Y, K, L):
		self.children.append((self.children_id, X, Y, K, L))
		self.children_id += 1

	def pick_correct_gift(self, child):
		(child_id, X, Y, K, L) = child
		print('2 %d' % L)

	def go_to_children(self, child):
		(child_id, X, Y, K, L) = child
		print('1 %d' % child_id)
		self.update_score_and_pos(X, Y)

	def put_correct_gift(self, child):
		(child_id, X, Y, K, L) = child
		print('3 %d' % L)

	def take_wrong_gift(self, child):
		(child_id, X, Y, K, L) = child
		print('2 %d' % K)

	def go_back_home(self):
		print('1 0')
		self.update_score_and_pos(0, 0)

	def empty_wrong_gift(self, child):
		(child_id, X, Y, K, L) = child
		print('3 %d' % K)

	def end(self):
		print('0')

	def naive_solution(self):
		for child in self.children:
			self.pick_correct_gift(child)
			self.go_to_children(child)
			self.put_correct_gift(child)
			self.take_wrong_gift(child)
			self.go_back_home()
			self.empty_wrong_gift(child)
		self.end()

	def compute_solution(self):
		self.naive_solution()
T = int(input())
for t in range(T):
	(N, G, B, X, Y) = list(map(int, input().split()))
	P = list(map(int, input().split()))
	S = Solver(N, G, B, X, Y, P)
	for i in range(N):
		(Xi, Yi, Ki, Li) = list(map(int, input().split()))
		S.add_child(Xi, Yi, Ki, Li)
	S.compute_solution()


T = int(input())
for _ in range(T):
	(N, G, B, X, Y) = (int(i) for i in input().split())
	P = [int(i) for i in input().split()]
	child_cordinate = []
	child_wish = []
	for i in range(N):
		(x, y, k, l) = (int(i) for i in input().split())
		child_cordinate.append([x, y])
		child_wish.append([k, l])
	for i in range(N):
		print(2, child_wish[i][1])
		print(1, i + 1)
		print(3, child_wish[i][1])
		print(2, child_wish[i][0])
		print(1, 0)
		print(3, child_wish[i][0])
	print(0)


t = int(input())
while t:
	t -= 1
	(n, g, b, x, y) = list(map(int, input().split()))
	list(map(int, input().split()))
	for i in range(n):
		(x, y, k, l) = list(map(int, input().split()))
		print(2, l)
		print(1, i + 1)
		print(3, l)
		print(2, k)
		print(1, 0)
		print(3, k)
	print(0)


q = int(input().strip())

def doit(houses):
	for ind in range(len(houses)):
		house = houses[ind]
		print('2 ' + str(house[3]))
		print('1 ' + str(ind + 1))
		print('3 ' + str(house[3]))
		print('2 ' + str(house[2]))
		print('1 0')
		print('3 ' + str(house[2]))
	print('1 0')
	print('0')
for _ in range(q):
	(N, G, B, X, Y) = map(int, input().strip().split(' '))
	p = list(map(int, input().strip().split(' ')))
	houses = []
	for ind in range(N):
		(x, y, k, l) = map(int, input().strip().split(' '))
		houses.append((x, y, k, l))
	doit(houses)