Petya studies at university. The current academic year finishes with $n$ special days. Petya needs to pass $m$ exams in those special days. The special days in this problem are numbered from $1$ to $n$.

There are three values about each exam:  $s_i$ — the day, when questions for the $i$-th exam will be published,  $d_i$ — the day of the $i$-th exam ($s_i < d_i$),  $c_i$ — number of days Petya needs to prepare for the $i$-th exam. For the $i$-th exam Petya should prepare in days between $s_i$ and $d_i-1$, inclusive. 

There are three types of activities for Petya in each day: to spend a day doing nothing (taking a rest), to spend a day passing exactly one exam or to spend a day preparing for exactly one exam. So he can't pass/prepare for multiple exams in a day. He can't mix his activities in a day. If he is preparing for the $i$-th exam in day $j$, then $s_i \le j < d_i$.

It is allowed to have breaks in a preparation to an exam and to alternate preparations for different exams in consecutive days. So preparation for an exam is not required to be done in consecutive days.

Find the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.


-----Input-----

The first line contains two integers $n$ and $m$ $(2 \le n \le 100, 1 \le m \le n)$ — the number of days and the number of exams.

Each of the following $m$ lines contains three integers $s_i$, $d_i$, $c_i$ $(1 \le s_i < d_i \le n, 1 \le c_i \le n)$ — the day, when questions for the $i$-th exam will be given, the day of the $i$-th exam, number of days Petya needs to prepare for the $i$-th exam. 

Guaranteed, that all the exams will be in different days. Questions for different exams can be given in the same day. It is possible that, in the day of some exam, the questions for other exams are given.


-----Output-----

If Petya can not prepare and pass all the exams, print -1. In case of positive answer, print $n$ integers, where the $j$-th number is:  $(m + 1)$, if the $j$-th day is a day of some exam (recall that in each day no more than one exam is conducted),  zero, if in the $j$-th day Petya will have a rest,  $i$ ($1 \le i \le m$), if Petya will prepare for the $i$-th exam in the day $j$ (the total number of days Petya prepares for each exam should be strictly equal to the number of days needed to prepare for it).

Assume that the exams are numbered in order of appearing in the input, starting from $1$.

If there are multiple schedules, print any of them.


-----Examples-----
Input
5 2
1 3 1
1 5 1

Output
1 2 3 0 3 

Input
3 2
1 3 1
1 2 1

Output
-1

Input
10 3
4 7 2
1 10 3
8 9 1

Output
2 2 2 1 1 0 4 3 4 4 



-----Note-----

In the first example Petya can, for example, prepare for exam $1$ in the first day, prepare for exam $2$ in the second day, pass exam $1$ in the third day, relax in the fourth day, and pass exam $2$ in the fifth day. So, he can prepare and pass all exams.

In the second example, there are three days and two exams. So, Petya can prepare in only one day (because in two other days he should pass exams). Then Petya can not prepare and pass all exams.

Difficulty: introductory

Starter code:

Solutions:
def ke(i):
    return b[i]
n,m=map(int,input().split())
a=[0]*m
b=[0]*m
c=[0]*m
e=[]
ans=[0]*n
for i in range(m):
    a[i],b[i],c[i]=map(int,input().split())
    ans[b[i]-1]=m+1
    e.append(i)
e.sort(key=ke)
for i in range(m):
    k=0
    for j in range(a[e[i]]-1,b[e[i]]-1):
        if ans[j]==0:
            ans[j]=e[i]+1
            k+=1
        if k==c[e[i]]:
            break
    if k!=c[e[i]]:
        print(-1)
        return
for i in ans:
    print(i,end=' ')

n, m = list(map(int, input().split()))
L = []
for i in range(m):
    a, b, c = list(map(int, input().split()))
    L.append([b, a, c, i])
L.sort()

M = [-1 for i in range(n + 1)]
for i in range(m):
    M[L[i][0]] = m + 1
for i in range(1, n + 1):
    if M[i] == -1:
        f = False
        for j in range(m):
            if L[j][1] <= i and L[j][2] > 0 and i < L[j][0]:
                M[i] = L[j][3] + 1
                L[j][2] -= 1
                f = True
                break
        if not(f):
            M[i] = 0
