'''import random
f = open('input.txt','w')
n = random.randint(1,100)
n= 100000
q = random.randint(1,100)
q = 100000
f.write(str(n)+' '+str(q)+'\n')
x = 1000000
for i in range(n):
s = '1'
y = random.randint(1,max(1,x-i-1))
x-=y
s += ''.join(random.choice('01') for _ in range(y-1))
f.write(str(s)+'\n')
x = 100000
for _ in range(q):
l = random.randint(1,n)
r = random.randint(1,n)
if l>r:
t = r
r = l
l = t
s = '1'
y = random.randint(1,max(1,x-i-1))
x-=y
s += ''.join(random.choice('01') for _ in range(y-1))
f.write(str(l)+' '+str(r)+' '+s+'\n')'''
import random
f = open('input.txt','w')
n= 10
q = 100
f.write(str(n)+' '+str(q)+'\n')
for i in range(n):
s = '1'
s += ''.join(random.choice('01') for _ in range(9))
f.write(str(s)+'\n')
for _ in range(q):
l = random.randint(1,n)
r = random.randint(1,n)
if l>r:
t = r
r = l
l = t
s = '1'
s += ''.join(random.choice('01') for _ in range(9))
f.write(str(l)+' '+str(r)+' '+s+'\n')
JycnaW1wb3J0IHJhbmRvbQpmID0gb3BlbignaW5wdXQudHh0JywndycpCm4gPSByYW5kb20ucmFuZGludCgxLDEwMCkKbj0gMTAwMDAwCnEgPSByYW5kb20ucmFuZGludCgxLDEwMCkKcSA9IDEwMDAwMApmLndyaXRlKHN0cihuKSsnICcrc3RyKHEpKydcbicpCnggPSAxMDAwMDAwCmZvciBpIGluIHJhbmdlKG4pOgoJcyA9ICcxJwoJeSA9IHJhbmRvbS5yYW5kaW50KDEsbWF4KDEseC1pLTEpKQoJeC09eQoJcyArPSAnJy5qb2luKHJhbmRvbS5jaG9pY2UoJzAxJykgZm9yIF8gaW4gcmFuZ2UoeS0xKSkKCWYud3JpdGUoc3RyKHMpKydcbicpCgp4ID0gMTAwMDAwCmZvciBfIGluIHJhbmdlKHEpOgoJbCA9IHJhbmRvbS5yYW5kaW50KDEsbikKCXIgPSByYW5kb20ucmFuZGludCgxLG4pCglpZiBsPnI6CgkJdCA9IHIKCQlyID0gbAoJCWwgPSB0CglzID0gJzEnCgl5ID0gcmFuZG9tLnJhbmRpbnQoMSxtYXgoMSx4LWktMSkpCgl4LT15CglzICs9ICcnLmpvaW4ocmFuZG9tLmNob2ljZSgnMDEnKSBmb3IgXyBpbiByYW5nZSh5LTEpKQoJZi53cml0ZShzdHIobCkrJyAnK3N0cihyKSsnICcrcysnXG4nKScnJwoKCmltcG9ydCByYW5kb20KZiA9IG9wZW4oJ2lucHV0LnR4dCcsJ3cnKQpuPSAxMApxID0gMTAwCmYud3JpdGUoc3RyKG4pKycgJytzdHIocSkrJ1xuJykKZm9yIGkgaW4gcmFuZ2Uobik6CglzID0gJzEnCglzICs9ICcnLmpvaW4ocmFuZG9tLmNob2ljZSgnMDEnKSBmb3IgXyBpbiByYW5nZSg5KSkKCWYud3JpdGUoc3RyKHMpKydcbicpCmZvciBfIGluIHJhbmdlKHEpOgoJbCA9IHJhbmRvbS5yYW5kaW50KDEsbikKCXIgPSByYW5kb20ucmFuZGludCgxLG4pCglpZiBsPnI6CgkJdCA9IHIKCQlyID0gbAoJCWwgPSB0CglzID0gJzEnCglzICs9ICcnLmpvaW4ocmFuZG9tLmNob2ljZSgnMDEnKSBmb3IgXyBpbiByYW5nZSg5KSkKCWYud3JpdGUoc3RyKGwpKycgJytzdHIocikrJyAnK3MrJ1xuJyk=