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

s=input()
n=len(s)
t=[]
mod=2019
for i in range(n):
    a=0
    for j in range(i,n):
        a+=pow(10,n-1-j)*int(s[j])
    t.append(a%mod)
t.append(0)
from collections import Counter
d=Counter(t)
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
sum=0
p=1
d={}
d[0]=1
for i in range(n-1,-1,-1):
    sum=(sum+int(s[i])*p)%mod
    if sum in d:
        d[sum]+=1
    else:
        d[sum]=1
    p=(p*10)%mod
ans=0
for v in d.values():
    ans+=(v*(v-1))//2
print(ans)
### BUGGY CODE ###

# coding:utf-8

S = input()
Q = int(input())
queries = [input().rstrip('\n') for _ in range(Q)]
reverse = False

for query in queries:
    q = query.split(' ')
    if q[0] == '1':
        reverse = not reverse
    else:
        if q[1] == '1':
            S = q[2] + S if not reverse else S + q[2]
        else:
            S = S + q[2] if not reverse else q[2] + S
print(S) if not reverse else print(S[::-1])

### FIXED CODE ###

# coding:utf-8
from collections import deque

S = deque(input())
Q = int(input())
queries = [input().rstrip('\n') for _ in range(Q)]
reverse = False

for query in queries:
    q = query.split(' ')
    if q[0] == '1':
        reverse = not reverse
    else:
        if q[1] == '1':
            S.appendleft(q[2]) if not reverse else S.append(q[2])
        else:
            S.append(q[2]) if not reverse else S.appendleft(q[2])

if reverse:
    S.reverse()
print("".join(S))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

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

answer_list = [0] * M
prefectures = [0] * (M+1)
data_set = [[0]] * (N+1)

data_set_dict = {}

for i in range(M):
	P, Y = map(int, input().split())
	data_set_dict[i] = Y
	if data_set[P] == [0]:
		data_set[P] = [Y]
	else:
		data_set[P].append(Y)

for n in range(N):
	data_set[n].sort()

for i in range(M):
	a = data_set_dict[i]
	for n in range(1, N+1):
		answer = ''
		if a not in data_set[n]:
			pass
		else:
			for j in range(6-len(list(str(n)))):
				answer += '0'

			answer += str(n)

			for j in range(6-len(list(str(data_set[n].index(a)+1)))):
				answer += '0'

			answer += str(data_set[n].index(a)+1)
			print(answer)

### FIXED CODE ###

# -*- coding: utf-8 -*-

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

answer_list = [0] * M
prefectures = [0] * (N+1)
data_set = [0] * M

for i in range(M):
	P, Y = map(int, input().split())
	data_set[i] = [P, Y, i]

data_set.sort()

for i in range(M):
	answer = ''
	P, Y, a = data_set[i]
	prefectures[P] += 1

	for j in range(6-len(list(str(P)))):
		answer += '0'

	answer += str(P)

	for k in range(6-len(list(str(prefectures[P])))):
		answer += '0'

	answer += str(prefectures[P])

	answer_list[a] = answer

for i in range(M):
	print(answer_list[i])
### BUGGY CODE ###

def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    ans = 0
    for i in range(1, 2 ** Q):
        vec = [1] * N
        flag = [False] * N
        ans_ = 0
        for q in range(Q):
            # print((i >> q) % 2, end='')
            if (i >> q) % 2 == 0:
                continue
            a, b, c, d = abcd[q]
            if not flag[b-1]:
                if vec[a-1] + c > M:
                    break
                vec[b-1] = vec[a-1] + c
                ans_ += d
                flag[b-1] = True
                flag[a-1] = True
            elif vec[b-1] - vec[a-1] == c:
                ans_ += d
            else:
                break
        
        if vec != sorted(vec):
            continue
            
        # print(bin(i), vec, ans_)
        if ans_ == 448129:
            print('★')
        ans = max(ans, ans_)

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, M, Q = [int(x) for x in input().strip().split()]
    abcd = [0] * Q
    for q in range(Q):
        abcd[q] = [int(x) for x in input().strip().split()]

    abcd.sort(key=lambda x:(x[0],x[1]))
    vecs = []

    def makevecs(n, vecs, A):
        if n == N:
            vecs.append(A)
            return None
        for b in range(A[-1], M+1):
            makevecs(n+1, vecs, A+[b])
        return None
        
    makevecs(1, vecs, [1])
    ans = 0
    for vec in vecs:
        ans_ = 0
        for q in range(Q):
            a, b, c, d = abcd[q]
            if vec[b-1] - vec[a-1] == c:
                ans_ += d
        
        ans = max(ans, ans_)

    print(ans)

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