f = True
for j in range(m):
    if L[j][2] > 0:
        f = False
if f:
    print(*M[1:])
else:
    print(-1)


T = input().split(' ')
n = int(T[0])
m = int(T[1])
L = [0] * n
M = []
D = [0] * m
F = [0] * m
for i in range(m):
    S = input().split(' ')
    a = int(S[0])
    b = int(S[1])
    c = int(S[2])
    L[b-1] = m+1
    F[i] = b-1
    M.append((a-1, b-2, i+1))
    D[i] = c
M.sort()
for i in range(n):
    if L[i] == 0:
        G = []
        for j in range(len(M)):
            if M[j][0]<=i:
                G.append((M[j][1], M[j][2]))
        G.sort()
        for k in range(len(G)):
            if D[G[k][1]-1] > 0 and F[G[k][1]-1]>i:
                D[G[k][1]-1]-=1
                L[i] = G[k][1]
                break
b = True
for j in range(len(D)):
    if D[j] > 0:
        b = False
if b:
    for i in range(n-1):
        print(L[i], end=' ')
    print(L[n-1])
else:
    print(-1)


n, m = list(map(int, input().split()))
prep = []

days = [-1] * n
release = []

for i in range(m):
    s_, d_, c_ = list(map(int, input().split()))
    release.append(s_)
    days[d_ - 1] = i
    prep.append(c_)

rel_on_day = {}
for i, r in enumerate(release):
    if r - 1 in rel_on_day:
        rel_on_day[r - 1].append(i)
    else:
        rel_on_day[r - 1] = [i]

ans = []

waiting = set()

exam_q = []
for d in days:
    if d != -1:
        exam_q.append(d)

#print(rel_on_day)

for i in range(n):
    if i in rel_on_day:
        waiting = waiting | set(rel_on_day[i])

 #   print(waiting)


    if days[i] != -1: #exam
        if prep[days[i]] == 0:
            ans.append(m + 1)
            waiting.remove(days[i])
        else:
            print(-1)
            return
    else: #choose closest unstudied exam
        chosen = None
        for ex in exam_q:
            if prep[ex] > 0 and ex in waiting:
                chosen = ex
                break
        if not chosen is None:
            prep[ex] -= 1
            ans.append(ex + 1)
        else:
            ans.append(0)

print(" ".join(list(map(str, ans))))


import sys










def __starting_point():
    n, m = [int(c) for c in input().split()]
    s = []
    d = []
    c = []
    studying = []
    for _ in range(m):
        x,y,z = [int(w) for w in input().split()]
        s.append(x)
        d.append(y)
        c.append(z)
        
    plan = []

    for i in range(1, n+1):
        
        if i in s:
            indices = [k for k, x in enumerate(s) if x == i]
            for idx in indices:
                studying.append( (d[idx], idx) )
            studying.sort()
        
        #print(studying)
        if i in d:
            idx = d.index(i)
            if (i, idx) in studying:
                print (-1)
                return
            else:
                plan.append(m+1)
        else:
            if not studying:
                plan.append(0)
                continue
            idx = studying[0][1]
            plan.append(idx+1)
            c[idx] -= 1
            if c[idx] == 0:
                studying = studying[1:]

    for i in plan:
        print (i, end=' ')
    print()






__starting_point()

# Hello World program in Python
class exam:
    def __init__(self, tickets, ex_day, prep_days, index):
        self.tick = tickets-1
        self.ex_day = ex_day-1
        self.prep_days = prep_days
        self.index = index


def task():
    n, m = [int(x) for x in input().split(' ')]
    exs = list()
    for i in range(m):
        a, b, c = [int(x) for x in input().split(' ')]
        exs.append(exam(a, b, c, i + 1))
    s = sum((x.prep_days for x in exs))
    if s > n - m:
        print(-1)
        return -1
    exs = sorted(exs, key=lambda x: -x.tick)
    exdays = [x.ex_day for x in exs]
    days = [m+1 if i in exdays else 0 for i in range(0, n)]
    for ex in exs:
        d = ex.ex_day
        offs = 1
        for i in range(ex.prep_days):
            cont = True
            while (cont):
                if d - offs < ex.tick:
                    print(-1)
                    return
                if days[d - offs] == 0:
                    days[d - offs] = ex.index
                    cont = False
                else:
                    offs += 1

    print(' '.join((str(x) for x in days)))


