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

import copy as cp
n,k = map(int,input().split())
lamps = list(map(int,input().split()))
for j in range(min(k,41)):
    lamp_io = [0]*n
    for i in range(len(lamps)):
        if(i == 0):
            for k in range(1,lamps[i]+1):
                if(i+k <= n-1):
                    lamp_io[k] += 1
                else:
                    break
            lamp_io[i] += 1
        elif(i == n-1):
            for k in range(1,lamps[i]+1):
                if(i-k >= 0):
                    lamp_io[i-k] += 1
                else:
                    break
            lamp_io[i] += 1
        else:
            for k in range(1,lamps[i]+1):
                a = 0
                b = 0
                if(i+k <= n-1):
                    lamp_io[i+k] += 1
                else:
                    a = 1
                if(i-k >= 0):
                    lamp_io[i-k] += 1
                else:
                    b = 1
                if(a == 1 and b == 1):
                    break
            lamp_io[i] += 1
        # print(lamp_io)    
    lamps = cp.copy(lamp_io)
ans = ""
for i in range(len(lamp_io)):
    ans += str(lamp_io[i]) +" "
print(ans.rstrip())

### FIXED CODE ###

from numba import jit
@jit
def main():
    n,k = map(int,input().split())
    lamps = list(map(int,input().split()))
    for ki in range(k):
        lamplog = [0]*(n+1)
        for i in range(n):
            lamplog[max(0,i-lamps[i])  ] += 1   #先端を出す
            lamplog[min(i+lamps[i]+1,n)] -= 1   #末尾を出す
        # print(lamplog)
        for i in range(n):                      #累積和を計算
            lamplog[i+1] += lamplog[i]
        # print(lamplog)
        lamplog.pop()
        if(lamplog == lamps):                   #１つ前の結果と今回の結果が同じだったら。
            break
        lamps = lamplog                         #今回の結果を記録
    return lamplog

lamplog = main()
ans = ""
for i in range(len(lamplog)):
    ans += str(lamplog[i]) +" "
print(ans.rstrip())
### BUGGY CODE ###

s = input()
reverse_count = 0
while "BW" in s:
    reverse_count += s.count("BW")
    s = s.replace("BW", "WB")
print(reverse_count)


### FIXED CODE ###

s = list(input())
W_count = 0
ans = 0
for i in range(len(s)):
    if s[i] == "W":
        ans += i - W_count
        W_count += 1
print(ans)
### BUGGY CODE ###

import numpy as np

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

dp = np.zeros((n+1, n+1), dtype=np.int64)
ans = 0

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]: dp[i][j] = dp[i+1][j+1] + 1
        ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)


### FIXED CODE ###

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

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

for i in range(n-1, -1, -1):
    for j in range(i, -1, -1):
        if s[i] == s[j]:
             dp[i][j] = dp[i+1][j+1] + 1
             ans = max(ans, min(i-j, dp[i][j]))
        
print(ans)
### BUGGY CODE ###

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]+1):
    answerList.append(0)

for i in range(N[0]):
    for j in range(N[0] + 1):
        if j > i > 0:
            calculateList = [abs(j - i),
                             abs(N[1] - i) + 1 + abs(j - N[2]),
                             abs(N[2] - i) + 1 + abs(j - N[1])]
            answerList[min(calculateList)] = answerList[min(calculateList)] + 1

for i in range(N[0] - 1):
    print(answerList[i+1])

### FIXED CODE ###

N = [int(i) for i in input().split()]

answerList = []

for i in range(N[0]):
    answerList.append(0)

for i in range(N[0]):
    if i > 0:
        for j in range(N[0]):
            if j + 1 > i > 0:
                calculateList = [abs(j + 1 - i),
                                 abs(N[1] - i) + 1 + abs(j + 1 - N[2]),
                                 abs(N[2] - i) + 1 + abs(j + 1 - N[1])]
                answer = min(calculateList)
                answerList[answer] = answerList[answer] + 1

for i in range(N[0] - 1):
    print(answerList[i + 1])
### BUGGY CODE ###

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)
for a, b in AB:
    uf.union(a - 1, b - 1)

max_ = 0
for key, val in uf.all_group_members().items():
    max_ = max(max_, len(val))

print(max_)


### FIXED CODE ###

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


class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


