typedef pair<KeyVector, StatVector> AggregatedRecord;

struct RecordTraits {
 static bool less(const AggregatedRecord& record1, const AggregatedRecord& record2)
 {
  return record1.first < record2.first;
 }
 static void merge(AggregatedRecord& dest, const AggregatedRecord& source)
 {
  for (size_t i = 0, imax = dest.second.size(); i < imax; ++i)
   dest.second[i].addBlock(source.second[i]);
 }
};

template<typename Input1, typename Input2, typename Output>
void mergeRecordSets(Input1& input1, Input2& input2, Output& output)
{
 AggregatedRecord mergeRecord;
 while (!input1.atEnd()) {
  if (input2.atEnd()) {
   do {
    output.write(input1.record());
    input1.moveNext();
   } while(!input1.atEnd());
   return;
  }
  if (RecordTraits::less(input2.record(), input1.record())) {
   output.write(input2.record());
   input2.moveNext();
  } else {
   if (RecordTraits::less(input1.record(), input2.record())) {
    output.write(input1.record());
   } else {
    mergeRecord = input2.record();
    RecordTraits::merge(mergeRecord, input1.record());
    output.write(mergeRecord);
    input2.moveNext();
   }
   input1.moveNext();
  }
 }
 while (!input2.atEnd()) {
  output.write(input2.record());
  input2.moveNext();
 }
}