task()

n, m = map(int, input().split())
exams = []
for i in range(m):
    e = list(map(int, input().split()))
    e.append(0)
    e.append(i + 1)
    exams.append(e)
exams.sort()
now, have, f, ans, c = 0, [], True, [], 0
for i in range(1, n + 1):
    while now < m and exams[now][0] == i:
        have.append(exams[now][1:])
        now += 1
        have.sort()
    if c < len(have) and have[c][0] == i:
        if have[c][1] == have[c][2]:
            ans.append(m + 1)
            c += 1
        else:
            f = False
            break
    else:
        j = 0
        while j < len(have) and have[j][1] == have[j][2]:
            j += 1
        if j == len(have):
            ans.append(0)
        else:
            ans.append(have[j][3])
            have[j][2] += 1
if f:
    for i in range(n):
        print(ans[i], end=' ')
else:
    print(-1)

n, m =[int(i) for i in input().split()]
s = [0] * m
d = [0] * m
c = [0] * m
for i in range(m):
	s[i], d[i], c[i] = [int(j) - 1 for j in input().split()]
	c[i] += 1
	if d[i] - s[i] < c[i]:
		print(-1)
		quit()

ans = [0] * n
for i in d:
	ans[i] = m + 1

exam = []
for i in range(n):
	exam.append([])
	for j in range(m):
		if s[j] <= i < d[j]:
			exam[i].append(j)

for i in range(n):
	if ans[i] == 0:
		day_min = n + 1
		for j in exam[i]:
			if (d[j] < day_min) and (c[j] > 0):
				day_min = d[j]
				exam_min = j
		if day_min != n + 1:
			ans[i] = exam_min + 1
			c[exam_min] -= 1
	else:
		if c[d.index(i)] != 0:
			print(-1)
			quit()

for i in range(n):
	if i != n - 1:
		print(ans[i], end = " ")
	else:
		print(ans[i])




(n, m) = list(map(int, input().split()))

array = [0] * (n + 1)
lst = []
for x in range(m):
    (s, d, c) = list(map(int, input().split()))
    lst.append((d, s, c, x + 1))

lst.sort()
i = 0
flag = True
for (d, s, c, p) in lst:
    x = s
    while c > 0 and x < d:
        if array[x] == 0:
            array[x] = p
            c -= 1
        x += 1
    if c != 0:
        flag = False
        break
    else:
        array[d] = m + 1

if flag:
    print(*array[1:])
else:
    print(-1)


import bisect
n,m=list(map(int,input().split()))
a=[]
b=[]
for i in range(m):
    s,d,c=list(map(int,input().split()))
    if c>d-s+1:
        print(-1)
        quit()
    l=bisect.bisect_left(b,d)
    a.insert(l,[s,d,c,i+1])
    b.insert(l,d)
ds=list('0' for i in range(n))
for i in range(m):
    s,d,c,mi=a[i]
    c0=0
    for j in range(s,d):
        if ds[j-1]=='0':
            ds[j-1]=str(mi)
            c0+=1
        if c0>=c:
            break
    if c0<c:
        print(-1)
        quit()
    ds[d-1]=str(m+1)
print(' '.join(ds))


[n, m] = [int(x) for x in input().split()]
I = 0
S = 1
D = 2
C = 3
exses = [[0, 0, 0, 0]]
pops = [0] * (n+1)
i = 1
while i <= m:
  [s, d, c] = [int(x) for x in input().split()]
  exses.append([i, s, d, c])
  pops[d] = i
  i += 1

i = 1
result = [0] * (n+1)
fail = False
while i <=n:
  if pops[i] != 0 and exses[pops[i]][C] == 0:
    result[i] = m+1
  elif pops[i] != 0 and exses[pops[i]][C] > 0:
    fail = True
    break
  else:
    ex = None
    min = n+1
    for e in exses:
      if e[D] > i and e[S] <= i and e[D] < min and e[C] > 0:
        min = e[D]
        ex = e
    if ex == None:
      result[i] = 0
    else:
      result[i] = ex[I]
      ex[C] -= 1
  i += 1

if fail:
  print(-1)
