Polycarpus has a hobby — he develops an unusual social network. His work is almost completed, and there is only one more module to implement — the module which determines friends. Oh yes, in this social network one won't have to add friends manually! Pairs of friends are deduced in the following way. Let's assume that user A sent user B a message at time t1, and user B sent user A a message at time t2. If 0 < t2 - t1 ≤ d, then user B's message was an answer to user A's one. Users A and B are considered to be friends if A answered at least one B's message or B answered at least one A's message.

You are given the log of messages in chronological order and a number d. Find all pairs of users who will be considered to be friends.

Input

The first line of the input contains two integers n and d (1 ≤ n, d ≤ 1000). The next n lines contain the messages log. The i-th line contains one line of the log formatted as "Ai Bi ti" (without the quotes), which means that user Ai sent a message to user Bi at time ti (1 ≤ i ≤ n). Ai and Bi are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and ti is an integer (0 ≤ ti ≤ 10000). It is guaranteed that the lines are given in non-decreasing order of ti's and that no user sent a message to himself. The elements in the lines are separated by single spaces.

Output

In the first line print integer k — the number of pairs of friends. In the next k lines print pairs of friends as "Ai Bi" (without the quotes). You can print users in pairs and the pairs themselves in any order. Each pair must be printed exactly once.

Examples

Input

4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4


Output

1
petya vasya


Input

1 1000
a b 0


Output

0

Note

In the first sample test case Vasya and Petya are friends because their messages' sending times are one second apart. Anya and Ivan are not, because their messages' sending times differ by more than one second.

Source: codeforces | Difficulty: MEDIUM
Tags: Implementation

Greedy algorithms


Solutions:
import re
from collections import Counter

class Task:
	data = []
	delta = 0
	friends = set()

	def getData(self):
		(n, self.delta) = [int(x) for x in input().split(' ')]
		for i in range(0, n):
			self.data += [input()]

	def solve(self):
		messages = dict()
		for line1 in self.data:
			(A1, B1, time1) = line1.split(' ')
			for line2 in self.data:
				(A2, B2, time2) = line2.split(' ')
				if A2 == B1 and B2 == A1 and (0 < abs(int(time2) - int(time1)) <= self.delta):
					self.friends.add(min(A2 + ' ' + B2, B2 + ' ' + A2))

	def printAnswer(self):
		print(len(self.friends))
		for pair in self.friends:
			print(pair)
task = Task()
task.getData()
task.solve()
task.printAnswer()


(n, d) = map(int, input().split())
arr = []
for _ in range(n):
	(a, b, c) = input().split()
	curr = [a, b, int(c)]
	arr.append(curr)
ans = []
for i in range(n):
	for j in range(i + 1, n):
		if abs(arr[i][2] - arr[j][2]) <= d and abs(arr[i][2] - arr[j][2]) > 0:
			if arr[i][0] == arr[j][1] and arr[i][1] == arr[j][0]:
				ans.append((arr[i][1], arr[i][0]))
		elif abs(arr[i][2] - arr[j][2]) > d:
			break
if ans == []:
	print(0)
else:
	distinct_ans = []
	for i in ans:
		i = list(i)
		x = i.sort()
		distinct_ans.append(i)
	stack = []
	for i in distinct_ans:
		if i not in stack:
			stack.append(i)
	print(len(stack))
	for i in stack:
		for j in i:
			print(j, end=' ')
		print()


(n, d) = map(int, input().split())
(ans, hist) = ([], [])
for i in range(n):
	s = input().split()
	t = int(s[2])
	for x in hist:
		if 0 < t - x[2] <= d and s[0] == x[1] and (s[1] == x[0]):
			a = sorted([x[0], x[1]])
			if not a in ans:
				ans.append(a)
	hist.append([s[0], s[1], t])
print(len(ans))
for x in ans:
	print(x[0], x[1])


def readln():
	return tuple(map(int, input().split()))
(n, d) = readln()
a = []
b = []
for _ in range(n):
	(p, q, t) = input().split()
	t = int(t)
	if p > q:
		a.append((p, q, t))
	else:
		b.append((q, p, t))
ans = set()
for (p, q, t) in a:
	for (p1, q1, t1) in b:
		if p == p1 and q == q1 and (0 < abs(t - t1) <= d):
			ans.add(p + ' ' + q)
print(len(ans))
print('\n'.join(ans))


l = input().split()
n = int(l[0])
d = int(l[1])
lfi = []
lofpairs = []
for you in range(n):
	s = input().split()
	for i in lfi:
		if s[0] == i[1] and s[1] == i[0]:
			if int(s[2]) - int(i[2]) <= d and int(s[2]) - int(i[2]) != 0:
				if (i[0], i[1]) not in lofpairs and (i[1], i[0]) not in lofpairs:
					lofpairs.append((i[0], i[1]))
	lfi.append(s)
