CodeEff/ECCO huggingface dataset:
# Original solution
def main():
    n, m, q = list(map(int, input().split()))
    trains = [list(map(int, input().split())) for _ in range(m)]
    questions = [list(map(int, input().split())) for _ in range(q)]

    for question in questions:
        a, b = question
        # result = [train for train in trains if a <= train[0] and train[1] <= b]
        result = list([x for x in trains if a <= x[0] and x[1] <= b])
        print((len(result)))

if __name__ == '__main__':
    main()


# Optimized solution
n, m, q = list(map(int, input().split()))
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

for i in range(n):
    for j in range(1, n-i+1):
        x = j + i
        cities[j][x] += cities[j][x-1] + cities[j+1][x] - cities[j+1][x-1]

for quest in quests:
    p, q = quest[0], quest[1]
    print((cities[p][q]))
# Original solution
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    for i in range(1, N+1):
        a[i] = list(itertools.accumulate(a[i]))

    for pp, qq in zip(p, q):
        print((int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)]))))
    # print(a)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()


# Optimized solution
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    a = [list(itertools.accumulate(x)) for x in a]
    a = [list(itertools.accumulate(s[::-1]))[::-1] for s in zip(*a)]

    for pp, qq in zip(p, q):
        # 転置略して逆指定
        print((a[qq][pp]))
    # print(*a, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()
# Original solution
n, m, q = list(map(int, input().split()))
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l,r)] = 0
for p, q in train:
    d[(p-1,q-1)] += 1
for l in range(n):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        add = 0
        for addl in range(l,l+w+1):
            add += d[(addl, l+w)]
        dp[l][l+w] = dp[l][l+w-1] + add
for l, r in quest:
    print((dp[l-1][r-1]))


# Optimized solution
n, m, q = list(map(int, input().split()))
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l+1,r+1)] = 0
for p, q in train:
    d[(p,q)] += 1
for l in range(1,n+1):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        dp[l+1][l+w+1] = dp[l+1][l+w] + dp[l+2][l+w+1] - dp[l+2][l+w] + d[(l+1,l+w+1)]
for l, r in quest:
    print((dp[l][r]))
# Original solution
N, M, Q = list(map(int, input().split()))
bord = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

for _ in range(M):
    left, right = list(map(int, input().split()))
    bord[left][right] += 1
# print(bord)
for i in range(1, N + 2):
    for j in range(1, N + 2):
        bord[i][j] += bord[i][j - 1]
# print(bord)
for _ in range(Q):
    left, right = list(map(int, input().split()))
    cost = 0
    for i in range(left, right + 1):
        cost += bord[i][right] - bord[i][left - 1]
    print(cost)


# Optimized solution
N, M, Q = list(map(int, input().split()))
areas = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

for _ in range(M):
    left, right = list(map(int, input().split()))
    areas[left][right] += 1
# print(areas)
for i in range(1, N + 2):
    for j in range(1, N + 2):
        areas[i][j] += areas[i][j - 1]
# print(areas)
for _ in range(Q):
    left, right = list(map(int, input().split()))
    cost = 0
    for i in range(left, right + 1):
        cost += areas[i][right] - areas[i][left - 1]
    print(cost)
# Original solution
import sys
from itertools import accumulate

