map{$==/ /&&print-($x=s/.\s/++$=x$&/ger*1e9)%$m+$x,$/;$m=$_}<>