uf = UnionFind(N)
for a, b in AB:
    uf.union(a - 1, b - 1)

max_ = 0
roots = uf.roots()

for r in roots:
    max_ = max(max_, uf.size(r))

print(max_)
### BUGGY CODE ###

N = int(input())
list_A = []

for _ in range(N):
    A = int(input())
    list_A.append(A)
    
for i in range(N):
    original = list_A[i]
    list_A[i] = 0
    print(max(list_A))
    list_A[i] = original

### FIXED CODE ###

N = int(input())
list_A = []

for _ in range(N):
    A = int(input())
    list_A.append(A)
    
A = max(list_A)
index_A = list_A.index(A)

list_B = sorted(list_A, reverse=True)
B = list_B[1]

for i in range(N):    
    if list_A[i] == A:
        print(B)
    else:
        print(A)
### BUGGY CODE ###

import numpy as np
n = int(input())
s = list(input() for i in range(n))
s = np.array(s)
i = 0
while 0 < (len(s)):
    s = s[s != s[0]] 
    i += 1
print(i)




### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    s = input()
    if not(s in d): d[s] = 1

print(len(d))
### BUGGY CODE ###

import heapq
S = input()
cum = []
heapq.heapify(cum)
for i in range(len(S)-1, -1, -1):
    n = int(S)
    n = n % 10**(i+1)
    heapq.heappush(cum, n % 2019)

prev = cum[0]
ans = 0
cnt = 0
for i in range(len(cum)):
    c = heapq.heappop(cum)
    if c != prev:
        if prev == 0:
            ans += cnt
        ans += cnt * (cnt-1) // 2
        cnt = 1
    else:
        cnt += 1
    prev = c

if cnt > 1:
    if prev == 0:
        ans += cnt
    ans += cnt * (cnt-1) // 2
    cnt = 1

print(ans)

### FIXED CODE ###

import sys
import math
from collections import deque
from collections import Counter

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

#nCr
def cmb(n, r):
    return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


def main():
    S = SI()
    l = len(S)
    T = [0] * (l+1)
    inv_S = S[::-1]
    for i, s in enumerate(inv_S):
        s = int(s)
        T[i+1] = (T[i] + s * pow(10, i, 2019)) % 2019
    C = Counter(Counter(T).values())
    ans = 0
    for n, x in C.items():
        if n == 1: continue
        ans += cmb(n, 2) * x
    print(ans)


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

from sys import stdin


def get_result(data):
    S, Q = data[0][0], int(data[1][0])
    for i in range(Q):
        if data[i+2][0] == '1':
            S = S[::-1]
        else:
            F, C = data[i+2][1], data[i+2][2]
            if F == '1':
                S = C + S
            else:
                S = S + C

    return S


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)


### FIXED CODE ###

from sys import stdin
from collections import deque

# not AC
# def get_result(data):
#     S, Q = data[0][0], int(data[1][0])
#     for i in range(Q):
#         if data[i+2][0] == '1':
#             S = S[::-1]
#         else:
#             F, C = data[i+2][1], data[i+2][2]
#             if F == '1':
#                 S = C + S
#             else:
#                 S = S + C
#     return S


