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

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    last_hs = hs[-1]
    for i in range(1,k+1):
        ans_list[-i] = abs(last_hs - hs[-i])
    for i in range(k+1,n+1):
        hs_i = hs[-i]
        ans_list[-i] = min([abs(hs_i-hs[x])+ans_list[x] for x in range(1-i,k+1-i)])
    print(ans_list[0])


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline
    n, k = map(int, input().split())
    hs = list(map(int, input().split()))
    if n <= k+1:
        print(abs(hs[0]-hs[-1]))
        exit()
    ans_list = [0]*n
    last_hs = hs[-1]
    for i in range(1,k+2):
        ans_list[-i] = abs(last_hs - hs[-i])
    for i in range(k+2,n+1):
        hs_i = hs[-i]
        ans_list[-i] = min([abs(hs_i-x)+y for x,y in zip(hs[1-i:k+1-i],ans_list[1-i:k+1-i])])
    print(ans_list[0])
### BUGGY CODE ###

l, r = map(int, input().split())
x = 2018

for i in range(l,r):
  for j in range(i+1, r+1):
    if (i * j) % 2019 <x:
      x = (i * j) % 2019
print(x)
    

### FIXED CODE ###

l, r = map(int, input().split())
x = 2018

if r - l >=2019:
  x = 0
  
else:
  for i in range(l,r):
    for j in range(i+1, r+1):
      if (i * j) % 2019 < x:
        x = (i * j) % 2019
        
print(x)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
suma=sum(a)
p=suma
for i in range(n):
    f=sum(a[:i])
    p=min(p,abs(suma-2*f))
print(p)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
suma=sum(a)
f=0
p=suma-2*f
for i in a:
    f+=i
    p=min(p,abs(suma-2*f))
print(p)
### BUGGY CODE ###


N,M = map(int,input().split())
A = list(map(int,input().split()))
for i in range(M):
  p = A.index(max(A))
  A[p] = int(A[p]/2)
print(sum(A))
 


### FIXED CODE ###

import numpy as np
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
A = [x*(-1) for x in A]
heapq.heapify(A)
for i in range(M):
  heapq.heapreplace(A,int(A[0]/2))
print(-sum(A))
### BUGGY CODE ###

import numpy as np

def seachPrimeNum(N):
    ma = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= ma:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

A,B =map(int,input().split())

plis = seachPrimeNum(max(2,min(A,B)))

ans = 1
for p in plis:
    if A%p +B%p ==0:
        ans += 1
        A = A//p
        B = B//p
        if min(A,B) == 1:
            break
print(ans)


### FIXED CODE ###


A,B = map(int,input().split())

#素数列挙
def searchPrimeNum(N):
    max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



#素因数分解(素数列挙が必要)
def pfact(N):
    plis = searchPrimeNum(int(N**0.5+1))
    ans = 1
    for p in plis:
        if N%p == 0:
            ans += 1
            N = N//p
        while N%p == 0:
            N = N//p
        if N == 1:
            break
    if N != 1:
        ans += 1
    return ans

#互除法(最大公約数)
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

print(pfact(gcd(A,B)))
### BUGGY CODE ###

l, r = list(map(int,input().split()))
Set = set([l%2019])
for i in range(r-l):
	Set.add((l+1+i)%2019)
List = list(Set)
if(0 in List):
	print(0)
else:
	answer = (l * r) % 2019
	k = 0
	for i in range(len(List)):
		for j in range(len(List)):
			if(i < j):
					if(answer > (List[i] * List[j])% 2019):
						answer = (List[i] * List[j])% 2019
						k = 1
	print(answer)

### FIXED CODE ###

l, r = list(map(int,input().split()))
lmod = l % 2019
rmod = r % 2019
if(r-l) >= 2018:
	answer = 0
elif(lmod > rmod):
	answer = 0
else:
	answer = (rmod * lmod)% 2019
	for i in range(rmod - lmod + 1):
		for j in range(rmod - lmod + 1):
			if(i < j):
				if(answer > (lmod + i) * (lmod + j) % 2019):
					answer = (lmod + i) * (lmod + j) % 2019
print(answer)
### BUGGY CODE ###

num = int(input())
lst = []
while num > 0:
    lst.append(num%10)
    num //= 10
if sum(lst) % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

lst = list(input())
total = sum([int(i) for i in lst])
if total % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

