The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Friends or Not

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarpus 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 *t*_{1}, and user *B* sent user *A* a message at time *t*_{2}. If 0 < *t*_{2} - *t*_{1} ≤ *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 "*A*_{i} *B*_{i} *t*_{i}" (without the quotes), which means that user *A*_{i} sent a message to user *B*_{i} at time *t*_{i} (1 ≤ *i* ≤ *n*). *A*_{i} and *B*_{i} are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and *t*_{i} is an integer (0 ≤ *t*_{i} ≤ 10000). It is guaranteed that the lines are given in non-decreasing order of *t*_{i}'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 "*A*_{i} *B*_{i}" (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.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 18:07:11 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|