Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]

    dpsum[i] = dpsum[i-1] + dp[i]

print(dp[-1] % 998244353)


### FIXED CODE ###

mod = 998244353
N, K = map(int, input().split())

S = []
for i in range(K):
    L, R = map(int, input().split())
    S.append((L, R))

dp = [0] * (N+1)
dpsum = [0] * (N+1)
dp[1] = 1
dpsum[1] = 1

for i in range(2, N+1):
    for s in S:
        l = i - s[1]
        r = i - s[0]
        if r < 1:continue
        l = max(1, l)

        dp[i] += dpsum[r] - dpsum[l-1]
        dp[i] %= mod

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod

print(dp[-1])
### BUGGY CODE ###

n, k = map(int, input().split())
p =[int(s) for s in input().split()]
s = 0
key = 0
pred = 0
for r in range(n-k+1):
    s2 = sum(p[r:r+k])
    if s2>s:
        s = s2
        key = r
for f in p[key:key+k]:
    pred+=(f+1)*0.5
print(pred)

### FIXED CODE ###

n, k = map(int, input().split())
p =[int(s) for s in input().split()]
s = 0
key = 0
pred = 0
acc = {}
for h in range(n):
    if h == 0:
        acc[0] = p[0]
    else:
        acc[h] = acc[h-1]+p[h]
for r in range(n-k+1):
    if r == 0:
        s2 = acc[k-1]
    else:
        s2 = acc[k+r-1]-acc[r-1]
    if s2>s:
        s = s2
        key = r
print(0.5*(s+k))
### BUGGY CODE ###

import sys
#import numpy as np
import bisect
sys.setrecursionlimit(10 ** 7)

# TLE
# PyPy3 (2.4.0) 2112 ms

N, Q = map(int, input().split())
STX = []
for _ in range(N):
    s, t, x = map(int, input().split())
    STX.append((s, t, x))

PEOPLE = []
for i in range(Q):
    d = int(input())
    PEOPLE.append((d, i))

ans = [-1] * Q

STX.sort(key=lambda x: x[2])

for s, t, x in STX:
    if len(PEOPLE) == 0:
        break

    i = bisect.bisect_left(PEOPLE, (s - x, -1))
    j = bisect.bisect_left(PEOPLE, (t - x, -1))

    if i == j:
        continue

    use = [PEOPLE[x][1] for x in range(i, j)]

    #print(len(PEOPLE), use)
    for k in use:
        ans[k] = x

    del PEOPLE[i:j]


print("\n".join(map(str, ans)))


### FIXED CODE ###

#D in [S_i-X_i,T_i-X_i) → Xiで止まる
import sys
input = sys.stdin.readline
from heapq import heappop,heappush
from collections import defaultdict

N,Q = map(int,input().split())
task = []

STX = [[int(x) for x in input().split()] for _ in range(N)]
for s,t,x in STX:
  task.append((t-x,0,x)) # xで止まらなくなる
  task.append((s-x,1,x)) # xで止まる

for i in range(Q):
  d = int(input())
  task.append((d,2,i)) # 止まる位置を答える
answer = [-1]*Q

task.sort()

# 引っかかってる場所の管理
se = set()
se_hp = [] # heapで最小値を先頭に保つ

# 小さい時刻から順に見ていく
for a,b,c in task:
  if not b: # b == 0
    se.remove(c)
  elif b&1: # b == 1
    se.add(c)
    heappush(se_hp,c)
  else: # b == 2
    while se_hp and se_hp[0] not in se:
      heappop(se_hp)
    answer[c] = se_hp[0] if se_hp else -1

print('\n'.join(map(str,answer)))
### BUGGY CODE ###

from collections import deque

N,Q = map(int,input().split())
dist = {i:[] for i in range(1,N+1)}
oya = [-1 for i in range(N+1)]
oya[1] = 0

for i in range(N-1):
  a,b = map(int,input().split())
  dist[a].append(b)
  dist[b].append(a)

kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      oya[t] = a

ans = [0 for i in range(N+1)]
for q in range(Q):
  a,b = map(int,input().split())
  ans[a] += b
  
kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      p = oya[t]
      ans[t] += ans[p]
      
print(*ans[1:])

### FIXED CODE ###