def input():
    return sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M, Q = map(int, input().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    G[l - 1][r - 1] += 1

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.append(csum[q][q] - csum[q][p - 1] - csum[p - 1][q] + csum[p - 1][p - 1])

print(*ans, sep='\n')


# Optimized solution
import sys
from itertools import accumulate

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M, Q = map(int, readline().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, readline().split())
    G[l - 1][r - 1] += 1

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

ans = []
for _ in range(Q):
    p, q = map(int, readline().split())
    ans.append(csum[q][q] - csum[q][p - 1] - csum[p - 1][q] + csum[p - 1][p - 1])

print(*ans, sep='\n')
# Original solution
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M, Q = map(int, input().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    G[l - 1][r - 1] += 1

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.append(csum[q][q] - csum[q][p - 1] - csum[p - 1][q] + csum[p - 1][p - 1])

print(*ans, sep='\n')


# Optimized solution
import sys
from itertools import accumulate

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

N, M, Q = map(int, readline().split())
G = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, readline().split())
    G[l - 1][r - 1] += 1

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

ans = []
for _ in range(Q):
    p, q = map(int, readline().split())
    ans.append(csum[q][q] - csum[q][p - 1] - csum[p - 1][q] + csum[p - 1][p - 1])

print(*ans, sep='\n')
# Original solution
n,m,q=list(map(int,input().split()))
A=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  a,b=list(map(int,input().split()))
  A[a][b]+=1
B=[[0]*(n+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(n+1):
    if i!=0 and j!=0:
      B[i][j]=B[i-1][j]+B[i][j-1]+A[i][j]-B[i-1][j-1]
    elif i!=0:
      B[i][j]=B[i-1][j]+A[i][j]
    elif j!=0:
      B[i][j]=B[i][j-1]+A[i][j]
    else:
      B[i][j]=A[i][j]
for i in range(q):
  a,b=list(map(int,input().split()))
  print((B[b][b]-B[a-1][b]-B[b][a-1]+B[a-1][a-1]))

# Optimized solution
n,m,q=list(map(int,input().split()))
A=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  a,b=list(map(int,input().split()))
  A[a][b]=A[a][b]+1
B=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    B[i][j]=B[i-1][j]+B[i][j-1]-B[i-1][j-1]+A[i][j]
for i in range(q):
  x,y=list(map(int,input().split()))
  print((B[y][y]-B[y][x-1]-B[x-1][y]+B[x-1][x-1]))
# Original solution
# ABC106 D - AtCoder Express 2
n,m,q=list(map(int,input().split()))
mat=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=list(map(int,input().split()))
    mat[l][r]+=1

for i in range(n+1):
    for j in range(n+1):
        mat[i][j]+=mat[i-1][j]
        mat[i][j]+=mat[i][j-1]
        mat[i][j]-=mat[i-1][j-1]

for i in range(q):
    l,r=list(map(int,input().split()))
    ans=mat[r][r]+mat[l-1][l-1]-mat[l-1][r]-mat[r][l-1]
    print(ans)

# Optimized solution
# ABC106 D - AtCoder Express 2
n,m,q=list(map(int,input().split()))
mat=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=list(map(int,input().split()))
    mat[l][r]+=1

for i in range(n+1):
    for j in range(n+1):
        mat[i][j]+=mat[i-1][j]
for i in range(n+1):
    for j in range(n+1):
        mat[i][j]+=mat[i][j-1]

for i in range(q):
    l,r=list(map(int,input().split()))
    ans=mat[r][r]+mat[l-1][l-1]-mat[l-1][r]-mat[r][l-1]
    print(ans)
# Original solution
n,m,q=list(map(int,input().split()))

mat=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=list(map(int,input().split()))
    mat[l][r]+=1

for i in range(n+1):
    for j in range(n+1):
        mat[i][j]+=mat[i-1][j]
        mat[i][j]+=mat[i][j-1]
        mat[i][j]-=mat[i-1][j-1]

for i in range(q):
    l,r=list(map(int,input().split()))
    ans=mat[r][r]+mat[l-1][l-1]-mat[l-1][r]-mat[r][l-1]
    print(ans)


# Optimized solution
n,m,Q=list(map(int,input().split()))
mat=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l,r=list(map(int,input().split()))
  mat[l][r]+=1

for i in range(n+1):
  for j in range(n+1):
    mat[i][j]+=mat[i-1][j]
    mat[i][j]+=mat[i][j-1]
    mat[i][j]-=mat[i-1][j-1]

for i in range(Q):
  p,q=list(map(int,input().split()))
  s=mat[q][q]-mat[q][p-1]-mat[p-1][q]+mat[p-1][p-1]
  print(s)
# Original solution
N, M, Q = list(map(int, input().split()))

A = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
    l, r = list(map(int, input().split()))
    A[l][r] += 1
    
for i in range(Q):
    p, q = list(map(int, input().split()))
    cnt = 0
    for i in range(p, q + 1):
        cnt += sum(A[i][p : q + 1])
    print(cnt)

# Optimized solution
N, M, Q = list(map(int, input().split()))

A = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
    l, r = list(map(int, input().split()))
    A[l][r] += 1
    
for i in range(1, N + 1):
    for j in range(1, N + 1):
        A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j -1]
        
for i in range(Q):
    p, q = list(map(int, input().split()))
    print((A[q][q] - A[q][p - 1] - A[p - 1][q] + A[p - 1][p - 1]))
# Original solution
N,M,Q=list(map(int,input().split()))
L,R=[],[]
for i in range(M):
  l,r=list(map(int,input().split()))
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    if i>j:
      c[i][j]=0
    c[i][j]+=c[i][j-1]
ans=[0]*Q
for i in range(Q):
  for j in range(Pl[i],Ql[i]+1):
    ans[i]+=c[j][Ql[i]]-c[j][Pl[i]-1]
for i in range(Q):
  print((ans[i]))

# Optimized solution
N,M,Q=list(map(int,input().split()))
L,R=[],[]
for i in range(M):
  l,r=list(map(int,input().split()))
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)
# Original solution
from itertools import accumulate

n,m,q = list(map(int,input().split()))
li = [[0 for i in range(n+1)]for j in range(n+1)]
lin = []

for i in range(m):
    l,r = list(map(int,input().split()))
    li[l][r] += 1

for i in range(n+1):
    lin.append(list(accumulate(li[i])))

for i in range(q):
    l,r = list(map(int,input().split()))
    point = 0
    for i in range(l,r+1):
        point += lin[i][r]-lin[i][l-1]
    print(point)

# Optimized solution
from itertools import accumulate

n,m,q = list(map(int,input().split()))
li = [[0 for i in range(n+1)]for j in range(n+1)]
lin = []

for i in range(m):
    l,r = list(map(int,input().split()))
    li[l][r] += 1

for i in range(n+1):
    lin += [list(accumulate(li[i]))]

for i in range(q):
    l,r = list(map(int,input().split()))
    point = 0
    for i in range(l,r+1):
        point += lin[i][r]-lin[i][l-1]
    print(point)
# Original solution
N, M, Q = list(map(int, input().split()))

LR = [[0 for i in range(2)] for j in range(M)]
pq = [[0 for i in range(2)] for j in range(Q)]

for i in range(M):
    LR[i] = list(map(int, input().split()))

for i in range(Q):
    pq[i] = list(map(int, input().split()))

x = [[0 for i in range(N)] for j in range(N)]

# print(LR[0][0])

for i in range(M):
    # x[LR[i][1] - 1][LR[i][0] - 1] = x[LR[i][1] - 1][LR[i][0] - 1] + 1
    x[LR[i][1] - 1][LR[i][0] - 1] += 1

xacu = [[0 for i in range(N)] for j in range(N)]

for i in range(N):
    for j in range(N):
        if j == 0:
            xacu[i][j] = x[i][j]
        else:
            xacu[i][j] = xacu[i][j - 1] + x[i][j]

# print(xacu)

for i in range(Q):
    count = 0
    p = pq[i][0]
    for j in range(pq[i][1]):
        if p == 1:
            count = count + xacu[j][N - 1]
        else:
            count = count + xacu[j][N - 1] - xacu[j][p - 2]

    print(count)


# Optimized solution
N, M, Q = list(map(int, input().split()))

x = [[0 for i in range(N + 1)] for j in range(N + 1)]

for i in range(M):
    l, r = list(map(int, input().split()))
    x[l][r] += 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1]

