/* Copyright (C) 2001 Markus Schoder
 
   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.
 
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.  */

#include <iostream>
#include <vector>
#include <string>
#include <stdlib.h>

using namespace std;

typedef unsigned long UINT32;

namespace {
const size_t buf_size = 5120;
char buf[buf_size];

struct Fingerprint
{
  string name;
  UINT32 u[8];
};

inline UINT32
hex_nibble(char c)
{
  return c - (c > '9' ? 'a' - 10 : '0');
}

UINT32
hex_convert_long(const char *s)
{
  UINT32 val = 0;
  for(int i = 0; i < 8; ++i)
  {
    val <<= 4;
    val += hex_nibble(s[i]);
  }
  return val;
}

void
hex_convert8(UINT32 *p, const char *s)
{
  for(int i = 0; i < 8; ++i)
    p[i] = hex_convert_long(s + i * 8);
}

inline int
count_bits(UINT32 u)
{
  if(u == 0)
    return 0;

  int diff = 1;
  while(u &= u - 1)
    ++diff;

  return diff;
}

inline int
le_bits_diff(UINT32 *p1, UINT32 *p2, int max_diff)
{
  int diff = 0;
  for(int i = 0; i < 8; ++i)
  {
    diff += count_bits(p1[i] ^ p2[i]);
    if(diff > max_diff)
      break;
  }
  return diff;
}
}

int
main(int argc, char *argv[])
{
  if(argc > 2)
  {
    cerr << "Usage: " << argv[0] << " [threshold]\n";
    return 1;
  }
  double threshold = 0.9;
  if(argc == 2)
    threshold = strtod(argv[1], 0);

  vector<Fingerprint> a;
  while(cin.getline(buf, buf_size))
  {
    char *p = strchr(buf, ':');
    if(!p)
      continue;
    a.push_back();
    a.back().name = string(buf, p - buf);
    hex_convert8(a.back().u, p + 1);
  }

  size_t n = a.size();
  int max_diff = (int)(256 * (1.0 - threshold));
  for(size_t i = 0; i < n - 1; ++i)
  {
    UINT32 *p = a[i].u;
    for(size_t j = i + 1; j < n; ++j)
    {
      int differing_bits = le_bits_diff(p, a[j].u, max_diff);
      if(differing_bits <= max_diff)
	cout << a[i].name << " " << a[j].name << ": "
	     << 1.0 - differing_bits / 256.0 << endl;
    }
  }
}