from collections import deque

N,Q = map(int,input().split())
dist = {i:[] for i in range(1,N+1)}
oya = [-1 for i in range(N+1)]
oya[1] = 0

for i in range(N-1):
  a,b = map(int,input().split())
  dist[a].append(b)
  dist[b].append(a)

kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      oya[t] = a

ans = [0 for i in range(N+1)]
for q in range(Q):
  a,b = map(int,input().split())
  ans[a] += b
  
kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      p = oya[t]
      ans[t] += ans[p]
      
print(*ans[1:])
### BUGGY CODE ###

import re
N,Q = map(int,input().split())
S = input()
pattern = re.compile(r'AC')

for i in range(Q):
    l,r = map(int,input().split())
    total = 0
    flag = 0
    for j in S[l-1:r]:
        if j == 'A':
            flag = 1
        elif j == 'C' and flag == 1:
            total += 1
        else:
            flag = 0
    
    print(total)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
lst = [0] * (N+1)
before = ''
count = 0
for i in range(len(S)-1):
    if S[i:i+2] == 'AC':
        count += 1
    lst[i+2] = count
for i in range(Q):
    l,r = map(int,input().split())
    print(lst[r]-lst[l])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000)
n, m = map(int, input().split())
bridge = list(map(int, sys.stdin.read().split()))
total = n*(n-1)//2
ans =[total]
u = [i for i in range(n+1)]
size = [1 for i in range(n+1)]
rank = [1 for i in range(n+1)]
def check(x, y):
    return find(x) != find(y)

def find(x):
    if x == u[x]:
        return x
    else:
        return u[x]

for x , y in zip(bridge[-2::-2],bridge[::-2]):
    if check(x, y):
        X = u[x]
        Y = u[y]
        total -= size[X] * size[Y]
        ans += [total]

        if rank[X] == rank[Y]:
            u = [Y if i == X else i for i in u]
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
        else:
            if rank[X] > rank[Y]:
                X, Y = Y, X
            rank =[x+1 if u[i] == u[Y] else x for i, x in enumerate(rank)]
            u = [Y if i == u[X] else i for i in u]
        size[Y] += size[X]

    else:
        ans += [total]

print(*ans[-2::-1], sep="\n")


### FIXED CODE ###

import sys
n , m, *e = map(int,sys.stdin.read().split())
total = n*(n-1)//2
ans =[total]
u = [-1]*(n+1)

def find(x):
    if u[x] < 0 :
        return x
    else:
        return find(u[x])

for x , y in zip(e[-2:1:-2],e[:1:-2]):
    x = find(x)
    y = find(y)
    x, y = sorted((x, y))
    if x != y:
        total -= u[x] * u[y]
        u[x] += u[y]
        u[y] = x
    ans += [total]

print(*ans[::-1], sep="\n")
### BUGGY CODE ###

n,k,*h=map(int,open(0).read().split());
dp=[0];
for i in range(1,n):dp+=[min(10**9*(i-j>k)+dp[j]+abs(h[j]-h[i])for j in range(i))];
print(dp[-1])

### FIXED CODE ###

n,k,*h=map(int,open(0).read().split());
dp=[0]*n;
for i in range(1,n):
    dp[i]=min(dp[j+max(i-k,0)]+abs(a-h[i])for j,a in enumerate(h[max(i-k,0):i]));
print(dp[-1])
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()
def sub(ii):
    dp = [0]*(k)
    dp[0] = 1
    for i in range(n):
        if i==ii:
            continue
        for j in range(k-1, a[i]-1, -1):
            dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if dp[i]>0)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = list(map(lambda x: min(int(x), k+1), input().split()))
a.sort()
mask = (1<<(k+1)) - 1
def sub(ii):
    dp = 1
    for i in range(n):
        if i==ii:
            continue
        dp |= (dp<<a[i]) & mask
#         for j in range(k-1, a[i]-1, -1):
#             dp[j] += dp[j-a[i]]
    val = max(i for i in range(k) if (dp>>i)&1)
    return val+a[ii]>=k
if sub(0):
    ans = 0
elif not sub(n-1):
    ans = n
else:
    l = 0
    r = n-1
    while l<r-1:
        m = (l+r)//2
        if sub(m):
            r = m
        else:
            l = m
    ans = l+1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