N = int(input())
S = list(input())

def check(red, blue): #赤色、青色がわかるリストが与えられる。
    max_n = len(blue) #青色の個数 = 赤色の後ろにつける個数
    max_r = len(red)
    dp = [[[-1] * (max_n + 1) for _ in range(max_r + 1)] for _ in range(N + 1)]
    
    def calc(red, blue, i, tmp, n):
        if i == N - 1:
            return 1

        if dp[i - N][tmp][n] != -1:
            return dp[i - N][tmp][n]

        tmp_count = 0
        if n < max_n and S[i] == S[blue[n]]:
            tmp_count += calc(red, blue, i - 1, tmp, n + 1)
        if tmp < max_r and S[i] == S[red[tmp]]:
            tmp_count += calc(red, blue, i - 1, tmp + 1, n)
        
        dp[i - N][tmp][n] = tmp_count
        return tmp_count

    return calc(red, blue, 2 * N - 1, 0, 0)
    # for i in range(2 * N - 1, N - 1, -1): #後半部分を後ろから探索
    #     # print (i, n - 1, blue[n - 1])
    #     if n < max_n and S[i] == S[blue[n]]: #青色と一致しているとき
    #         n += 1
    #     else:
    #         if tmp < len(red) and S[i] == S[red[tmp]]:
    #             tmp += 1
    #         else:
    #             return False
    # return True


count = 0
for i in range(2 ** N):
    red = []
    blue = []
    lst = [0] * N #0: 赤色、1: 青色
    for j in range(N):
        if (i >> j) & 1:
            red.append(j)
            lst[j] = 1
        else:
            blue.append(j)
    
    # print (check(red, blue), red, blue)
    count += check(red, blue)

print (count)

### FIXED CODE ###

from collections import defaultdict

N = int(input())
S = str(input())

dic = defaultdict(int)

for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j + N]
        else:
            b += S[j + N]
    
    dic[(a, b)] += 1

count = 0
for i in range(2 ** N):
    a = str()
    b = str()
    for j in range(N):
        if (i >> j) & 1:
            a += S[j]
        else:
            b += S[j]
    count += dic[b[::-1], a[::-1]]

print (count)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    q = deque()
    q.append((0, 0))
    while q:
        p, i = q.popleft()
        ai = a[i]
        for j in range(n):
            if ai[j]:
                j1 = 1 << j
                if p & j1:
                    continue
                pj1 = p | j1
                if pj1 != n1 - 1: q.append((pj1, i + 1))
                dp[pj1] += dp[p]
                if dp[pj1] >= mod:
                    dp[pj1] %= mod

    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n = II()
    a = LIR(n)
    n1 = 1 << n
    dp = [0] * n1
    dp[0] = 1
    b = [0]
    for i in range(n):
        b += [x + 1 for x in b]
    # print(b)
    c = [1 << i for i in range(n)]
    for i in range(n1-1):
        p = b[i]
        ap = a[p]
        for j in range(n):
            if ap[j]:
                j1 = c[j]
                if i & j1:
                    continue
                dp[i|j1] += dp[i]


    print(dp[-1] % mod)


    return


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

#!/usr/bin/env python3
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
import sys


def solve(A: int, B: int, N: int):
    def f(x: int) -> int:
        return int(A*x/B) - A*int(x/B)
    print(max(map(f, range(min(B, N)+1))))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
import sys


