import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.TreeMap;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Collisions {
	public static void main(String[] args) throws IOException {
		float loadFactor = Float.parseFloat(args[0]);
		List<String> words = new ArrayList<String>();
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in, "ISO-8859-1"));
		String line;
		while ((line = in.readLine()) != null) words.add(line);
		int[] table = new int[upsize((int)(words.size() / loadFactor))];
		float trueLoadFactor = (float)words.size() / (float)table.length;
		System.out.println("true load factor: " + trueLoadFactor);
		// for (String word: words) ++table[word.hashCode() & (table.length - 1)];
		// for (String word: words) ++table[stir(word.hashCode()) & (table.length - 1)];
		for (String word: words) ++table[adahash(word) & (table.length - 1)];
		Map<Integer, Integer> counts = new TreeMap<Integer, Integer>();
		for (int count: table) {
			Integer n = counts.get(count);
			if (n == null) n = 0;
			counts.put(count, (n + 1));
		}
		for (Map.Entry<Integer, Integer> entry: counts.entrySet()) {
			System.out.println(Integer.toString(entry.getKey()) + ": " + entry.getValue() + " (" + (((float)entry.getValue()/(float)table.length) * 100.0) + ")");
		}
	}
	static int stir(int h) { // NICKED FROM OPENJDK
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}
	static int upsize(int initialCapacity) { // NICKED FROM OPENJDK
		int capacity = 1;
		while (capacity < initialCapacity) capacity <<= 1;
		return capacity;
	}
	static int adahash(String s) {
		int h = 0;
		for (int i = 0; i < s.length(); ++i) {
			h = (rotate(h, 3)) + s.charAt(i);
		}
		return h;
	}
	static int rotate(int x, int n) {
		return (x << n) | (x >>> (32 - n));
	}
}