# Fast IO (only use in integer input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
Resident = []
for i in range(N):
    x,y,p = map(int,input().split())
    Resident.append((x,y,p))

minCost = [-1] * (N+1)

totalCases = 3 ** N

for i in range(totalCases):
    railRoad = []
    tmp = i
    for j in range(N):
        railRoad.append(tmp % 3)
        tmp //= 3
    numNewRailroad = sum(map(lambda x: 1 if x != 0 else 0,railRoad))
    minDistance = [-1] * N
    for j in range(N):
        minDistance[j] = min(abs(Resident[j][0]),abs(Resident[j][1]))
        for k in range(N):
            if railRoad[k] == 1 and abs(Resident[j][0] - Resident[k][0]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][0] - Resident[k][0])
            if railRoad[k] == 2 and abs(Resident[j][1] - Resident[k][1]) < minDistance[j]:
                minDistance[j] = abs(Resident[j][1] - Resident[k][1])
    cost = 0
    for j in range(N):
        cost += Resident[j][2] * minDistance[j]
    if minCost[numNewRailroad] == -1 or minCost[numNewRailroad] > cost:
        minCost[numNewRailroad] = cost
print('\n'.join(list(map(str,minCost))))


### FIXED CODE ###

# Fast IO (only use in integer input)

# TLE

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

def main():

    N = int(input())
    Resident = []
    for i in range(N):
        x,y,p = map(int,input().split())
        Resident.append((x,y,p))

    def abs(N):
        if N >= 0:
            return N
        else:
            return -N

    minCost = [float("inf")] * (N+1)

    preCalRange = 1 << N

    horizontalLineDistance = []
    verticalLineDistance = []

    for i in range(preCalRange):
        railRoad = bin(i)[2:]
        railRoad = '0' * (N - len(railRoad)) + railRoad
        horizontalLineDistance.append([])
        verticalLineDistance.append([])
        for j in range(N):
            horizontalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            verticalLineDistance[i].append(min(abs(Resident[j][0]),abs(Resident[j][1])))
            for k in range(N):
                if railRoad[k] == '1' and abs(Resident[j][0] - Resident[k][0]) < horizontalLineDistance[i][j]:
                    horizontalLineDistance[i][j] = abs(Resident[j][0] - Resident[k][0])
                if railRoad[k] == '1' and abs(Resident[j][1] - Resident[k][1]) < verticalLineDistance[i][j]:
                    verticalLineDistance[i][j] = abs(Resident[j][1] - Resident[k][1])

    power2 = [1]
    for i in range(N):
        power2.append(power2[-1] * 2)
    loopCount = power2[N]
    for i in range(loopCount):
        numNewRailroad = bin(i)[2:].count('1')
        j = i
        while j >= 0:
            j &= i
            goodList1 = horizontalLineDistance[j]
            goodList2 = verticalLineDistance[i - j]
            cost = 0
            for k in range(N):
                cost += Resident[k][2] * min(goodList1[k], goodList2[k])
            if minCost[numNewRailroad] > cost:
                minCost[numNewRailroad] = cost
            j -= 1
    for elem in minCost:
        print(elem)

main()
### BUGGY CODE ###

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

dp = [-1] * (T + 3000)
dp[0] = 0
c = 0
for a, b in sorted(AB):
    for j in range(c, -1, -1):
        if dp[j] == -1:
            continue
        t = dp[j] + b
        if dp[j + a] < t:
            dp[j + a] = t
    c = min(c + a, T - 1)
print(max(dp))


### FIXED CODE ###

def main():
    N, T = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [-1] * (T + 3000)
    dp[0] = 0
    for a, b in sorted(AB):
        for j in range(T - 1, -1, -1):
            if dp[j] == -1:
                continue
            if dp[j] + b > dp[j + a]:
                dp[j + a] = dp[j] + b
    print(max(dp))


main()
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
B = []
b = 1
ans = 1
while ans:
  b = A[b-1]
  B.append(b)
  

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
pos = 0
visit = [0] * N
move = []
roop = []
while visit[pos]!=2:
    if visit[pos]==0:
        move.append(pos)
    else:
        roop.append(pos)
    visit[pos] += 1
    pos = A[pos] - 1
if len(move)>K:
    print(move[K]+1)