l = [a.pop()]
ans = 0

for i in range(n-1):
    m = a.pop()
    now = 0
    ind = 0
    for j in range(len(l)):
        b = min(l[j], l[(j+1)%len(l)])
        if b > now:
            now = b
            ind = j
    l.insert(ind+1, m)
    ans += now
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
q, r = divmod(n, 2)
print(a[0] + sum(a[1:q]) * 2 + a[q] * r)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    H, N = map(int, input().split())
    A = []
    B = []
    for _ in range(N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)

    dp = [float("inf")] * (H + 1)
    dp[0] = 0

    for h in range(0, H):
        for a, b in zip(A, B):
            tmp = dp[h] + b
            if h + a >= H and tmp < dp[H]:
                dp[H] = tmp
            elif h + a < H and tmp < dp[h + a]:
                dp[h + a] = tmp

    print(dp[-1])


if __name__ == "__main__":
    main()
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
    l, r = map(int, input().split())
    print(s[l-1:r].count("AC"))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
numofac = [0]*len(s)
cnt = 0
for i in range(1, len(s)):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
    numofac[i] = cnt

for _ in range(q):
    l, r = map(int, input().split())
    print(numofac[r-1]-numofac[l-1])
### BUGGY CODE ###

from operator import itemgetter
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = []

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E.append((D_i, i, -1))
        D[C[i]] = i

    for i in range(Q):
        l, r = map(int, input().split())
        E.append((l - 1, r - 1, i))

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*N
dp[0] = 1

ok = [0]*(N+1)
for _ in range(K):
    l, r = mapint()
    ok[l-1] += 1
    ok[r] -= 1
from itertools import accumulate
ok = list(accumulate(ok))
lis = [i for i in range(1, N+1) if ok[i-1]]
for i in range(N):
    for d in lis:
        if i-d>=0:
            dp[i] += dp[i-d]
            dp[i] %= mod

print(dp[-1])

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, K = mapint()
mod = 998244353
dp = [0]*(N+1)
dp[1] = 1

Ks = [list(mapint()) for _ in range(K)]
Ks.sort()

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sums(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

bit = Bit(N)
bit.add(1, 1)

for i in range(2, N+1):
    for l, r in Ks:
        if i-l<0:
            break
        dp[i] += bit.sums(i-l) - bit.sums(max(0, i-r-1))
        dp[i] %= mod
    bit.add(i, dp[i])

print(dp[-1])
### BUGGY CODE ###

N,T = map(int,input().split())
item=sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])

dp=[0]*(T+1)

for a,b in item:
    for t in reversed(range(T)):
        dist=min(T,t+a)
        dp[dist] = max(dp[t]+b,dp[dist])
print(max(dp))


### FIXED CODE ###

N,T = map(int,input().split())

item=[list(map(int,input().split())) for _ in range(N)]
item = sorted(item,key=lambda x:x[0])

dp=[[0]*(T+3000) for _ in range(N+1)]

for i,(a,b) in  enumerate(item,1):
    for t in reversed(range(T)):
        dist=t+a
        dp[i][dist] = max(dp[i-1][t]+b,dp[i][dist])
        dp[i][t]=max(dp[i-1][t],dp[i-1][t])
ans=0
for l in dp:
    ans=max(ans,max(l))
print(ans)
### BUGGY CODE ###