else:
  for x in result[1:]:
    print(x, end=' ')


def solve(n, m, ss, dd, cc):
	# day: i ( 1 -> n)
	# exam: j (0 -> m - 1)
	# date : d (1 -> n)
	# start: s (1 -> n)
	#

	date = [-1] * (n + 1)
	for j, d in enumerate(dd):
		date[d] = j		# mark exam date for i-th exam
	# print(date)
	start = [[] for _ in range(n + 1)]
	for j, d in enumerate(ss):
		start[d].append(j)
	# print(start)
	preps = []
	for i in range(1, n + 1): # for each day in n days
		if start[i]: # a start date
			preps += start[i] # add to the list of preparation
		# print(date)
		u = date[i]

		# print(i, u, start[i], end=' ')
		if u >= 0: # an exam date 0 -> m - 1
			j = u # j-th exam
			if cc[j] > 0: # failed to prepare
				# print('failed ', j + 1)
				return -1
			date[i] = m + 1 # take the exam
		else:
			# print(preps, end=' ')
			if not preps: # no subject to prepare
				date[i] = 0
			else: # prepare for subject closest to the exam date
				min_d = min(dd[j] for j in preps)
				for j in preps:
					if dd[j] == min_d: break
				date[i] = j + 1 # prepare for j-th exam
				cc[j] -= 1
				if cc[j] == 0:
					preps.remove(j)
		# print(date[i])

	return date[1:]





def main():
	n, m = [int(_) for _ in input().split()]

	s = []
	d = []
	c = []
	for i in range(m):
		s_, d_, c_ = [int(_) for _ in input().split()]

		s.append(s_)
		d.append(d_)
		c.append(c_)




	plan = solve(n, m, s, d, c)
	if isinstance(plan, list):
		print(' '.join(map(str, plan)))
	else:
		print(-1)




def __starting_point():
	main()

__starting_point()

import heapq
n,m = [int(s) for s in input().split()]
q0,q1 = [],[]
ans = [0]*n
for i in range(m):
    si, di, ci = [int(s) for s in input().split()]
    si -= 1
    di -= 1
    ans[di] = m+1
    heapq.heappush(q0, (si, di, ci, i))

for currday in range(n):
    while len(q0) and q0[0][0] <= currday:
        si,di,ci,i = heapq.heappop(q0)
        heapq.heappush(q1, (di,si,ci,i))
    if len(q1) and ans[currday] == 0:
        if currday > q1[0][0]:
            break
        ans[currday] = q1[0][3]+1
        if q1[0][2] == 1:
            heapq.heappop(q1)
        else:
            q1[0] = (q1[0][0], q1[0][1], q1[0][2]-1, q1[0][3])

if len(q1) == 0 and len(q0) == 0:
    print(*ans)
else:
    print(-1)

#!/usr/bin/env python3
from sys import stdin, stdout

def rint():
    return list(map(int, stdin.readline().split()))
#lines = stdin.readlines()

n, m = rint()

s = [0 for i in range(m)]
d = [0 for i in range(m)]
c = [0 for i in range(m)]


for i in range(m):
    s[i], d[i], c[i] = rint()

s_in_day = [set() for i in range(n+1)]
for i in range(m):
    day = s[i]
    s_in_day[day].add(i)

d_in_day = [-1 for i in range(n+1)]
for i in range(m):
    day = d[i]
    d_in_day[day] = i


di_sorted = [0 for i in range(m)]
di_sorted.sort(key=lambda x: d[i])

ans = [0 for i in range(n+1)]

candi_exam = set()
for day in range(1, n+1):
    for exam in s_in_day[day]:
        candi_exam.add(exam)
    if d_in_day[day] != -1:
        exam = d_in_day[day]
        if c[exam] != 0:
            print(-1)
            return
        ans[day] = m+1
        if exam in candi_exam:
            candi_exam.remove(exam)
        continue
    
    if len(candi_exam) == 0:
        ans[day] = 0
        continue
    min_d_day = 101
    busy_exam = 0
    for exam in candi_exam:
        if d[exam] < min_d_day:
            busy_exam = exam
            min_d_day = d[exam]
    
    ans[day] = busy_exam + 1
    c[busy_exam] -= 1
    if c[busy_exam] == 0:
        candi_exam.remove(busy_exam)