else:
    print(roop[(K-(len(move)-len(roop)))%len(roop)]+1)
### BUGGY CODE ###

n,m=map(int, input().split())
a=list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
for i in range(m):
    for j in range(bc[i][0]):
        a.append(bc[i][1])
a.sort(reverse=True)
ans=0
for i in range(n):
    ans+=a[i]
print(ans)


### FIXED CODE ###

n,m=map(int, input().split())
a=list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
x=[]
for i in range(n):
    x.append([a[i],1])
for i in range(m):
    x.append([bc[i][1],bc[i][0]])
x.sort(reverse=True)
ans=0
count=n
for i in range(n):
    if x[i][1]<count:
        ans+=x[i][0]*x[i][1]
    else:
        ans+=x[i][0]*count
    count-=x[i][1]
    if count<=0:
        break
print(ans)
### BUGGY CODE ###

import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
LR.sort(key=lambda x: x[1])

table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += bisect.bisect_right(table[i], q)
    print(ans)


### FIXED CODE ###

import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
dp = [[0]*(N+1) for i in range(N+1)]

for L, R in LR:
    dp[L][R] += 1
for i in reversed(range(1, N)):
    for j in range(1, N+1):
        dp[i][j] += dp[i+1][j]

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


for _ in range(Q):
    p, q = map(int, input().split())
    print(dp[p][q])
### BUGGY CODE ###

import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    clocks = inputs
    clocks.sort()

    max_c = clocks.pop()
    clocks = set(clocks)

    pops = []
    for c in clocks:
        if max_c % c == 0:
            pops.append(c)
    for p in pops:
        clocks.remove(p)

    count = max_c
    while count <= 10 ** 18:
        fin = count
        for c in clocks:
            if count % c != 0:
                fin = None
                break
        if fin is not None:
            return count
        count += max_c


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(int_inputs(N))
    print(ret)


### FIXED CODE ###

import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def euqrid(a, b):
    if a > b:
        large = a
        small = b
    else:
        large = b
        small = a

    if small == 0:
        return large
    return euqrid(small, large % small)


def calc_m(numbers):
    if len(numbers) == 1:
        return numbers[0]
    if len(numbers) == 2:
        a = numbers.pop()
        b = numbers.pop()
        e = euqrid(a, b)
        return a * b // e
    a = numbers.pop()
    b = calc_m(numbers)
    e = euqrid(a, b)
    return a * b // e


def solve(inputs):
    clocks = inputs
    return calc_m(clocks)


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    N = int(input())
    ret = solve(int_inputs(N))
    print(ret)
### BUGGY CODE ###

from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0, h0))
    r = h0
    for i, (x, h) in enumerate(XH):
        while Q:
            xx, hh = Q[0]
            if xx < x - D:
                Q.popleft()
            else:
                break
        for xx, hh in Q:
            h -= hh 
            if h <= 0:
                break
        else:
            Q.append((x, h))
            r += h
    print(r)

main()


### FIXED CODE ###

from collections import deque

def main():
    N, D, A = list(map(int, input().split()))
    XH = []
    for _ in range(N):
        x, h = map(int, input().split())
        h = (h + A - 1) // A
        XH.append((x, h))
    XH.sort()
    D *= 2
    Q = deque()
    x0, h0 = XH[0]
    Q.append((x0 + D, h0))
    r = h0
    c = h0
    for x, h in XH:
        while Q and Q[0][0] < x:
            _, hh = Q.popleft()
            c -= hh
        h -= c
        if h > 0:
            Q.append((x + D, h))
            c += h
            r += h
    print(r)

main()
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math