for i in range(Q):
    p, q = list(map(int, input().split()))

    ans = x[N][q] - x[p - 1][q]
    print(ans)
# Original solution
N, M, Q = list(map(int, input().split()))

S = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    l, r = list(map(int, input().split()))
    S[l][r] += 1
    
for i in range(1, N+1):
    for j in range(N+1):
        S[i][j] += S[i-1][j]
        
for i in range(N+1):
    for j in range(1, N+1):
        S[i][j] += S[i][j-1]
      
for i in range(Q):
    p, q = list(map(int, input().split()))
    print((S[q][q]-S[q][p-1]-S[p-1][q]+S[p-1][p-1]))

# Optimized solution
N, M, Q = list(map(int, input().split()))
train = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(M):
    l, r = list(map(int, input().split()))
    train[l][r] +=1
    
for i in range(N+1):
    for j in range(N):
        train[i][j+1] += train[i][j]
        
for i in range(N):
    for j in range(N+1):
        train[i+1][j] += train[i][j]
        
for i in range(Q):
    p, q = list(map(int, input().split()))
    print((train[q][q]+train[p-1][p-1]-train[p-1][q]-train[q][p-1]))
# Original solution
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return list(map(int,input().split()))
def ii(): return int(eval(input()))
def isp(): return input().split()
def deb(text): print(("-------\n{}\n-------".format(text)))

