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

import sys


def my_input(): return sys.stdin.readline().rstrip()


def main():

    N = int(input())
    S = tuple(input())

    ans = 0
    for i in range(1000):
        d1 = (i // 100) % 10
        d2 = (i // 10) % 10
        d3 = i % 10
        d1_flag = True
        d2_flag = True

        for i in range(N):

            now = int(S[i])
            if d1_flag:
                if d1 == now:
                    d1_flag = False
                continue

            if d2_flag:
                if d2 == now:
                    d2_flag = False
                continue

            if d3 == now:
                ans += 1
                break

    print(ans)


if __name__ == '__main__':

    main()


### FIXED CODE ###

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

ans = 0


for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = 0
            flag2 = 0
            
            for l in range(n):
                if flag1 == 0 and s[l] == str(i):
                    flag1 = 1
                    continue
                
                if flag1 == 1 and flag2 == 0 and s[l] == str(j):
                    flag2 = 1
                    continue
                
                if flag1 == 1 and flag2 == 1 and s[l] == str(k):
                    ans += 1
                    break
                
print(ans)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
all_rain = sum(l)
ans = []

for i in range(n):
    now = (i+2)%n
    others = 0
    while now%n != (i+1)%n:
        others += l[(now-1)%n]
        now = (now+2)%n
    ans.append(str(all_rain-others*2))

print(" ".join(ans))

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = []

cnt =1
rain_others = 0
while cnt != n:
    rain_others += l[cnt] * 2
    cnt += 2
ans.append(sum(l)-rain_others)

for i in range(1, n):
    ans.append(l[i-1]*2-ans[i-1])

print(" ".join(list(map(str, ans))))
### BUGGY CODE ###

s = input()

n = len(s)
ans = 0
flag = 0
for i in range(n):
    flag = 0
    for j in range(i+1,n):
        if flag != 0:
            flag -= 1
            continue
        if int(s[i:j+1]) % 2019 == 0:
            ans += 1
            flag = 3
print(ans)

### FIXED CODE ###

s = input()
#s = '9' * 200000

mod = [1] + [0]*2018
t = 0
a = 1
n = len(s)
s = s[::-1]
for i in range(n):
    t = (t + int(s[i])*a) % 2019
    a = a * 10 % 2019
    mod[t] += 1
ans = 0
for i in range(2019):
    ans += mod[i]*(mod[i]-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
count = 0
for A in range(1,N):
    for B in range(1,N):
        for C in range(1,N):
            if N == A*B+C:
                count += 1
print(count)

### FIXED CODE ###

N = int(input())
NR = int(N**0.5)
count = 0
if int(N/2)-N/2 == 0:
    for i in range(1,int(N/2)):
        if int(N/i)-N/i == 0:
            count += int(N/i)-1
        else:
            count += int(N/i)
else:
    for i in range(1,int(N/2)+1):
        if int(N/i)-N/i == 0:
            count += int(N/i)-1
        else:
            count += int(N/i)

count += int(N/2)
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict, deque
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
Q = [inpl() for _ in range(M)]
 
tree = [[-1, 1]  for _ in range(N+1)] # [next, rank]
  
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
adj = [[] for _ in range(N+1)]  
 
for l, r, d in Q:
    if find(l) != find(r):
        unite(l, r)
    adj[l].append([r, d])
    adj[r].append([l, -d])
 
 
G = set([find(n) for n in range(1, N+1)])
 
X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
res = True
 
for g in G:
    X[g] = 0
    Q = deque([g])
    searched[g] = True
    while Q:
        p = Q.popleft()
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
                searched[np] = True
    if not res:
        break
 
if res:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict, deque
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
Q = [inpl() for _ in range(M)]
# グループごとにトポロジカルソートをして、最後の方から遡って計算
 
tree = [[-1, 1]  for _ in range(N+1)] # [next, rank]
  
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
 
adj = [[] for _ in range(N+1)]  
 
for l, r, d in Q:
    if find(l) != find(r):
        unite(l, r)
    adj[l].append([r, d])
    adj[r].append([l, -d])
 
 
G = set([find(n) for n in range(1, N+1)])
 
X = [-1 for _ in range(N+1)]
searched = [False for _ in range(N+1)]
res = True
 
for g in G:
    X[g] = 0
    Q = deque([g])
    searched[g] = True
    while Q:
        p = Q.popleft()
        for np, d in adj[p]:
            if searched[np]:
                if X[np] != X[p] + d:
                    Q = []
                    res = False
                    break
            else:
                X[np] = X[p] + d
                Q.append(np)
                searched[np] = True
    if not res:
        break
 
if res:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from heapq import heappush, heappop

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

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

for i in range(n):
    x, pi = heappop(hq)
    for l in range(i+1):
        r = i-l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*A[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop

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

MX = 2005
f_inf = float('inf')
dp = [[0 for _ in range(MX)] for _ in range(MX)]
dp[0][0] = 0

hq = []
for i in range(n):
    heappush(hq, (-A[i], i))

ans = 0
for i in range(n):
    x, pi = heappop(hq)
    for l in range(i+1):
        r = i-l
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + (pi-l)*A[pi])
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ((n-r-1)-pi)*A[pi])

ans = 0
for i in range(n+1):
    ans = max(ans, dp[n][i])
print(ans)
### BUGGY CODE ###

N,M = map(int, raw_input().split())
ab = [[0 for i in range(2)] for j in range(N)]
for i in range(N):
    ab[i][0], ab[i][1] = map(int, raw_input().split())
AB = sorted(ab, key=lambda x:x[0])
count = 0
total = 0
for i in range(N):
    for j in range(AB[i][1]):
        if count < M:
            total += AB[i][0]
            count += 1
        else:
            break
                                                                                                                    
print total


### FIXED CODE ###

N,M = map(int, raw_input().split())
ab = [[0 for i in range(2)] for j in range(N)]
for i in range(N):
    ab[i][0], ab[i][1] = map(int, raw_input().split())
AB = sorted(ab, key=lambda x:x[0])
count = 0
total = 0
for AB_ in AB:
    num = min(M, AB_[1])
    total += AB_[0]*num
    M -= num
print total
### BUGGY CODE ###

import re

def checkFunction(c):
    # print(c)
    c = re.sub('W+$','',c)
    c = re.sub('^R+','',c)
    if (not 'WR' in c):
        return 0
    if c.index('WR') + 2 != len(c):
        c2 = c.replace('WR', 'RR',1)[:-1]
        return checkFunction(c2) + 1
    return 1


N = int(input())
c= input()

print(checkFunction(c))


### FIXED CODE ###


def check(N, c):
    RinRight = c.count('R')
    WinLeft = 0
    r = RinRight
    for i in range(N):
        if c[i] == 'R':
            RinRight -= 1
        else: # c[i] == 'W'
            WinLeft +=1
        r = min(r, max(RinRight,WinLeft))

    return r


N = int(input())
c= input()
print(check(N,c))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
e1 = list(map(lambda x: (x+1)/2, P))

ans = 0
for i in range(N-K+1):
    a = sum(e1[i:i+K])
    ans = a if a > ans else ans
print(ans)


### FIXED CODE ###

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

ans = sum(P[0:K])
tmp = sum(P[0:K])

for i in range(1, N-K+1):
    tmp = tmp - P[i-1] + P[i+K-1]
    ans = max(tmp, ans)
print((ans + K)/2)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)

def find(LI,i,j,p):
    data=[(0,1),(0,-1),(1,0),(-1,0)]
    if not (0<=i<h and 0<=j<w):
        return -1
    if s[i][j]=="#":
        return -1
    if LI[i][j]!=-2:
        return LI[i][j]
    else:
        LI[i][j]= find(LI, i+data[p][0], j+data[p][1], p)+1
        return LI[i][j]
    

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
R=[[-2]*w for i in range(h)]
L=[[-2]*w for i in range(h)]
F=[[-2]*w for i in range(h)]
B=[[-2]*w for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        find(R,i,j,0)
        find(L,i,j,1)
        find(F,i,j,2)
        find(B,i,j,3)
        if s[i][j]!="#":
            ans = max(ans, sum((R[i][j], L[i][j], F[i][j], B[i][j]))+1)
print(ans)



### FIXED CODE ###

h,w=map(int,input().split())
data=[list(input()) for i in range(h)]
yoko=[[0]*w for i in range(h)]
for i in range(h):
	j=0
	while j <w:
		if data[i][j]=='#':
			j+=1
		else:
			start=j
			while j<w-1:
				j+=1
				if data[i][j]=='#':
					for k in range(start,j):
						yoko[i][k]=j-start-1
					j+=1
					break
			else:
				j+=1
				for k in range(start,j):
					yoko[i][k]=j-start-1
				j+=1
# for i in range(h):
# 	print(yoko[i])

for j in range(w):
	i=0
	while i <h:
		if data[i][j]=='#':
			i+=1
		else:
			start=i
			while i<h-1:
				i+=1
				if data[i][j]=='#':
					for k in range(start,i):
						yoko[k][j]+=i-start-1
					i+=1
					break
			else:
				i+=1
				for k in range(start,i):
					yoko[k][j]+=i-start-1
				i+=1

# print(yoko)
for i in range(h):
	# print(yoko[i])
	yoko[i]=max(yoko[i])
print(max(yoko)+1)
### BUGGY CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    X = 1
    for i in range(K):
        X *= A[i]
    B = [X]
    for i in range(K,N):
        tmp = B[-1] * A[i] // A[i-K]
        B.append(tmp)

    for i in range(N-K):
        if B[i+1]<=B[i]:
            print('No')
        else:
            print('Yes')



if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    for i in range(K,N):
        if A[i]<=A[i-K]:
            print('No')
        else:
            print('Yes')


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

n, k = map(int, input().split())
a = list(map(int, input().split()))
counter = 1
for i in range(k):
    counter *= a[i]
for i in range(k, n):
    after = counter / a[i-k] * a[i]
    if after > counter:
        print('Yes')
    else: 
        print('No')
    counter = after

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
for i in range(0, n-k):
    if a[i] >= a[i+k]:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

n=int(input())
ans=n
for i in range(n+1):
  t=i
  cnt=0
  while t:
    cnt+=t%6
    t//=6
  j=n-i
  while j:
    cnt+=t%9
    t//=9
  ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

n=int(input())
dp=list(range(n+1))
dp[0]=0
a=[]
b=[]
i=1
while True:
  if 6**i>n:break
  a.append(6**i)
  i+=1
i=1
while True:
  if 9**i>n:break
  b.append(9**i)
  i+=1
for i in a:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
for i in b:
  for j in range(i,n+1):
    dp[j]=min(dp[j],dp[j-i]+1)
print(dp[n])
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


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

for i in range(Q):
	p, x = list(map(int, input().split()))
	ope[p - 1] += x


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])





### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq


N, Q = list(map(int, input().split()))
eda = [[] for i in range(N)]
ope = [0]*N
score = [0]*N
parent = [-1]*N


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

for i in range(Q):
	p, x = list(map(int, input().split()))
	ope[p - 1] += x


que = []
que.append(0)
score[0] = ope[0]
for ss in range(N - 1):
	loc = que.pop()
	for edge in eda[loc]:
		if parent[loc] != edge:
			score[edge] += score[loc] + ope[edge]
			que.append(edge)
			parent[edge] = loc

for i in range(N - 1):
	print(score[i], end = "")
	print(" ", end = "")
print(score[N - 1])
### BUGGY CODE ###

a=int(input())
b=''
while a:
 b=str(a&1)+b
 a=-(a<<1)
print(b if b else 0)


### FIXED CODE ###

a=int(input())
b=''
while a:
 b=str(a&1)+b
 a=-(a>>1)
print(b if b else 0)
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, h, a):
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        dpi = dp[i]
        dpi1 = dp[i - 1]
        for j in range(1, n + 1):
            dpi[j] = dpi1[j]
            if h[i] <= j:
                dpij_ = dpi1[h[i] - 1] + a[i]
                if dpij_ > dpi[j]:
                    dpi[j] = dpij_
    return(dp[-1][-1])

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f(n, h, a))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