def solve(A: int, B: int, N: int):
    def f(x: int) -> int:
        return int(A*x/B) - A*int(x/B)
    print(f(min(B-1, N)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(A, B, N)


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

n=int(input())
s=list(input())
x=[]
y=[]
z=[]
count=0
count1=0

for i in range(n-2):
    y=[]
    count1+=count
    count=0
    if x.count(s[i])!=0:
        continue
    else:
        x.append(s[i])
        for j in range(i+1,n-1):
                for k in range(j+1,n):
                    v=s[j]+s[k]
                    if y.count(v)!=0:
                        continue
                    else:
                        y.append(v)
                        count+=1
                        if count==100:
                            count1+=100
                            count=0
                            break
                            
                        
                
        
    
print(count+count1)


### FIXED CODE ###

n=int(input())
s=list(input())
count=0

for i in range(1000):
    if len(str(i))==1:
        i=str(0)+str(0)+str(i)
    elif len(str(i))==2:
        i=str(0)+str(i)
    else:
        i=str(i)
    x=0
    for j in range(n):
        if s[j]==i[x]:
            x+=1
            if x==3:
                count+=1
                break
print(count)
### BUGGY CODE ###

import heapq
def dijkstra_heap(N,S,edge):
  S = min(S,5000)
  d = [[float('inf')]*5001 for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*5001 for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0 and S+sil<=5000:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=5000 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  for i in range(M):
    u,v,a,b = map(int, input().split())
    edge[u-1].append([b,v-1,-a])
    edge[v-1].append([b,u-1,-a])
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')


### FIXED CODE ###

import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')
### BUGGY CODE ###

s=input()
i,b=0,0
while i<len(s):
  if (((s[i]=='R') & (i%2==0))|((s[i]=='L') & (i%2==1))):
    b=1
if(b):
  print('NO')
else:
  print('YES')
  

### FIXED CODE ###

s=input()
i,b=0,0
while i<len(s):
	if (((s[i]=='R') & (i%2==1))|((s[i]=='L') & (i%2==0))):
		b=1
		break
	i+=1
if(b):
	print('No')
else:
	print('Yes')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break
  # print(node,res+1)
  return res + 1 , i
print((dfs(0)[0]-1)%mod)
# print(visited)
# print(XD)
# dfs(1)

### FIXED CODE ###

#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 998244353
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)

n = int(input())
XD = [(-10**10,inf)]
for i in range(n):
  x,d = map(int,input().split())
  XD.append((x,d))
XD.sort()
visited = [0] * (n+1)
def dfs(node):
  visited[node] = 1
  res = 1
  i = node + 1
  while i < n+1:
    if XD[i][0] < XD[node][0] + XD[node][1]:
      if visited[i]:continue
      pro,i = dfs(i)
      res *= pro
      res %= mod
    else: break
  # print(node,res+1)
  return res + 1 , i
print((dfs(0)[0]-1)%mod)
# print(visited)
# print(XD)
# dfs(1)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

l = p[0:k]
l_sum = [sum(l)]
for i in range(k, n):
    l.pop(0)
    l.append(p[i])
    l_sum.append(sum(l))
ans = (max(l_sum)+k)/2
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

p = list(map(lambda x: (1+x)/2, p))
s = [0]
num = 0
for i in range(n):
  num += p[i]
  s.append(num)
l = []
for i in range(n - k + 1):
  l.append(s[i+k]-s[i])

print(max(l))
### BUGGY CODE ###

N, K, Q = map(int, input().split())
val = [K]*N
a = []
for i in range(Q):
    num = [int(i) for i in range(N)]
    num.remove(int(input())-1)
    for j in num:
        val[j] -= 1

for i in val:
    if i <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

N, K, Q = map(int, input().split())
val = [K]*N
for i in range(Q):
    val[int(input())-1] += 1

for i in val:
    if i - Q <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[[] for _ in range(3)] for _ in range(N)]
for u,v in uv:
    for i in range(3):
        adj_list[u-1][i].append([v-1,(i+1)%3])


INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][0] = 0

stack = [[S,0,0]]
while stack:
    v,c,count = stack.pop()
    nxt_v = adj_list[v][c]
    for nv,nc in nxt_v:
        if dist[nv][nc]>(count+1)//3:
            dist[nv][nc] = (count+1)//3
            stack.append([nv,(c+1)%3,count+1])
            
            
if dist[T][0]==INF:
    ans = -1
else:
    ans = dist[T][0]
print(ans)
            
        
        
        
    





### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from queue import Queue
# 12:55~
sys.setrecursionlimit(10**9)

N,M = map(int,input().split())
uv = [list(map(int,input().split())) for _ in range(M)]
S,T = map(int,input().split())

S -= 1
T -= 1
#%%
adj_list = [[[] for _ in range(3)] for _ in range(N)]
for u,v in uv:
    for i in range(3):
        adj_list[u-1][i].append([v-1,(i+1)%3])