INF=10**20
def main():
    N,M,Q=mi()
    Ls = []
    Rs = []
    for i in range(M):
        L,R=mi()
        Ls.append((L,i))
        Rs.append((R,i))

    Ls.sort()
    Rs.sort()

    L_indexs = [set()] * (M+1)
    R_indexs = [set()] * (M+1)

    _Ls = []
    _Rs = []
    for i in range(M):
        L,L_i = Ls[M-1-i]
        R,R_i = Rs[i]

        L_indexs[i+1] = L_indexs[i] | set([L_i])
        R_indexs[i+1] = R_indexs[i] | set([R_i])

        _Ls.append(Ls[i][0])
        _Rs.append(R)

        
        
    # print(L_indexs)
    # print(L_indexs,R_indexs)
    for i in range(Q):
        p,q=mi()
        L_i = bisect.bisect_left(_Ls,p)

        # print(L_i)
        
        R_i = bisect.bisect_right(_Rs,q)
        if R_i == M:
            R_i -= 1
        elif Rs[R_i][0] != q:
            R_i -= 1

        ans = 0
        # print(M-L_i,R_i, L_indexs[M-L_i],R_indexs[R_i+1])
        if R_indexs[R_i+1] > L_indexs[M-L_i]:
            for j in L_indexs[M-L_i]:
                if j in R_indexs[R_i+1]:
                    ans += 1
        else:
            for j in R_indexs[R_i+1]:
                if j in L_indexs[M-L_i]:
                    ans += 1
        
        print(ans)



if __name__ == "__main__":
    main()

# Optimized solution
import sys
sys.setrecursionlimit(10**9)

def mi(): return list(map(int,input().split()))
def ii(): return int(eval(input()))
def isp(): return input().split()
def deb(text): print(("-------\n{}\n-------".format(text)))

INF=10**20
def main():
    N,M,Q=mi()
    
    count = [[0] * (N+1) for _ in range(N+1)]
    for i in range(M):
        L,R=mi()
        count[L][R] += 1
    
    # print(count)
    dp = [[0] * (N+1) for _ in range(N+1)]

    for w in range(1,N+1):
        for h in range(1,N+1):
            l,r=N+1-w,h
            dp[w][h] += dp[w][h-1] + dp[w-1][h] - dp[w-1][h-1] + count[l][r]


    # print(dp)
    for i in range(Q):
        p,q=mi()
        w,h=N+1-p,q
        # print(w,h)
        print((dp[w][h]))

            






if __name__ == "__main__":
    main()
# Original solution
n=int(input())
il=list(map(int,input().split()))
s=0
t=0
cnt=[]
while t<n-1:
    if il[t]==il[t+1]:
        cnt.append(t+1-s)
        s=t+1
    t+=1
    if t==n-1:
        cnt.append(t+1-s)
ans=0
if len(cnt)<=3:
    print((sum(cnt)))
else:
    for i in range(len(cnt)-2):
        ans=max(ans,cnt[i]+cnt[i+1]+cnt[i+2])
    print(ans)

# Optimized solution
n=int(input())
il=list(map(int,input().split()))
s=0
cnt=[]
for t in range(n):
    if t==n-1:
        cnt.append(t+1-s)
        break
    if il[t]==il[t+1]:
        cnt.append(t+1-s)
        s=t+1
ans=0
if len(cnt)<=3:
    print((sum(cnt)))
else:
    for i in range(len(cnt)-2):
        ans=max(ans,cnt[i]+cnt[i+1]+cnt[i+2])
    print(ans)