powof2 = lambda x: len("{:b}".format(x))

def f2(n, h, a):
    p = powof2(n)
    N = 2 ** p
    segt = [0] * (2 * N - 1)

    def getmax(a, b, i = 0, l = 0, r = N - 1):
        if r <= a or b <= l:
            return(0)
        if a <= l and r <= b:
            return(segt[i])
        i1 = 2 * i + 1
        i2 = i1 + 1
        lr = (l + r) // 2
        lmax = getmax(a, b, i1, l, lr)
        rmax = getmax(a, b, i2, lr, r)
        return(lmax if lmax > rmax else rmax)

    def setmax(i, v):
        si = i + N - 1
        segt[si] = v
        while si > 0:
            si = (si - 1) // 2
            si1 = 2 * si + 1
            si2 = si1 + 1
            segt[si] = segt[si1] if segt[si1] > segt[si2] else segt[si2]

    for i in range(1, n + 1):
        m = getmax(0, h[i])
        setmax(h[i], m + a[i])

    return(getmax(0, n))

n = int(input()) # 1 <= n <= 2 x 10^5
h = [0] + list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
print(f2(n, h, a))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
visited=[]
x=0
now=1
next_point=a[now-1]
for cnt in range(min(n,k)):
    now=next_point
    next_point=a[now-1]
    if now in visited:
        x=visited.index(now)
        break
    else:
        visited.append(now)