def main():
  import sys
  input = sys.stdin.readline

  N = int(input())
  A = list(map(int, input().split()))
  T = set(A)
  mod = 10 ** 9 + 7

  from fractions import gcd
  from functools import reduce

  def lcm(x, y):
    return x * y // gcd(x, y)

  L = reduce(lcm, T)

  ans = 0

  for i in range(N):
    ans += (L // A[i]) % mod

  print(ans % mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7

from fractions import gcd

L = A[0]
for i in range(1,N):
  L=(L*A[i])//gcd(L,A[i])

ans = 0

for i in range(N):
  ans += (L // A[i])

print(ans % mod)
### BUGGY CODE ###

import sys
read = sys.stdin.read
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def same(x, y):
        return find(x) == find(y)
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    par = [-1] * n
    friend = {e: set() for e in range(n)}
    table = [[0] * n for _ in range(n)]
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        friend[a].add(b)
        friend[b].add(a)
    for i1 in range(n):
        mem = members(i1)
        for meme in mem:
            table[i1][meme] = 1
        table[i1][i1] = 0
        for frie in friend[i1]:
            table[i1][frie] = 0
    m = map(int, read().split())
    cd = zip(m, m)
    for c, d in cd:
        c -= 1
        d -= 1
        table[c][d] = 0
        table[d][c] = 0
    for i1 in range(n):
        r = sum(table[i1])
        print(r, end=' ')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import defaultdict
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True
    def members(x):
        root = find(x)
        return [i for i in range(n) if find(i) == root]

    n, m, k = map(int, input().split())
    num_of_friends = [-1] * n
    par = [-1] * n
    for _ in range(m):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        unite(a, b)
        num_of_friends[a] += -1
        num_of_friends[b] += -1
    roots = defaultdict(int)
    #roots = {e: set() for e in range(n)}
    for i2 in range(n):
        roots[find(i2)] += 1
    for i3 in range(n):
        #num_of_friends[i3] += len(roots[find(i3)])
        num_of_friends[i3] += roots[find(i3)]
    for _ in range(k):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        if find(c) == find(d):
            num_of_friends[c] -= 1
            num_of_friends[d] -= 1

    for i in range(n):
        print(num_of_friends[i], end=' ')

if __name__ == '__main__':
    main()
### BUGGY CODE ###

from functools import lru_cache
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


@lru_cache(maxsize=None)
def f(c1, c2, c3):
    if c1 is 0 and c2 is 0 and c3 is 0:
        return 0

    res = (n \
           + (f(c1 - 1, c2, c3) * c1 if c1 else 0) \
           + (f(c1 + 1, c2 - 1, c3) * c2 if c2 else 0) \
           + (f(c1, c2 + 1, c3 - 1) * c3 if c3 else 0)) \
          / (c1 + c2 + c3)
    return res


n = int(input())
a = tuple(map(int, input().split()))

c = Counter(a)
c1 = c[1]
c2 = c[2]
c3 = c[3]

print(f(c1, c2, c3))

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

n, x = map(int, input().split())
while True:
    if n == 0 and x == 0:
        break
    cnt = 0
    sort_list = []
    for i in range(1, n+1):
        for j in range(1, n+1):
            for k in range(1, n+1):
                if i + j + k == x\
                and i != j != k\
                and i != j and i != k and j != k:
                    sort = sorted([i, j, k])
                    if sort not in sort_list:
                        sort_list.append(sort)
                        cnt += 1
    print(cnt)
    n, x = map(int, input().split())

### FIXED CODE ###

import itertools
while True:
    n, x = map(int, input().split())
    if n == 0\
    and x == 0:
        break

    a = [i for i in range(1, n+1)]
    b = [i for i in itertools.combinations(a, 3)]
    c = 0
    cnt = 0
    for i in range(len(b)):
        for j in range(3):
            c += b[i][j]
        if c == x:
            cnt += 1
        c = 0
    print(cnt)
### BUGGY CODE ###

a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]

e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=[[0,-1]]
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.pop(0)
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
    
  

  
  


### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
e=[[]for i in range(a)]

for i in range(a-1):
  c1,c2=map(int,input().split())
  e[c1-1].append(c2-1)
  e[c2-1].append(c1-1)

g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
### BUGGY CODE ###

N, M, Q = map(int, input().split())

# cum_sum[L][R]
cum_sum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map(int, input().split())
    cum_sum[L][R] += 1

for l in range(1, N+1):
    for r in range(1, N+1):
        cum_sum[l][r] += cum_sum[l][r-1]

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for l in range(p, q+1):
        ans += cum_sum[l][q] - cum_sum[l][p-1]
    print(ans)


### FIXED CODE ###

N, M, Q = map(int, input().split())

# cum_sum[L][R]
cum_sum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map(int, input().split())
    cum_sum[L][R] += 1

for l in range(1, N+1):
    for r in range(1, N+1):
        cum_sum[l][r] += cum_sum[l][r-1] + cum_sum[l-1][r] - cum_sum[l-1][r-1]

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