for i in range(m):
    if c[i] != 0:
        print(-1)
        return
print(*ans[1:])
    

        



aa = input()
n, m = [int(s) for s in aa.split(' ')]

exams = []
res = [0] * n

for i in range(m):
    aa = input()
    s,d,c = [int(s) for s in aa.split(' ')]
    el = {'s':s-1, 'd':d-1, 'c':c}
    exams.append(el)
    res[d - 1] = m + 1

for i in range(n-1, -1,-1):
    if res[i] > 0: #exam
        continue
    exam_num = -1
    min_zapas = n + 1
    for j in range(m):
        if (exams[j]['s'] <= i) and (i < exams[j]['d']) and (exams[j]['c'] > 0):
            zapas = i - exams[j]['s'] - exams[j]['c']
            if zapas < min_zapas:
                min_zapas = zapas
                exam_num = j
            if zapas < 0:
                break
    if exam_num == -1:
        continue
    
    res[i] = exam_num + 1
    exams[exam_num]['c'] = exams[exam_num]['c'] - 1
    
possible = True

for i in range(m):
    if exams[i]['c'] > 0:
        possible = False
        break

if possible:
    print(" ".join([str(x) for x in res]))
else:
    print(-1)

R = lambda: list(map(int, input().split()))

n, m= R()
a = []
for i in range(m):
    s, d, c = R()
    a.append([d, s, c, i+1])
a.sort()
r = [0] * (n+1)
for i in range(m): r[a[i][0]] = m + 1
for i in range(m):
    for j in range(a[i][1], a[i][0]):
        if a[i][2]==0: break
        elif r[j]==0:
            r[j] = a[i][3]
            a[i][2] -= 1
    if a[i][2]: print((-1)); return
print(*r[1:])


from collections import namedtuple

Exam = namedtuple("Exam", "id s d c")


def get_exam(day, exams, prepared):
    result = None

    for exam in exams:
        if exam.s <= day and prepared[exam.id] < exam.c and (result is None or exam.d < result.d):
            result = exam

    return result


n, m = list(map(int, input().split()))
exams = []
prepared = [0] * (m + 1)
schedule = [0] * (n + 1)

for i in range(m):
    s, d, c = list(map(int, input().split()))
    exams.append(Exam(i + 1, s, d, c))
    schedule[d] = -1

for day in range(1, n + 1):
    if schedule[day] == -1:
        print(-1)
        return

    if schedule[day] == m + 1:
        continue

    exam = get_exam(day, exams, prepared)

    if exam is None:
        continue

    prepared[exam.id] += 1
    schedule[day] = exam.id

    if prepared[exam.id] == exam.c:
        schedule[exam.d] = m + 1

print(' '.join(map(str, schedule[1:])))


a = input().split(" ")
a = [int(e) for e in a]

isdc = []
for i in range(a[1]):
    l = input().split(" ")
    l = [int(e) for e in l]
    isdc.append([i+1, l[0]-1, l[1]-1, l[2]])

l = [0] * a[0]
for e in isdc:
    l[e[2]] = len(isdc) + 1

isdc = sorted(isdc, key=lambda one: one[2])

for exam in isdc:
    day = exam[1]
    while day < exam[2]:
        if exam[3] == 0:
            break
        if l[day] == 0:
            l[day] = exam[0]
            exam[3] -= 1

        day += 1

    if exam[3] != 0:
        print(-1)
        return

for e in l:
    print(e, end=" ")


import heapq




n, m = map(int, input().split())
ans = [0]*n
ary = []
dp = [[0]*n for i in range(n)]
# print(dp)
tmp =0

while tmp < m:
    s, d, c = map(int, input().split())
    s -= 1; d -= 1
    ans[d] = m + 1
    ary.append((s, d, c + 1, tmp))
    # print('sdc', s,d,c)
    dp[s][d] = c + 1
    # print('dp', dp[s][d])
    tmp += 1


# print(dp)


d = 2
while d< n:
    l = 0
    while l+d < n:
        r = l+d

        dp[l][r] += dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1]
        # print('lr', l, r ,dp[l][r], dp[l + 1][r], dp[l][r - 1], dp[l + 1][r - 1])
        # if dp[l][r] > d:
        #     print(-1)
        #     quit(0)
        l += 1
    d+=1