# Original solution
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na, ne = min(d, a + da), min(100, e + de)
      if na == d:
        print((score + 1))
        return True

      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

while True:
  d, n = list(map(int, input().split()))
  if d == 0:
    break
  item_lst = [[] for _ in range(101)]
  for _ in range(n):
    a, e, r = list(map(int, input().split()))
    for i in range(r, 101):
      item_lst[i].append((a, e))
  search(item_lst)


# Optimized solution
from heapq import heappush, heappop
INF = 10 ** 20

def search(item_lst, d):
  visited = {}
  visited[(0, 0)] = True
  que = []
  heappush(que, (0, 0, 0))
  while que:
    score, a, e = heappop(que)
    for da, de in item_lst[e]:
      na = a + da
      if na >= d:
        print((score + 1))
        return True
      ne = e + de
      if ne > 100:
        ne = 100
      
      if (na, ne) not in visited:
        visited[(na, ne)] = True
        heappush(que, (score + 1, na, ne))
  
  print("NA")
  return False

def main():
  while True:
    d, n = list(map(int, input().split()))
    if d == 0:
      break
    item_lst = [[] for _ in range(101)]
    for _ in range(n):
      a, e, r = list(map(int, input().split()))
      for i in range(r, 101):
        item_lst[i].append((a, e))
    search(item_lst, d)
main()
# Original solution
N = int(input())
score = [list(map(int, input().split())) for _ in range(N)]
players = [0 for _ in range(N)]
for play in list(zip(*score)):
    for i, p in enumerate(play):
        if play.count(p) == 1:
            players[i] += p
print(*players, sep='\n')


# Optimized solution
N = int(input())
score = [input().split() for _ in range(N)]
players = [0]*N
for play in list(zip(*score)):
    for i, p in enumerate(play):
        if play.count(p) == 1:
            players[i] += int(p)
print(*players, sep='\n')
# Original solution
N,M = list(map(int,input().split()))
atob = []
btoz = []
for _ in range(M):
    a, b = list(map(int,input().split()))
    if a == 1:
        if b in btoz:
            print('POSSIBLE')
            break
        atob.append(b)
    elif b == N:
        if a in atob:
            print('POSSIBLE')
            break
        btoz.append(a)
else:print('IMPOSSIBLE')

# Optimized solution
N,M = list(map(int,input().split()))
atob = [0] * N
btoz = [0] * N
for _ in range(M):
    a, b = list(map(int,input().split()))
    if a == 1:atob[b-1] = 1
    elif a == N:btoz[b-1] = 1
    if b == 1:atob[a-1] = 1
    elif b == N:btoz[a-1] = 1

for i in range(N):
    if atob[i]*btoz[i] == 1:
        print('POSSIBLE')
        break
else:print('IMPOSSIBLE')
# Original solution
from collections import deque
n, m = list(map(int, input().split()))
x = deque()
y = deque()
for _ in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        x.append(b)
    elif b == n:
        y.append(a)
for i in x:
    if i in y:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')


# Optimized solution
n, m = list(map(int, input().split()))
x = [[0] * 2 for _ in range(n)]
for _ in range(m):
    a, b = list(map(int, input().split()))
    if a == 1:
        x[b - 1][0] = 1
    elif b == n:
        x[a - 1][1] = 1
if [1, 1] in x:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
# Original solution
n, m = list(map(int, input().split()))
l = list(list(map(int, input().split())) for _ in range(m))
c = []
for i in l:
  if i[0] == n:
    c.append(i[1])
    l.remove(i)
  elif i[1] == n:
    c.append(i[0])
    l.remove(i)
  elif 1 in i:
    continue
  else:
    l.remove(i)
    
for i in range(len(l)):
  if l[i][0] == 1:
    if l[i][1] in c:
      print('POSSIBLE')
      exit()
  if l[i][1] == 1:
    if l[i][0] in c:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')

# Optimized solution
n, m = list(map(int, input().split()))
c = [[] for _ in range(n+1)]
for i in range(m):
  a, b = list(map(int, input().split()))
  c[a].append(b)
  c[b].append(a)

for i in c[1]:
  if n in c[i]:
    print('POSSIBLE')
    exit()

print('IMPOSSIBLE')