"""Original lazy head-heap k-way merge, explicit late monotonicity failure."""
import heapq,json
from itertools import permutations

def merge(runs,counters,guard=True):
 if type(runs) is not list or len(runs)>4 or any(type(r) is not list or len(r)>8 for r in runs) or sum(map(len,runs))>32 or type(counters) is not list or len(counters)!=len(runs) or guard not in [True,False]:raise ValueError('0..4 bounded list-runs, counters per producer')
 iters=[iter(r) for r in runs];heap=[];last={};seen=set()
 def pull(i):
  try:row=next(iters[i])
  except StopIteration:return None
  counters[i]+=1
  if type(row) is not tuple or len(row)!=2 or type(row[0]) is not int or abs(row[0])>1000 or type(row[1]) is not str or not 1<=len(row[1])<=12:raise ValueError('integer score/stringID total key')
  if row[1] in seen:raise ValueError('duplicate ID, possibly discovered late')
  seen.add(row[1])
  if guard and i in last and row<last[i]:raise ValueError('late run inversion; previous outputs not rolled back')
  last[i]=row;return row
 for i in range(len(runs)):
  row=pull(i)
  if row is not None:heapq.heappush(heap,(row[0],row[1],i))
 while heap:
  score,ident,i=heapq.heappop(heap);yield(score,ident)
  row=pull(i)
  if row is not None:heapq.heappush(heap,(row[0],row[1],i))

def demo():
 runs=[[(1,'A'),(4,'D')],[(2,'B'),(4,'C')],[(0,'E'),(7,'F')]];counters=[0]*3;g=merge(runs,counters);prefix=[next(g) for _ in range(3)];counts_after_prefix=counters[:];rest=list(g);out=prefix+rest;ref=sorted(x for r in runs for x in r);assert out==ref==list(heapq.merge(*runs));assert counts_after_prefix==[2,1,2] and counters==[2,2,2]
 checks=0
 for rr in permutations(runs):
  data=list(rr);c=[0]*3;assert list(merge(data,c))==ref;checks+=1
 wrong=[[(4,'D'),(1,'A')],runs[1],runs[2]];unguarded=list(merge(wrong,[0]*3,False));assert unguarded!=ref and [x[1] for x in unguarded]==['E','B','C','D','A','F']
 guarded=merge(wrong,[0]*3);escaped=[]
 try:
  while True:escaped.append(next(guarded))
 except ValueError as e:message=str(e)
 except StopIteration:raise AssertionError('guard must reject inversion')
 assert [x[1] for x in escaped]==['E','B','C','D']
 empty=list(merge([[],[],[]],[0]*3));assert empty==[] and list(merge([],[]))==[]
 rejected=[]
 for label,rr in [('bad_key_type',[[('x','A')]]),('duplicate_id',[[(0,'A')],[(1,'A')]]),('too_many_runs',[[]]*5),('run_budget',[[(i,str(i)) for i in range(9)]])]:
  try:list(merge(rr,[0]*len(rr)))
  except ValueError:rejected.append(label)
  else:raise AssertionError('expected rejection')
 return {'authored_sorted_runs':runs,'first_three_outputs':prefix,'producer_consumption_after_three':counts_after_prefix,'remaining_outputs':rest,'all_outputs':out,'final_producer_consumption':counters,'all_six_run_permutations_equal':checks,'independent_full_sort_and_stdlib_merge_equal':True,'unsorted_run_with_guard_disabled':unguarded,'late_guard_failure':{'already_yielded_prefix':escaped,'error':message,'all_or_nothing_claimed':False},'empty_runs_result':empty,'invalid_inputs_rejected':rejected,'scope':'bounded in-memory list-producer simulation with lazy next counters, score/ID totalkey, no externaldisk/async/network/atomiccommit/infinite-stream benchmark; full JSON/output storage separate from heap heads'}
if __name__=='__main__':print(json.dumps(demo(),ensure_ascii=True,indent=2))