new_visited=visited[x:]
k-=len(visited)-len(new_visited)

#print(visited)
#print(new_visited)

print(new_visited[k%len(new_visited)-1])


### FIXED CODE ###

N,K=map(int,input().split())
A=[int(a)-1 for a in input().split()]
city=0
if K<=N:
    for k in range(K):
        city=A[city]
    print(city+1)
else:
    visited=[-1]*N
    for k in range(K):
        if visited[city]!=-1:
            roop_start=visited[city]
            cycle_num=k-roop_start
            break
        visited[city]=k
        city=A[city]
    K=(K-roop_start)%cycle_num+roop_start
    city=0
    for k in range(K):
        city=A[city]
    print(city+1)
### BUGGY CODE ###

import itertools
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				break
		B = B[:bi + 1]
		for i in range(1,len(B) + 1):
			C = list(itertools.combinations(B,i))
			for c in C:
				if sum(c) in fusoku:
					need.append(a)
					z = 1
					break
			if z == 1:
				break
		if z == 0:
			iranaiko.append(a)
print(N - len(need))

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
need = []
iranaiko = []
for a in A:
	if a >= K:
		need.append(a)
	elif a in need:
		need.append(a) 
	elif a in iranaiko:
		pass
	else:
		z = 0
		B = A[:]
		B.remove(a)
		fusoku = [K - i - 1 for i in range(a)]
		for bi,b in enumerate(B):
			if b >= K:
				bi = bi - 1
				break
		B = B[:bi + 1]
		B.reverse()
		C = [0]
		for b in B:
			D = []
			for c in C:
				if b + c < K:
					if b + c in fusoku:
						z = 1
						need.append(a)
						break
					D.append(b + c)
				
			D.append(0)
			C = D[:]
			if z == 1:
				break
			
		if z == 0:
			iranaiko.append(a)

print(N - len(need))
### BUGGY CODE ###

a,b=[int(x) for x in input().split()]
if a>b:
  a,b=b,a
tmp=0
for p in range(a,b+1):
  tmp^=p
print(tmp)


### FIXED CODE ###

a,b=[int(x)for x in input().split()]
if a>b :
  a,b=b,a
l=a%4
m=b%4
tmp=0
for p in range(a,a+4-l):
  tmp^=p
for p in range(b-m,b+1):
  tmp^=p
print(tmp)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
Q=int(input())
for i in range(Q):
    B,C=map(int,input().split())
    S=S+(C-B)*A.count(B)
    A = [C if i ==B  else i for i in A]
    print(S)


### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
D=collections.Counter(A)
Q=int(input())
for i in range(Q):
    B,C=map(int,input().split())
    S+=(C-B)*D[B]
    D[C]+=D[B]
    D[B]=0
    print(S)
### BUGGY CODE ###

# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)

### FIXED CODE ###

# N分木におけるxの親は、0-indexedのときに、(x - 1) // N
# 一度0-indexedに戻すため、最初に-1したうえで、(x - 1) // Nを繰り返す
# 初めて一致した点が(0-indexedにおける)答えなので、+1して答え

