#include <cstdio>
#include <map>
#include <string>

using FileManifest = std::multimap<std::string, std::string>;

int main()
{
  FileManifest manifest;

  // read from /etc/setup/*.lst.gz
  const FileManifest installed {
    {"/usr/bin/file11", "package1"}, // #1 package2
    {"/usr/bin/file12", "package1"}, // #2 package3
    {"/usr/bin/file21", "package2"},
    {"/usr/bin/file22", "package2"}, // #3 package3, package4
    {"/usr/bin/file11", "package2"}  // #1 package1
  };
  manifest.insert(installed.begin(), installed.end());

  // read from tar files to be installed
  const FileManifest install {
    {"/usr/bin/file31", "package3"},
    {"/usr/bin/file12", "package3"}, // #2 package1
    {"/usr/bin/file22", "package3"}, // #3 package2, package4
    {"/usr/bin/file41", "package4"},
    {"/usr/bin/file42", "package4"},
    {"/usr/bin/file22", "package4"}  // #3 package2, package3
  };
  manifest.insert(install.begin(), install.end());
  
  for (auto i = manifest.cbegin(), end = manifest.cend(); i != end; ) {
    auto j = i;
    if (++j != end && j->first == i->first) {
      std::printf("Packages");
      j = i;
      do
        std::printf(" %s", j->second.c_str());
      while (++j != end && j->first == i->first);
      std::printf(" contain file %s\n", i->first.c_str());
    }
  //else
    //std::printf("Package %s contains file %s\n",
    //            i->second.c_str(), i->first.c_str());
    i = j;
  }
  return 0;
}