def generate_intervals(n):
    if n > 1:
        l = math.ceil(math.log(2 * n + 1, 3))
        return [(3 ** i - 1) // 2 for i in range(l - 1, 0, -1)]
    else:
        return [1]


class Sort(object):

    def __init__(self, array, num):
        self.a = array
        self.n = num
        self.cnt = 0
        self.gs = generate_intervals(self.n)
        self.m = len(self.gs)

    def insertionsort(self, g):
        for i in range(g, self.n):
            v = self.a[i]
            j = i - g
            while j >= 0 and self.a[j] > v:
                self.a[j + g] = self.a[j]
                j = j - g
                self.cnt += 1
            self.a[j + g] = v

    def shellsort(self):
        for i in range(0, self.m):
            self.insertionsort(self.gs[i])


def main():
    n = int(input())
    a = [int(input()) for i in range(n)]
    s = Sort(a, n)
    s.shellsort()
    print(s.m)
    print(" ".join(map(str, s.gs)))
    print(s.cnt)
    for i in range(n):
        print(s.a[i])


if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3

def construct_gs(n):
    gs = []
    g = 1
    while g <= n:
        gs.append(g)
        g = 3 * g + 1
    return gs[::-1]


def shell_sort(xs, n):
    global cnt
    cnt = 0
    gs = construct_gs(n)
    m = len(gs)
    def insertion_sort(g):
        global cnt
        for i in range(g, n):
            v = xs[i]
            j = i - g
            while j >= 0 and xs[j] > v:
                xs[j + g] = xs[j]
                j = j - g
                cnt += 1
            xs[j + g] = v
    for g in gs:
        insertion_sort(g)
    return m, gs, cnt, xs


def main():
    n = int(input())
    xs = [int(input()) for _ in range(n)]
    m, gs, cnt, xs = shell_sort(xs, n)
    print(m)
    print(" ".join(map(str, gs)))
    print(cnt)
    for x in xs:
        print(x)


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

N, K = map(int, input().split())
p = list(map(int, input().split()))
e = [(n+1)/2 for n in p]
ans = 0
for i in range(N-K+1):
  ans = max(ans, sum(e[i:i+K]))
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))
e = [(n+1)/2 for n in p]
now = sum(e[0:K])
ans = now
if N == 1:
  print(e[0])
  exit()

for i in range(1, N-K+1):
  now -= e[i-1]
  now += e[i+K-1]
  ans = max(ans, now)
print(ans)
### BUGGY CODE ###

l, r = map(int, input().split())

ans = 1000000000
for i in range(l, r):
  for j in range(i + 1, r + 1):
    ans = min((i * j) % 2019, ans)

print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
r = min(r, l + 4038)
ans = 2018
for i in range(l, r):
  for j in range(i + 1, r + 1):
    ans = min((i * j) % 2019, ans)
    #割り切れた場合はそれが最小値なので探索終了とする
    if ans == 0:
      break

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

n = int(input())

bariety = []

h = []

for i in range(n):
    t = input()
    if t not in bariety:
        bariety.append(t)
        h.append([t,1])
    else:
        h[bariety.index(t)][1] += 1
        
for i in h:
    i.reverse()
    
h.sort(reverse = True)

maxh = h[0][0]

ans = []

for i in h:
    if i[0] == maxh:
        ans.append(i[1])
        
ans.sort()

for i in ans:
    print(i)

### FIXED CODE ###


import collections as col

n = int(input())

s = []

for i in range(n):
    s.append(input())
    
x = col.Counter(s)

m = 0

x = x.most_common()

ans = []

for i in x:
    if i[1]<m:
        break
    else:
        ans.append(i[0])
        m = i[1]
        
ans.sort()

for i in ans:
    print(i)
### BUGGY CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
for i in range(n-1):
  ans += str_list[i+1:].count(str_list[i])
print(ans)


### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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

if N%2:
    x,y=N//2,N//2+1
    for i in range(M):
        print(x-i,y+i)

else:
    #lst=set([i for i in range(1,N//2+1)])
    visited=set()
    c=1
    z=1
    while M:
        if c>N:
            c=1
        if c in visited:
            c+=1
            continue
        else:
            Z=c+z
            if Z>N:
                Z-=N
            if Z in visited:
                c+=1
                continue
            else:
                print(c,Z)
                visited.add(c)
                visited.add(c+z)
                c+=1
                z+=1
                M-=1


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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

if N%2:
    x,y=N//2,N//2+1
    for i in range(M):
        print(x-i,y+i)