import sys
readline = sys.stdin.readline

N,Q = map(int,readline().split())

for i in range(Q):
  v,w = map(int,readline().split())
  if N == 1:
    print(min(v,w))
    continue
  v -= 1
  w -= 1
  while v != w:
    if v > w:
      v = (v - 1) // N
    else:
      w = (w - 1) // N
  print(v + 1)
### BUGGY CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def resolve():
    k = int(input())

    sum = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1,k+1):
                sum += gcd(gcd(a,b), c)
    
    print(sum)
    
resolve()

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def resolve():
    k = int(input())

    tmp = []
    for a in range(1, k+1):
        for b in range(1, k+1):
            tmp.append(gcd(a,b))

    ans = 0
    for c in range(1,k+1):
        for i in tmp:
            ans += gcd(i, c)
    
    print(ans)
    
resolve()
### BUGGY CODE ###

n, m = map(int, input().split())
x = range(1, n+1)

for i in range(m):
  l, r  = map(int, input().split())
  y = range(l, r+1)
  x = list(set(x) & set(y))

print(len(x))

### FIXED CODE ###

n, m = map(int, input().split())
ls = [0]*m
rs = [0]*m

for i in range(m):
  l, r  = map(int, input().split())
  ls[i] = l
  rs[i] = r

print(max(min(rs)-max(ls)+1,0))
### BUGGY CODE ###

import math
import collections
import fractions
import itertools
import functools
import operator

def solve():
    n = int(input())
    s = list(map(int, input()))
    allper = [(s[a], s[b], s[c]) for a, b, c in itertools.combinations(range(n), 3)]
    print(len(set(allper)))
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

n = [int(i) for i in input().split()]
s = input()
a = set([""])
ans = set()
for i in s:
    b = a.copy()
    for j in a:
        if len(j) == 2:
            ans.add(j + i)
        else:
            b.add(j + i)
    a = b
print(len(ans))
### BUGGY CODE ###

n, m = map(int, input().split())
k = []
for i in range(m):
    l, r = map(int, input().split())
    k.append(list(range(l, r + 1)))
c = [0] * n
for i in range(m):
    for j in range(n):
        if (j + 1) in k[i]:
            c[j] += 1
count = 0
for i in c:
    if m == i:
        count += 1
print(count)

### FIXED CODE ###

n, m = map(int, input().split())
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
count = min(R) - max(L) + 1
if count <= 0:
    print(0)
else:
    print(count)
### BUGGY CODE ###

N = int(input())
cnt = 0
number = 1

while number <= N:
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(1,N+1):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == number:
                    cnt += 1
                else:
                    continue
    print(cnt)
    cnt = 0
    number += 1


### FIXED CODE ###

N = int(input())
ans_list = [0 for _ in range(1,10100)]

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            value = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if value <= 10000:
                ans_list[value] += 1

for i in range(1, N+1):
    print(ans_list[i])
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
B.sort()
C.sort()

cnt = 0
a_left = 0
c_left = 0
for i in range(N):
    b = B[i]
    a_left += bisect_left(A[a_left:], b)
    c_left += bisect_right(C[c_left:], b)
    cnt += a_left * (N - c_left)
print(cnt)

### FIXED CODE ###

from bisect import bisect_left, bisect_right

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort()
C.sort()

cnt = 0
for b in B:
    cnt += bisect_left(A, b) * (N - bisect_right(C, b))
print(cnt)
### BUGGY CODE ###

def resolve():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**10] * n
    dp[0] = 0
    for i in range(1, n):
        for j in range(1, k+1):
            if i-j >= 0 :
                dp[i] = min(dp[i], dp[i-j]+abs(h[i]-h[i-j]))
    print(dp[-1])
resolve()

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int, input().split())) + [0]*K, dtype=np.int64)
H = np.array(h)
dp = np.full(N + K, 10 ** 10, dtype=np.int64)
dp[0] = 0
for i in range(1, N):
    dp[i:i + K] = np.minimum(dp[i:i + K],
                             np.abs(H[i:i + K] - H[i - 1]) + dp[i - 1])
print(dp[N - 1])