print(len(lofpairs))
for i in lofpairs:
	print(i[0], i[1])


(n, d) = map(int, input().split())
(f, p, q, r) = ([], [], {}, 0)
for i in range(n):
	(a, b, t) = input().split()
	(u, v, t) = (a + ' ' + b, b + ' ' + a, int(t))
	if t == r:
		p.append((u, v))
	else:
		f += [min(x, y) for (x, y) in p if y in q and q[y] >= r - d]
		for (x, y) in p:
			q[x] = r
		(p, r) = ([(u, v)], t)
f = set(f + [min(x, y) for (x, y) in p if y in q and q[y] >= r - d])
print(len(f))
print('\n'.join(f))


(n, d) = map(int, input().split())
f = list()
m = dict()
for i in range(n):
	add = False
	(a, b, t2) = input().split()
	t2 = int(t2)
	c = m.get(b + ' ' + a, 0)
	if c != -1:
		if c != 0:
			for t1 in c:
				if 0 < t2 - t1 <= d:
					f.append(a + ' ' + b)
					m[b + ' ' + a] = -1
					m[a + ' ' + b] = -1
					add = True
					break
		if not add:
			c = m.get(a + ' ' + b, 0)
			if c == 0:
				m[a + ' ' + b] = [t2]
			elif c[0] != t2:
				m[a + ' ' + b] = [t2, c[0]]
print(len(f))
for i in f:
	print(i)


(n, d) = map(int, input().split())
L = []
pair = []
for it in range(n):
	j = input().split()
	j[2] = int(j[2])
	for i in L:
		if (0 < j[2] - i[2] <= d) & (i[0] == j[1]) & (i[1] == j[0]):
			if i[0] > i[1]:
				fri = [i[1], i[0]]
			else:
				fri = [i[0], i[1]]
			if pair.count(fri) == 0:
				pair.append(fri)
	L.append(j)
print(len(pair))
for i in pair:
	print(i[0], i[1])


import sys
from collections import Counter
(n, k) = map(int, input().split())
l = []
for i in range(n):
	(p, q, t) = map(str, sys.stdin.readline().split())
	t = int(t)
	l.append([[p, q], t])
p = []
for i in range(n):
	for j in range(i + 1, n):
		if l[j][1] - l[i][1] > k:
			break
		if Counter(l[i][0]) == Counter(l[j][0]) and l[j][1] - l[i][1] <= k and (l[j][1] - l[i][1] > 0) and (l[i][0] != l[j][0]):
			if l[i][0] not in p and l[i][0][::-1] not in p:
				p.append(l[i][0])
print(len(p))
if len(p) == 0:
	exit(0)
for i in p:
	print(i[0], i[1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys
from collections import Counter
(n, k) = map(int, input().split())
l = []
for i in range(n):
	(p, q, t) = map(str, sys.stdin.readline().split())
	t = int(t)
	l.append([[p, q], t])
p = []
for i in range(n):
	for j in range(i + 1, n):
		if l[j][1] - l[i][1] > k:
			break
		if Counter(l[i][0]) == Counter(l[j][0]) and l[j][1] - l[i][1] <= k and (l[j][1] - l[i][1] > 0) and (l[i][0] != l[j][0]):
			if l[i][0] not in p and l[i][0][::-1] not in p:
				p.append(l[i][0])
print(len(p))
if len(p) == 0:
	exit(0)
for i in p:
	print(i[0], i[1])


def min_positive_difference(numbers1, numbers2):
	min_difference = float('inf')
	if not numbers1 or not numbers2:
		return min_difference
	for n in numbers1:
		for m in numbers2:
			candidate = abs(n - m)
			if candidate < min_difference and candidate > 0:
				min_difference = candidate
	return min_difference
(n, d) = map(int, input().split())
messages = {}
for _ in range(n):
	(first, second, time) = input().split()
	if (first, second) in messages:
		messages[first, second].append(int(time))
	else:
		messages[first, second] = [int(time)]
result = []
for (first, second) in messages:
	if (second, first) in result:
		continue
	if 0 < min_positive_difference(messages[first, second], messages.get((second, first))) <= d:
		result.append((first, second))
print(len(result))
for (first, second) in result:
	print(first, second)


from itertools import dropwhile
(n, d) = map(int, input().split())
queue = []
ans = set()
for i in range(n):
	(a, b, time) = input().split()
	time = int(time)
	queue = list(dropwhile(lambda x: time - x[2] > d, queue))
	for msg in queue:
		if msg[0] == b and msg[1] == a and (msg[2] != time):
			ans.add((min(a, b), max(a, b)))
	queue.append((a, b, time))
print(len(ans))
while 1:
	try:
		t = ans.pop()
		print(t[0], t[1])
	except KeyError:
		break