else:

    for i in range(M//2+M%2):
        print(1+i,1+M-1*(M%2==0)-i)
    for i in range(M//2):
        print(N-(M-M%2)+i,N-i)
### BUGGY CODE ###

def f(p):
    return sum([n for n in range(1,p) if p%n==0])

while 1:
    n=int(input())
    if n==0:break
    m=f(n)
    if n==m:print('perfect number')
    else: print('deficient number' if n>m else 'abundant number')

### FIXED CODE ###

def f(p):
    ans=1
    if p<=5: return 0
    for n in range(2,int(p**0.5)+1):
        if p%n==0:
            if n!=p//n:ans+=n+p//n
            else:ans+=n
    return ans

while 1:
    n=int(input())
    if n==0:break
    m=f(n)
    if n==m:print('perfect number')
    else: print('deficient number' if n>m else 'abundant number')
### BUGGY CODE ###

from collections import defaultdict
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=defaultdict(lambda:0)
# dp[i]:足場iに到達するための最小コスト。はじめカエルは足場1にいるのでdp[1]=0
dp[1]=0
dp[2]=abs(h[0]-h[1])
for i in range(3,n+1):      
      dp[i]=min([dp[i-j]+abs(h[i-1]-h[i-j-1]) for j in range(1,min(k+1,i))])
print(dp[n])


### FIXED CODE ###

n,k=map(int,input().split())
import numpy as np
h=np.array(input().split(),np.int64)
if n<3:
  print(abs(h[0]-h[1]))
  exit()
dp=np.zeros(n)
dp[1]=abs(h[0]-h[1])
for i in range(2,n):
  j=max(0,i-k)
  dp[i]=np.min(dp[j:i]+np.abs(h[i]-h[j:i]))
  #dp[i]=min([dp[i-j]+abs(h[i]-h[i-j]) for j in range(1,min(k+1,i+1))])
print(int(dp[-1]))
### BUGGY CODE ###

Q = int(input())
LR = []
max = 0

for i in range(Q):
  _input = input().split(' ')
  LR.append((int(_input[0]), int(_input[1])))
  if max < LR[i][1]:
    max = LR[i][1]

num = [True]*(max+1)
num[0] = num[1] = False
for i in range(2,int(max**0.5)+1):
  if num[i]:
    for j in range(i**2, max, i):
      num[j] = False
primeList = [i for i in range(2,max+1) if num[i]]

for i in range(Q):
  sum = 0
  for i in range(LR[i][0], LR[i][1]+1):
    if (i in primeList) and ((i+1)/2 in primeList):
      sum = sum + 1
  print(sum)

### FIXED CODE ###

num = [True]*100001
num[0] = num[1] = False
for i in range(2,317):
  if num[i]:
    for j in range(i**2, 100000, i):
      num[j] = False

c = [0]*100002
for i in range(3, 100001, 2):
  if (num[i]) and (num[int((i+1)/2)]):
    c[i] = c[i] + 1

for i in range(3, 100001):
  c[i] = c[i] + c[i-1]

for i in range(int(input())):
  _input = input().split(' ')
  print(c[int(_input[1])] - c[int(_input[0])-1])
### BUGGY CODE ###

x,y=map(int,input().split())
cnt=0
dp=[[0 for i in range(x+1)]for i in range(2)]
a=10**9+7
if x>1:
    dp[1][2]=1
if y>1:
    dp[0][1]=1

for i in range(y+1):
    if i<3:
        continue
    for j in range(x,-1,-1):
        if i%2==0:
            if dp[1][j-2]!=0 or dp[0][j-1]!=0:
                dp[0][j]=(dp[1][j-2]+dp[0][j-1])%a
            else:
                dp[0][j]=0
                
        else:
            if dp[0][j-2]!=0 or dp[1][j-1]!=0:
                dp[1][j]=(dp[0][j-2]+dp[1][j-1])%a
            else:
                dp[1][j]=0
if y%2==0:
    print(dp[0][x])
else:
    print(dp[1][x])

### FIXED CODE ###

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

x,y=map(int,input().split())
if (x+y)%3!=0 or min(x,y)<(x+y)/3:
    print(0)
    exit()
n=(x+y)//3
r=(n-abs(x-y))//2
mod=10**9+7
a = cmb(n,r)
print(a%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_t = [0]
for i in range(n):
    a_t.append(a[i] + a_t[i])
ans = 0
for i in range(n + 1):
    for j in range(i + 1, n + 1):
        b = a_t[j] - a_t[i]
        if not b % m:
            ans += 1
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a_t = [0]
for i in range(n):
    a_t.append(a[i] + a_t[i])
dict = {}
for i in range(n + 1):
    b = a_t[i] % m
    if b in dict:
        dict[b] += 1
    else:
        dict[b] = 1
ans = 0
for i in dict.values():
    ans += i * (i - 1) // 2
print(ans)