l = 0
pos = 0
sary = sorted(ary)
# print(sary)
que = []

while l<n:
    while pos<m and sary[pos][0] == l:
        heapq.heappush(que, [sary[pos][1], sary[pos][2] , sary[pos][3]])
        pos += 1
    if ans[l] > 0:
        l += 1
        continue
    if que.__len__() == 0:
        # ans[l] = 0
        l += 1
        continue
    head = heapq.heappop(que)
    # print('head',l, head)
    if head[1] + l - 1 > head[0]:
        print(-1)
        quit(0)


    head[1] -= 1
    ans[l] = head[2] + 1
    if head[1] > 1:
        heapq.heappush(que, head)
    l += 1

if que.__len__() >0 or pos < m:
    print(-1)
else:
    print(*ans)

import heapq




n, m = map(int, input().split())
ans = [0]*n
ary = []
dp = [[0]*n for i in range(n)]
# print(dp)
tmp =0

while tmp < m:
    s, d, c = map(int, input().split())
    s -= 1; d -= 1
    ans[d] = m + 1
    ary.append((s, d, c + 1, tmp))
    # print('sdc', s,d,c)
    dp[s][d] = c
    # print('dp', dp[s][d])
    tmp += 1


# print(dp)


d = 2
while d< n:
    l = 0
    while l+d < n:
        r = l+d

        dp[l][r] += dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1]
        # print('lr', l, r ,dp[l][r], dp[l + 1][r], dp[l][r - 1], dp[l + 1][r - 1])
        if dp[l][r] > d:
            print(-1)
            quit(0)
        l += 1
    d+=1

l = 0
pos = 0
sary = sorted(ary)
# print(sary)
que = []

while l<n:
    while pos<m and sary[pos][0] == l:
        heapq.heappush(que, [sary[pos][1], sary[pos][2] , sary[pos][3]])
        pos += 1
    if ans[l] > 0:
        l += 1
        continue
    if que.__len__() == 0:
        # ans[l] = 0
        l += 1
        continue
    head = heapq.heappop(que)
    # print('head',l, head)
    if head[1] + l - 1 > head[0]:
        print(-1)
        quit(0)


    head[1] -= 1
    ans[l] = head[2] + 1
    if head[1] > 1:
        heapq.heappush(que, head)
    l += 1

if que.__len__() >0 or pos < m:
    print(-1)
else:
    print(*ans)

n,m =map(int,input().split())
l = list()
out = [0] * n
for i in range(m):
    s1,d1,c1 = map(int,input().split())
    l.append((s1,d1,c1,i))
l.sort(key=lambda x:x[1])
can = True
for j in l:
    out[j[1] - 1] = m + 1
for i in l:
    c = i[2]
    for t in range(i[0],i[1]):
        if out[t - 1] == 0 and c > 0:
            out[t - 1] = i[3] + 1
            c -= 1
        if c == 0:
            break
    if c != 0:
        print(-1)
        can = False
        break

if can is True:
    print(" ".join(map(str,out)))

rd = lambda: list(map(int, input().split()))
n, m = rd()
a = sorted(([*rd()] + [i + 1] for i in range(m)), key=lambda x: x[1])
r = [0] * n
for x in a:
    r[x[1] - 1] = m + 1
    for i in range(x[0] - 1, x[1] - 1):
        if not r[i]:
            r[i] = x[3]
            x[2] -= 1
            if not x[2]:
                break
    if x[2]:
        print(-1)
        return
print(*r)


# from itertools import accumulate
# from bisect import bisect_left
# from collections import OrderedDict

I = lambda: list(map(int, input().split()))

n, m = I()
dates = [0 for i in range(n + 1)]
data = []
for i in range(m):
    d = I() + [i + 1]
    if dates[d[1]]:
        print(-1)
        return
    dates[d[1]] = m + 1
    data.append(d)
data.sort(key = lambda x: x[1])
for s, d, c, idx in data:
    x = 0
    for i in range(s, d):
        if x == c:
            break
        if not dates[i]:
            dates[i] = idx
            x += 1
    if x != c:
        print(-1)
        return
print(*dates[1:])