def get_result(data):
    S, Q = data[0][0], int(data[1][0])
    # 文字列と反転状況を別で判断する
    ans = deque(S)
    cnt = 0
    for i in range(Q):
        if data[i+2][0] == '1':
            cnt += 1
        else:
            F, C = data[i+2][1], data[i+2][2]
            if F == '1':
                if cnt % 2 == 0:
                    ans.appendleft(C)
                else:
                    ans.append(C)
            else:
                if cnt % 2 == 0:
                    ans.append(C)
                else:
                    ans.appendleft(C)

    if cnt % 2 == 1:
        ans = ''.join(reversed(ans))
    else:
        ans = ''.join(ans)

    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip('\n') for val in stdin.readlines()]
    data = [list(map(str, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
m = str(max(A))
ANS = []

for i in range(n):
    if i == A.index(max(A)):
        ans = A[:]
        ans.pop(i)
        ANS.append(str(max(ans)))
    else:
        ANS.append(m)

print('\n'.join(ANS))

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
B = A[:]
B.sort()

a_max = B[len(B)-1]
a_next = B[len(B)-2]

for i in range(n):
    if A[i] != a_max:
        print(a_max)
    else:
        print(a_next)
### BUGGY CODE ###

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

S = input()
N = len(S)
"""
L4 = []
L5 = []
L6 = []
L7 = []
L8 = []
for i in range(10000):
    t = len(str(i*2019))
    if t == 4:
        L4.append(i*2019)
    if t == 5:
        L5.append(i*2019)
    if t == 6:
        L6.append(i*2019)
    if t == 7:
        L7.append(i*2019)
    if t == 8:
        L8.append(i*2019)
#print(len(L4),len(L5),len(L6),len(L7))

"""
counter = 0

for i in range(N-3):
    #j = 4
    #while (j < N+1-i):
    M = min(9,N+1-i)
    for j in range(4,M):
        if int(S[i:i+j]) % 2019 == 0:
            counter += 1
            for k in range(j+1,N+1-i):
                if int(S[i:i+k]) % 2019 == 0:
                    counter += 1
print(counter)


### FIXED CODE ###

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

surplus = [0]*2019
surplus[0] += 1

d = 1
n = 0
for i in reversed(input()):
    n = (n + int(i)*d) %2019
    d = d*10 % 2019
    surplus[n] += 1

print(sum([i*(i-1)//2 for i in surplus]))
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    b = [0]*n
    f = True
    ans = 0
    for i in reversed(range(n)):
        if i < a[i] or a[i] < b[i]:
            f = False
            break
        if b[i] < a[i]:
            for j in range(i-a[i], i):
                ans += 1
                b[j+1] = b[j]+1
    if f:
        print(ans)
    else:
        print(-1)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(input()) for _ in range(n)]
    f = True
    ans = 0
    L = n-1
    for i in reversed(range(n)):
        if i < a[i] or a[i] < i-L:
            f = False
            break
        if i-L < a[i]:
            ans += a[i]
            L = i - a[i]
    if f:
        print(ans)
    else:
        print(-1)

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

N,M = map(int, input().split())
ans = 0
while not (N == 0 and M == 0):
 for i in range(1, N+1):
  for j in range(i, N+1):
   k = M - i - j
   if ( i==j or i==k or j==k): pass
   elif (i + j + k == M): ans += 1
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
ans = 0
while not (N == 0 and M == 0):
 for i in range(1, N+1):
  for j in range(i+1, N+1):
   k = M - i - j
   if ( k > N): pass
   elif  k <= j : break
   else: ans += 1
 print(ans)
 ans = 0
 N,M = map(int, input().split())
### BUGGY CODE ###

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

if M == 1:
    l1, r1 = map(int, input().split())
    print(r1 - l1 + 1)
else:
    C = 0
    
    l1, r1 = map(int, input().split())
    for _ in range(M - 1):
        l2, r2 = map(int, input().split())

        A = list(range(l1, r1 + 1))
        B = list(range(l2, r2 + 1))

        C = set(A) & set(B)
    print(len(C))

### FIXED CODE ###

N, M = map(int, input().split())
left= []
right = []
for _ in range(M):
    L, R = map(int, input().split())
    left.append(L)
    right.append(R)

min_right = min(right)
max_left = max(left)
if min_right < max_left:
    print(0)
else:
    print(min_right - max_left + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, y):
    global N, Z, W
    X = Z if x == 0 else A[x - 1]
    Y = W if y == 0 else A[y - 1]

    if memo[x][y] >= 0:
        return memo[x][y]
    else:
        if x == N or y == N:
            rst = abs(X - Y)
        else:
            if x <= y:
                rst = 0
                for i in range(y + 1, N + 1):
                    rst = max(rst, dfs(i, y))
            else:
                rst = 10 ** 10
                for i in range(x + 1, N + 1):
                    rst = min(rst, dfs(x, i))
            return rst
        memo[x][y] = rst
        return rst


N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
memo = [[-1] * (N + 1) for _ in range(N + 1)]
ans = dfs(0, 0)
print(ans)


### FIXED CODE ###

N, Z, W = map(int, input().split())
A = list(map(int, input().split()))
dp = [[-1] * (N + 1) for _ in range(N + 1)]

for x in range(N, -1, -1):
    for y in range(N, -1, -1):
        if x == y:
            continue
        X = Z if x == 0 else A[x - 1]
        Y = W if y == 0 else A[y - 1]
        if x == N or y == N:
            rst = abs(X - Y)
        elif x - y == 1:
            rst = 10 ** 10
            for j in range(N, x, -1):
                rst = min(rst, dp[x][j])
        elif x - y > 1:
            rst = dp[x][y + 1]
        elif y - x == 1:
            rst = 0
            for i in range(N, y, -1):
                rst = max(rst, dp[i][y])
        elif y - x > 1:
            rst = dp[x + 1][y]
        else:
            raise Exception
        dp[x][y] = rst

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

taka, aoki, times= map(int,input().split())


for i in range(times):
    if taka > 0:
        taka -= 1
    elif aoki > 0:
        aoki -= 1
    else:
        break

print(taka,aoki)

### FIXED CODE ###

taka, aoki, times= map(int,input().split())
if taka + aoki > times:
    if taka < times:
        print(0,aoki - (times - taka))
    elif taka > times:
        print(taka - times, aoki)
    else:
        print(0,aoki)
else:
    print(0,0)
### BUGGY CODE ###

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

works = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    heapq.heappush(works[A-1], -B)

total = 0
for i in range(1, M+1):
    max_m = 0
    for j in range(i):
        if len(works[j]) == 0:
            continue
        else:
            x = heapq.heappop(works[j])
            if -x > max_m:
                max_m = -x
            else:
                heapq.heappush(works[j], x)

    total += max_m

print(total)

### FIXED CODE ###

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

jobs = [[] for _ in range(M)]
for _ in range(N):
    A, B = map(int, input().split())
    if A > M:
        continue
    jobs[A-1].append(-B)

total = 0
heap = []
for i in range(M):
    for job in jobs[i]:
        heapq.heappush(heap, job)

    if len(heap) == 0:
        continue
    else:
        total += -heapq.heappop(heap)

print(total)
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    N = 80 * (H+W) // 2
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(0)
    def ltN(x): return x <= N
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            dp[(i+1) & 1][j+1] |= set(filter(ltN, [abs(x + diff)
                                                   for x in dp[i & 1][j+1]]))
            dp[(i+1) & 1][j+1] |= set(filter(ltN, [abs(x - diff)
                                                   for x in dp[i & 1][j+1]]))
            dp[(i+1) & 1][j+1] |= set(filter(ltN, [abs(x + diff)
                                                   for x in dp[(i+1) & 1][j]]))
            dp[(i+1) & 1][j+1] |= set(filter(ltN, [abs(x - diff)
                                                   for x in dp[(i+1) & 1][j]]))
    print(min(dp[H & 1][W]))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    H, W = map(int, input().split())
    N = 80 * (H+W) // 2
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [list(map(int, input().split())) for _ in range(H)]
    dp = [[set() for _ in range(W+1)] for _ in range(2)]
    dp[0][1].add(0)
    def ltN(x): return x <= N
    for i in range(H):
        dp[(i+1) & 1] = [set() for _ in range(W+1)]
        for j in range(W):
            diff = abs(A[i][j] - B[i][j])
            tmp = set()
            for x in dp[i & 1][j + 1]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            for x in dp[(i+1) & 1][j]:
                tmp.add(abs(x + diff))
                tmp.add(abs(x - diff))
            dp[(i+1) & 1][j+1] = tmp
    print(min(dp[H & 1][W]))


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

N = int(input())

point = []
dist = []
maxDist = 0

for _ in range(N) :
    x, y = map(int, input().split())
    d = abs(x) + abs(y)
    maxDist = max(maxDist, d)
    point.append((x, y, d))
    dist.append(d)

mask = maxDist % 2

for d in dist :
    if d % 2 != mask :  # 実現不可能
        print('-1')
        break
else :  # 実現可能
    print(maxDist) # 腕の数
    for _ in range(maxDist) :
        print('1 ', end='')

    for x, y, d in point :
        if x < 0 :
            for _ in range(-x) :
                print('L', end='')
        elif x > 0 :
            for _ in range(x) :
                print('R', end='')

        if y < 0 :
            for _ in range(-y) :
                print('D', end='')
        elif y > 0 :
            for _ in range(y) :
                print('U', end='')

        R = (maxDist - d) // 2
        if R > 0 :
            for _ in range(R) :
                print('LR', end='')

        print('')


### FIXED CODE ###

N=int(input())

point = []
parity = {}
for _ in range(N) :
    x, y = map(int, input().split())
    point.append((x, y))
    parity[(x + y) % 2] = 1

if len(set(parity)) == 2 :
    print('-1')
else :
    m = 38
    parity = 1 if (1 in parity) else 0
    print(m + 1 - parity)
    if parity == 1 :  # 距離が奇数
        print(*[1 << i for i in range(m)])
    else :
        print(1, *[1 << i for i in range(m)])

    def arm(x, y, m) :
        if abs(x) >= abs(y) :
            if x >= 0 :
                return ('R', x - (1<<m), y)
            else :
                return ('L', x + (1<<m), y)
        else :
            if y >= 0 :
                return ('U', x, y - (1<<m))
            else :
                return ('D', x, y + (1<<m))

    for x, y in point :
        ans = []
        for i in range(m-1, -1, -1) :
            mode, x, y = arm(x, y, i)
            ans.append(mode)
        if parity == 0 :  # 偶数の場合一つ足す
            if x == 1 :
                ans.append('R')
            elif x == -1 :
                ans.append('L')
            elif y == 1 :
                ans.append('U')
            elif y == -1 :
                ans.append('D')
        print(''.join(ans[::-1]))
### BUGGY CODE ###

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

Answer = [p+1 for p in range(n)]

for i in range(m):
  l,r = map(int, input().split())
  Answer = [q for q in Answer if q >=l]
  Answer = [s for s in Answer if s <=r]
  
print(len(Answer)) 

### FIXED CODE ###

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

min_value = 1
max_value = n

for _ in range(m):
  l, r = map(int, input().split())
  if l >= min_value:
    min_value = l
  if r <= max_value:
    max_value = r

Answer = max(max_value - min_value +1,0)

print(Answer)
### BUGGY CODE ###

def solve():
    MOD = 10**9 + 7

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

    num1s = [0] * 60
    for A in As:
        for d in range(60):
            if (A>>d) & 1:
                num1s[d] += 1

    ans = 0
    for d in range(60):
        ans += num1s[d] * (N-num1s[d]) * pow(2, d, MOD)
        ans %= MOD

    print(ans)


solve()


### FIXED CODE ###

MOD = 10**9 + 7

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

ans = 0
for d in range(60):
    sumXOR = 0
    num0, num1 = 0, 0
    for A in As:
        if (A>>(59-d))&1:
            num1 += 1
        else:
            num0 += 1
#    print('d:', d, '/ num0:', num0, '/ num1:', num1)
    sumXOR += (num0 * num1) % MOD
    sumXOR %= MOD
    ans *= 2
    ans += sumXOR
    ans %= MOD

print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0,N-2) :
    for j in range(i+1,N-1) :
        for k in range(j+1,N) :
            if j - i != k -j :
                if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]) :
                    ans += 1

print(ans) 

### FIXED CODE ###

N = int(input())
S = input()
r = S.count("R")
g = S.count("G")
b = S.count("B")
ans = r*g*b
for i in range(0,N-2) :
    for j in range(i+1,N-1) :
        k = j + (j - i)
        if k < N :
            if (S[i] != S[j]) and (S[i] != S[k]) and (S[j] != S[k]) :
                ans -= 1
print(ans)
### BUGGY CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)


### FIXED CODE ###

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N = int(input())
A = [int(x) for x in input().split()]
a = 1
MOD = 10**9+7
for i in A:
  a = lcm(a,i)
ans = 0
for i in A:
  ans += (a//i)
print(ans%MOD)
### BUGGY CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    intersects = set()
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            intersects = set(range(o[0], o[1]+1))
        else:
            intersects = intersects & set(range(o[0], o[1]+1))
            if len(intersects) == 0:
                break

    print(len(intersects))


if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (n, m) = list(map(int, input().split(" ")))
    
    for i in range(m):
        o = list(map(int, input().split(" ")))
        if i == 0:
            lmax = o[0]
            rmin = o[1]
        else:
            lmax = max(lmax, o[0])
            rmin = min(rmin, o[1])

    print(rmin-lmax+1 if lmax <= rmin else 0)


if '__main__' == __name__:
    resolve()