"""
核心关系式:
若两个相邻区间:[a,b](有xa个0,ya个1,ka个01子序列), [b+1,c](有xb个0,yb个1,kb个01子序列)
则合成的新区间:[a,c]有ka+kb+xa*yb个01子序列, 即新区间的01子序列个数与原来两个区间具体的排列方式无关.
若已知一个区间的0个数和1个数, 则当它左侧全为0, 右侧全为1时, 有最大的01子序列个数, 最大值为0、1个数的乘积.

对于两个大小区间, D1:[li,ri],D2:[lj,rj], 小区间D1包含于大区间D2, 即lj<=li<=ri<=rj.
把大区间分成三份:
[lj,li):长度为n=li-lj, 有xa个0、ya个1、ka个01子序列,
[li,ri]:长度为l=ri-li+1, 有xi个0、yi个1、ki个01子序列,
(ri,rj]:长度为m=rj-ri, 有xb个0、yb个1、kb个01子序列,
则有等式:
xa + xb + xi = xj       (1)
xa*yi + xi*yb + xa*yb + ka + kb + ki = kj   (2)
xa + ya = n     (3)
xb + yb = m     (4)
不等式:
ka >= 0         (5)
kb >= 0         (6)
xa >= 0         (7)
xb >= 0         (8)
ya >= 0         (9)
yb >= 0         (10)
ka <= xa*ya       (11)
kb <= xb*yb       (12)

剩下就是纯数学计算了, 我的思路是通过消元得到关于xa的不等式组, 查看xa的解的区间是否有整数解.
联立等式(1)(2)(3)(4), 可得:
ka + kb = D – xa*xa – C*xa  (13), 其中C=2*xi+m+yi-xj, D=kj-ki+xi*(xj-xi-m)
再结合(11)+(12):ka + kb <= xa*ya+xb*yb, 和(5)+(6):ka + kb >= 0,
可得两个不等式:
xa*xa – A*xa + B <= 0, 其中 A=xj+yi+n, B=kj-ki-xj*(m+xi-xj)
xa*xa + C*xa – D <= 0,
分别解得:[left1,right1], [left2,right2].
求交集得:xa∈[left0,right0]
联立(3)(7)(9), 可得:
0<=xa<=n
联立(1)(4)(8)(10), 可得:
xj-xi-m<=xa<=xj-xi
求交集得:xa∈[L,R]
再对xa∈[L,R]和xa∈[left0,right0]求交集，即可得xa的解.
求出xa的一个解后, 可根据(3)(6)(11)(13)将ka取最大值, kb取最小值.
"""
from math import sqrt

def makestr(x,k,l):
    ”’求满足长度为l, 含x个0, k个01子序列的一个字符串.这个字符串含有y=l-x个1.
    思路:
    1、先构造一个含y*(k//y)个01子序列的字符串，这个字符串左侧全是k//y个0,右侧全是y个1.
    2、在上述字符串中, 在从右往左数第k%y个1的左侧插入一个0, 得到一个含k个01子序列的新字符串.
    3、将剩余的0加入新字符串的最右侧, 所含的01子序列个数仍为k.”’
    y = l-x
    if y==0:
        return "0"*l
    if k%y == 0:
        return "0"*(k//y)+"1"*y+"0"*(x-k//y)
    return "0"*(k//y)+"1"*(y-k%y)+"0"+"1"*(k%y)+"0"*(x-k//y-1)

def main():
    length,num = map(int,input().split())
    limit = [] # 限制条件的集合
    for i in range(num):
        limit.append(list(map(int,input().split())))
    limit.sort(key=lambda x:x[1]-x[0]) # 将限制条件的区间从小到大排序
    li,ri,xi,yi,ki = limit[0]

    if ki > xi*yi: # 检测初始最小区间的限制条件
        return -1
    else: # 创建初始最小字符串
        s = makestr(xi,ki,ri-li+1)

    for idx in range(1,num): # 从小到大依次遍历条件的区间, 逐步扩大已知字符串的范围
        lj,rj,xj,yj,kj = limit[idx] # 大区间及其限制条件
        n,m = li-lj,rj-ri
        L,R = max(0,xj-xi-m),min(n,xj-xi) # xa∈[L,R], 即满足xa,xb,ya,yb非负的xa取值区间
        if L>R:
            return -1

        # 计算二次不等式组系数A,B,C,D
        A = xj+yi+n
        B = kj-ki-xj*(m+xi-xj)
        C = 2*xi+m+yi-xj
        D = kj-ki+xi*(xj-xi-m)

        if A*A<4*B or C*C<-4*D: # 二次不等式判别式, 有解的条件
            return -1

        # 解二次不等式组
        left1 = (A-sqrt(A*A-4*B))/2
        right1 = (A+sqrt(A*A-4*B))/2
        left2 = (-sqrt(C*C+4*D)-C)/2
        right2 = (sqrt(C*C+4*D)-C)/2

        # 求xa∈[left1,right1], x∈[left2,right2]的交集并将边界取整, xa∈[left0,right0]
        left0 = int(-((-max(left1,left2))//1))
        right0 = int(min(right1, right2)//1)
        if left0 > right0:
            return -1

        # 求满足xa∈[left0,right0], xa∈[L,R]的一个特解
        if left0 < L:
            if right0 >= L:
                xa = L
            else:
                return -1
        elif left0 <= R:
            xa = left0
        else:
            print(left0,right0,L,R)
            return -1

        # ka<=D-C*xa-xa*xa, ka<=xa*(n-xa), ka取最大, kb取最小
        ka,kb,xb = min(D-C*xa-xa*xa,xa*(n-xa)),max(0,D-C*xa-n*xa),xj-xi-xa
        s = makestr(xa,ka,n)+s+makestr(xb,kb,m) # 将已知字符串的范围从[li,ri]朝两侧扩展至[lj,rj]
        li,ri,xi,yi,ki = lj,rj,xj,yj,kj # 将当前限制条件更新为小区间的限制条件

    # 最终字符串的长度不足时两边补0
    if li>1:
        s = "0"*(li-1)+s
    if ri < length:
        s = s+"0"*(length-ri)
    return s

r = main() # 时间复杂度,空间复杂度均为O(n+m)
print(r)

09:52