INF = 10**9+7
dist = [[INF]*3 for _ in range(N)]
dist[S][0] = 0

stack = Queue()
stack.put([S,0])
while not stack.empty():
    v,c = stack.get()
    nxt_v = adj_list[v][c]
    for nv,nc in nxt_v:
        if dist[nv][nc]==INF:
            dist[nv][nc] = dist[v][c] + 1
            stack.put([nv,nc])
            
            
if dist[T][0]==INF:
    ans = -1
else:
    ans = dist[T][0]//3
print(ans)
### BUGGY CODE ###

from collections import defaultdict
def d():
    tree_map = defaultdict(list)
    value_map = defaultdict(int)
    N, Q = map(int,input().split())
    
    for _ in range(1, N):
        a, b = map(int,input().split())
        tree_map[a].append(b)
        tree_map[b].append(a)

    for _ in range(1, Q+1):
        p, x = map(int,input().split())
        value_map[p] += x

    res = [0] * N
    stack = []
    stack.append((1, -1, 0))

    while stack:
        i, p, s = stack.pop()
        if value_map[i] != 0:
            s += value_map[i]
        res[i-1] += s
        
        for j in tree_map[i]:
            if j == p:
                continue
            else:
                stack.append((j, i, s))

    print(*res)


if __name__ == "__main__":
    d()

### FIXED CODE ###

from collections import defaultdict
def d():
    tree_map = defaultdict(list)
    value_map = defaultdict(int)
    N, Q = map(int,input().split())
    
    for _ in range(1, N):
        a, b = map(int,input().split())
        tree_map[a].append(b)
        tree_map[b].append(a)

    res = [0] * N

    for _ in range(1, Q+1):
        p, x = map(int,input().split())
        res[p-1] += x
    
    stack = []
    stack.append((1, -1, 0))

    while stack:
        i, p, s = stack.pop()

        res[i-1] += s
        s = res[i-1]
        
        for j in tree_map[i]:
            if j == p:
                continue
            else:
                stack.append((j, i, s))

    print(*res)


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

# coding: utf-8
# Your code here!

N, M = map(int,input().split())
li = [list(map(int,input().split())) for i in range(M)]
L = [li[j][0] for j in range(M)]
R = [li[k][1] for k in range(M)]
ctr = 0

for i in range(1, N + 1):
    if i >= max(L) and i <= min(R):
        ctr += 1
print(ctr)

### FIXED CODE ###

# coding: utf-8
# Your code here!

N, M = map(int,input().split())
li = [list(map(int,input().split())) for i in range(M)]
L = [li[j][0] for j in range(M)]
R = [li[k][1] for k in range(M)]
ctr = 0

if min(R) - max(L) >= 0:
    print(min(R) - max(L) + 1)
else:
    print(0)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))

c = N // 2
x = sorted(X)
for v in X:
	if x.index(v) < c:
		print(x[c])
	else:
		print(x[c - 1])


### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))

c = N // 2
x = sorted(X)
for v in X:
	if v < x[c]:
		print(x[c])
	else:
		print(x[c - 1])
### BUGGY CODE ###

N = int(input())


def f(x):
    i = 1
    count = 0
    while i ** 2 < x:
        if x % i == 0: count += 2
        i += 1
    if i ** 2 == x: count += 1
    return count


dp = [0] * N
for i in range(1, N):
    dp[i] = dp[i - 1] + f(i)

print(dp[N - 1])



### FIXED CODE ###

N = int(input())

ans = 0
for i in range(1,N):
	ans += (N-1)//i
print(ans)
### BUGGY CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
heapq.heapify(A)

for i in range(M):
    b, c = map(int, input().split())

    count = 1
    while count <= b:
        top = A[0]
        if top <= c:
            heapq.heappop(A)
            heapq.heappush(A, c)
            count += 1
        else:
            break

ans = sum(A)
print(ans)


### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [(A[i], 1) for i in range(N)]

changes = [None] * M
for i in range(M):
    b, c = map(int, input().split())
    changes[i] = (c, b)

allVals = A + changes

allVals.sort(key = lambda x:x[0], reverse = True)
# print(allVals)

i = 0
j = -1
res = 0
while True:
    j += 1
    res += allVals[j][0] * allVals[j][1]
    i += allVals[j][1]

    if i >= N:
        res -= allVals[j][0] * (i - N)
        break



print(res)