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

def main():
    import numpy as np
    n,m=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    dp=np.zeros((n+1,m+1),dtype=np.int32)
    dp[:,m]=1
    dp[n,:]=1
    for i in range(n-1,-1,-1):
        temp=s[i]
        for j in range(m-1,-1,-1):
            if t[j]!=temp:
                dp[i,j]=(dp[i+1,j]+dp[i,j+1]-dp[i+1,j+1])%(10**9+7)
            else:
                dp[i,j]=(dp[i+1,j]+dp[i,j+1])%(10**9+7)
    print(dp[0,0])
main()

### FIXED CODE ###

def main():
    n,m=map(int,input().split())
    s=list(map(int,input().split()))
    t=list(map(int,input().split()))
    dp=[[0]*(m+1) for _ in [0]*(n+1)]
    for i in range(n+1):
        dp[i][m]=1
    for i in range(m+1):
        dp[n][i]=1
    for i in range(n-1,-1,-1):
        for j in range(m-1,-1,-1):
            dp[i][j]=(dp[i+1][j]+dp[i][j+1]-(s[i]!=t[j])*dp[i+1][j+1])%(10**9+7)
    print(dp[0][0])
main()
### BUGGY CODE ###

import sys
import numpy as np

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = np.array(s[1])
Q = s[2][0]
BC = np.array(s[3:])
B = BC[:, 0]
C = BC[:, 1]

A_sum = np.sum(A)

D = np.zeros(100001).astype(np.uint32)
D = np.array([np.count_nonzero(A == i) for i in range(100001)])
for i in range(Q):
    b = B[i]
    c = C[i]
    A_sum += D[b] * (c - b)
    print(A_sum)
    D[c] += D[b]
    D[b] = 0


### FIXED CODE ###

import sys
import numpy as np
from collections import Counter

# 実行環境(0:vscode, 1:atcoder)
MODE = 1

# 入力の次元
DIMENSION = 2

# int型に変換
INT_TYPE = 1

if not (MODE):
    with open("input.txt", "r") as f:
        s = f.read()
else:
    s = sys.stdin.read()

if DIMENSION == 0:
    if INT_TYPE == 1:
        s = int(s)
elif DIMENSION == 1:
    if INT_TYPE == 0:
        s = s.split()
    elif INT_TYPE == 1:
        s = [int(x) for x in s.split()]
elif DIMENSION == 2:
    if INT_TYPE == 0:
        s = [x.split() for x in s.splitlines()]
    elif INT_TYPE == 1:
        s = [[int(y) for y in x.split()] for x in s.splitlines()]

N = s[0][0]
A = np.array(s[1])
Q = s[2][0]
BC = np.array(s[3:])
B = BC[:, 0]
C = BC[:, 1]

A_sum = np.sum(A)

D = Counter(A)

for i in range(Q):
    b = B[i]
    c = C[i]
    A_sum += D[b] * (c - b)
    print(A_sum)
    D[c] += D[b]
    D[b] = 0
### BUGGY CODE ###

import math
n=int(input())
g=0
for i in range(1,n+1):
    j= math.floor(n/i)
    g+= j*(j+1)*i/2
print(int(g))

### FIXED CODE ###


n=int(input())
g=0
for i in range(1,n+1):
    g+= 0.5*i*(n//i)*((n//i)+1)
print(int(g))
### BUGGY CODE ###

import itertools
n,*a=open(0).read().split()
a=[''.join(sorted(i)) for i in a]
p=0
for i,j in itertools.combinations(range(int(n)),2):
    #print(i,j)
    if a[i]==a[j]:
        p+=1
print(p)

### FIXED CODE ###

import math

def ABC137C(i):
    if i!=1:
        return math.factorial(i)//math.factorial(i-2)//2
    else:
        return 0

n,*a=open(0).read().split()
a=[''.join(sorted(i)) for i in a]
d=dict()
p=0
for i in a:
    if i not in d:
        d[i]=1
    else:
        d[i]+=1
for i in d.values():
    p+=ABC137C(i)
print(p)
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
import numpy as np

def main():
	h,w=map(int,input().split())
	AB=np.array(read().split(), np.int64)
	
	
	A=AB[:h*w]
	B=AB[h*w:]
	
	A=np.reshape(A, (h,w))
	B = np.reshape(B, (h, w))
	
	G=abs(A-B)
	M=(h+w)*80

	
	li=[[[0]*M for i in range(w)] for j in range(h)]

	
	li[0][0][G[0][0]]=1
	for i in range(h):
		for j in range(w):
			for k in range(M):

				if li[i][j][k]==1:

					try:
						li[i + 1][j][abs(k - G[i][j])] = 1
						li[i + 1][j][abs(k + G[i][j])] = 1
					except:
						pass
					try:
						li[i][j + 1][abs(k - G[i][j])] = 1
						li[i][j + 1][abs(k + G[i][j])] = 1
					except:
						pass
	
	for i in range(M):
		if li[h-1][w-1][i]==1:
			print(i-1)
			exit(0)
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np

def main():
	h, w = map(int, input().split())
	
	G = [[0] * w for i in range(h)]
	A = [0]*h
	B = [0]*h
	
	for i in range(h):
		A[i] = list(map(int, input().split()))
	for i in range(h):
		B[i] = list(map(int, input().split()))
	
	for i in range(h):
		for j in range(w):
			G[i][j]=abs(A[i][j]-B[i][j])

	M = (h + w) * 80

	li = [[[0] * M for i in range(w)] for j in range(h)]
	
	li[0][0][G[0][0]] = 1
	for i in range(h):
		for j in range(w):
			for k in range(M):
				
				if li[i][j][k] == 1:
					if i < h - 1:
						li[i + 1][j][abs(k - G[i+1][j])] = 1
						li[i + 1][j][abs(k + G[i+1][j])] = 1
					if j < w - 1:
						li[i][j + 1][abs(k - G[i][j+1])] = 1
						li[i][j + 1][abs(k + G[i][j+1])] = 1

	for i in range(M):
		if li[h-1][w - 1][i] == 1:
			print(i)
			exit(0)


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

length, quests = map(int, input().rstrip().split())
string = input()

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    substring = string[left-1:right]
    j = 0
    count = 0
    while j < len(substring) - 1:
        if substring[j] == 'A' and substring[j + 1] == 'C':
            count += 1
            j += 2
        else:
            j += 1
    print(count)


### FIXED CODE ###

length, quests = map(int, input().rstrip().split())
string = input()
totals = [0]

count = 0
for i in range(1, len(string)):
    if string[i-1] == "A" and string[i] == "C":
        count += 1
    totals.append(count)

for i in range(quests):
    left, right = map(int, input().rstrip().split())
    print(totals[right-1] - totals[left-1])
### BUGGY CODE ###

mod =1000000007
n = int(input())
a = list(map(int, input().split()))
sumpro = 0

for i in range(n-1):
    x = 0
    for j in range(i+1, n):
        x += a[j]
    x = x%mod
    y = a[i]* x
    if y > mod:
        y = y%mod
    sumpro += y
    if sumpro > mod:
        sumpro = sumpro%mod    
print(sumpro)

### FIXED CODE ###

MOD = 10 ** 9 + 7  # MODは変数に入れてしまったほうが打ち間違えなくていいです

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

S = sum(A) % MOD
ans = 0

# A_Nも含まれてしまいますが、そのときはs=0なので問題ありません
for x in A:
    S -= x  # 自分と自分自身を掛けないように、先に引く必要があります
    S %= MOD  # MODはいちいち取っておくといいです
    ans += S * x
    ans %= MOD

ans %= MOD  # この行は完全に不要ですが、最後だけMODを取り忘れてWAになるミスは非常によくあるので、必要以上に取っておくと安心できます
print(ans)
### BUGGY CODE ###

import numpy as np
from itertools import combinations, permutations

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n)]


def mean_dis(data):
    comb = permutations(data, n)
    sum = 0
    count = 0
    for c in comb:
        count += 1
        for i in range(1, len(c)):
            _c = np.array([c[i-1], c[i]])
            euclid = np.sqrt(np.sum((_c[0]-_c[1]) ** 2))
            sum += euclid
    return sum/count


print(mean_dis(ls))

### FIXED CODE ###

import numpy as np
from itertools import combinations, permutations

n = int(input())
ls = [list(map(int, input().split())) for _ in range(n)]


def mean_dis(data):
    comb = permutations(data, n)
    sum = 0
    count = 0
    for c in comb:
        count += 1
        for i in range(1, len(c)):
            _c = np.array([c[i-1], c[i]])
            euclid = np.sqrt(np.sum((_c[0]-_c[1]) ** 2))
            sum += euclid
    return sum/count


def mean_dis2(data, n):
    comb = combinations(data, 2)
    all_dis = 0
    for c in comb:
        _c = np.array([c[0], c[1]])
        euclid = np.sqrt(np.sum((_c[0] - _c[1]) ** 2))
        all_dis += euclid

    return (all_dis*2)/n

print(mean_dis2(ls, n))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(10 ** 8 // n):
    f = 0
    for j in range(n):
        f += i % a[j]
    print(f)
    ans.append(f)
print(max(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
f = 0
ans = np.cumsum(a) - n
print(ans[-1])
### BUGGY CODE ###

import sys
from bisect import bisect

def main():
    input = sys.stdin.readline
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    ans = 0
    for a in A:
        n = bisect(B, a)
        for b in B[n:]:
            m = bisect(C, b)
            ans += (N - m)

    print(ans)



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from bisect import bisect
from itertools import accumulate

def main():
    input = sys.stdin.readline
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    Bn = [0] * N
    for i in range(N):
        b = B[i]
        m = bisect(C, b)
        Bn[i] = (N - m)

    Bn = list(accumulate(Bn[::-1]))[::-1]
    Bn += [0]

    ans = 0
    for i in range(N):
        a = A[i]
        m = bisect(B, a)
        ans += Bn[m]

    print(ans)


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

import sys
sys.setrecursionlimit(10**5)
def 解():
	iN,iK,iL = [int(_) for _ in input().split()]
	aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]
	a道 = aD[0:iK]
	a鉄道 = aD[iK:]

	d道 = {}
	d鉄道 = {}
	def fMakeSet(d,x,y):
		if x in d:
			d[x].add(y)
		else:
			d[x] = {y}
		
	for p,q in a道:
		fMakeSet(d道,q,p)
		fMakeSet(d道,p,q)
	for r,s in a鉄道:
		fMakeSet(d鉄道,r,s)
		fMakeSet(d鉄道,s,r)

	def fdfs(d,iS):
		dsVisited=set()
		def digRoute(iT):
			dsVisited.add(iT)
			if iT in d:
				for i in d[iT] - dsVisited:
					#dsVisited.add(i)
					digRoute(i)
		digRoute(iS)	
		return dsVisited

	def buildGroup(d):
		gl = {}
		gidx = {}
		v = set()
		iC = 0
		for i in range(1,iN+1):
			if i in v:
				continue
			else:
				dsList = fdfs(d,i)
				for i in dsList:
					gidx[i] = iC
				gl[iC]=dsList
				iC += 1
				v = v | dsList
		return (gl,gidx)
	dg鉄道,idxdg鉄道 = (buildGroup(d鉄道))
	dg道,idxdg道 = (buildGroup(d道))
	ak鉄道 = dg鉄道.keys()
	ak道 = dg道.keys()
	aM = [[ None for _ in range(len(ak道))] for _ in range(len(ak鉄道))]
	for i in ak鉄道:
		for j in ak道:
			aM[i][j]=str(len(dg鉄道[i] & dg道[j]))
	aRet = []
	for i in range(1,iN+1):	
		aRet.append(aM[idxdg鉄道[i]][idxdg道[i]])
	print( " ".join(aRet))
解()


### FIXED CODE ###

#Union-Find木の構築
import sys
def 解():
    iN,iK,iL = [int(_) for _ in input().split()]
    aD = [[int(_) for _ in sLine.split()] for sLine in sys.stdin.readlines()]

    def buildTree(a):
        aT = [0]*(iN+1)
        for p,q in a:
            rp = getRoot(aT,p)
            rq = getRoot(aT,q)
            thisRoot = max(rp,rq,q)
            aT[p] = thisRoot
            aT[q] = thisRoot
            aT[rp] = thisRoot #これで Union してるつもり
            aT[rq] = thisRoot
        return aT
    def getRoot(a,i): #find みんな小さい方に合わせるならデカい方に合わせてみよう
        if a[i] == i or a[i] == 0:
            if a[i] == 0 : a[i] = i
            return i
        elif i < a[i] :
            a[i] = getRoot(a,a[i])
            return a[i]
    #   else:
    #       print("! ",i,a[i])

    aT道 = buildTree(aD[0:iK])
    aT鉄道 = buildTree(aD[iK:])
    aRet = []
    dRet = {}
    for i in range(1,iN+1):
        # いやはやこんなもんもキーになるのか。
        Comb = (getRoot(aT道,i), getRoot(aT鉄道,i))
        aRet.append(Comb)
        if Comb in dRet:
            dRet[Comb] += 1
        else:
            dRet[Comb] = 1
    print(" ".join([str(dRet[_]) for _ in aRet]))

解()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import heapq

def main(): 

    X,Y,Z,K = map(int,input().split())
    
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    
    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    ABC=[]
    for i in range(min(K,len(AB))):
        for j in range(Z):
            ABC.append(AB[i]+C[j])
    ABC.sort(reverse=True)
    for i in range(K):
        print(ABC[i])


        


if __name__ == "__main__":
    main()
    

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq

def main(): 

    X,Y,Z,K = map(int,input().split())
    
    A=list(map(int,input().split()))
    B=list(map(int,input().split()))
    C=list(map(int,input().split()))
    
    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    ABC=[]
    for i in range(min(K,len(AB))):
        for j in range(Z):
            ABC.append(AB[i]+C[j])
    ABC.sort(reverse=True)
    for i in range(K):
        print(ABC[i])


        


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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

s = input()
for i in range(len(s)):
	for j in range(i+1, len(s)):
		c = Counter(s[i:j+1])
		if len(s[i:j+1]) < c.most_common()[0][1]*2:
			print(i+1, j+1)
			break
	else:
		continue
	break
else:
	print(-1, -1)




### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

s = input()

dic = defaultdict(list)

for i, x in enumerate(s, 1):
	dic[x].append(i)

for lis in dic.values():
	for i in range(len(lis)-1):
		if lis[i+1] <= lis[i]+2:
			print(lis[i], lis[i+1])
			break
	else:
		continue
	break
else:
	print(-1, -1)
### BUGGY CODE ###

n, k = map(int, input().split())
a = [int(t) - 1 for t in input().split()]

loc = 0
visited_list = []
loop_idx = -1
while True:
    visited_list.append(loc + 1)
    loc = a[loc]
    if loc + 1 in visited_list:
        loop_idx = visited_list.index(loc + 1)
        break
loop_len = len(visited_list) - loop_idx
start_len = len(visited_list) - loop_len
print(visited_list[start_len + (k - start_len) % loop_len] if k >= len(visited_list) else visited_list[k])


### FIXED CODE ###

n, k = map(int, input().split())
a = [int(t) - 1 for t in input().split()]

loc = 0
visited_bkt = [-1 for _ in range(2 * 10 ** 5 + 1)]
count = 0
loop_len = -1
while True:
    visited_bkt[loc + 1] = count
    loc = a[loc]
    count += 1
    if visited_bkt[loc + 1] >= 0:
        loop_len = count - visited_bkt[loc + 1]
        break
start_len = count - loop_len
print(visited_bkt.index(start_len + (k - start_len) % loop_len) if k >= count else visited_bkt.index(k))
### BUGGY CODE ###

import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

    for i in range(M):
        A, B, C = list(map(int, input().split()))
        A -= 1
        B -= 1
        G[A].append([C, B])
        G[B].append([C, A])


    def dijkstra(d):
        que = []

        for i in range(len(d)):
            if d[i] == -1:
                break
            heapq.heappush(que, (d[i], i))

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

    for i in range(N):
        ds[i][i] = 0

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())

### FIXED CODE ###

import heapq
import itertools

def solve():
    N, M, _ = list(map(int, input().split()))
    R = list(map(int, input().split()))
    R = map(lambda x: x-1, R)
    G = [[] for i in range(N)]

    for i in range(M):
        A, B, C = list(map(int, input().split()))
        A -= 1
        B -= 1
        G[A].append((C, B))
        G[B].append((C, A))


    def dijkstra(d):
        que = []

        tar = -1
        for i in range(len(d)):
            if d[i] == -1:
                break
            if d[i] == 0:
                tar = i
            heapq.heappush(que, (d[i], i))

        while len(que) != 0:
            dist, node = heapq.heappop(que)
            for (cost, to) in G[node]:
                if d[to] > d[node] + cost:
                    d[to] = d[node] + cost
                    heapq.heappush(que, (dist + cost, to))

        return d


    ds = [[1e16 for i in range(N)] for j in range(N)]

    for i in range(N):
        ds[i][i] = 0

    for i in range(N):
        ds[i] = dijkstra(ds[i])
        for j in range(N):
            ds[j][i] = ds[i][j]

    res = 1e16
    for r in list(itertools.permutations(R)):
        d = 0
        for i in range(len(r)-1):
            d += ds[r[i]][r[i+1]]
        res = min(res, d)

    return res

print(solve())
### BUGGY CODE ###

N, M = list(map(int, input().split()))
S = [0] * M
E = [0] * M
for i in range(M):
    S[i], E[i] = list(map(int, input().split()))
X = []
Y = []
for i in range(M):
    if S[i] == 1:
        X.append(E[i])
    if E[i] == N:
        Y.append(S[i])
while 1:
    if X == [] or Y == []:
        print("IMPOSSIBLE")
        break
    min_x = min(X)
    min_y = min(Y)
    if min_x == min_y:
        print("POSSIBLE")
        break
    elif min_x > min_y:
        Y.remove(min_y)
    elif min_x < min_y:
        X.remove(min_x)
else:
    print("IMPOSSIBLE")


### FIXED CODE ###

N, M = list(map(int, input().split()))
X = [0] * N
Y = [0] * N
for i in range(M):
    S, E = list(map(int, input().split()))
    if S == 1:
        X[E-1] = 1
    if E == N:
        Y[S-1] = 1
for i in range(N):
    if X[i] == 1 and Y[i] == 1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import bisect

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

for i in range(N-1):
    A = int(input())
    idx = bisect.bisect_left(find, A)

    if not idx:
        find.insert(0, A)
    else:
        find[idx-1] = A

print(len(find))

### FIXED CODE ###

from bisect import bisect_right

def main():    
    N = int(input())
    A = [int(input()) for i in range(N)]
    n = [A.pop(-1)]
    A.reverse()
    
    for a in A:
        if n[-1] <= a: n.append(a)
        else: n[bisect_right(n, a)] = a
    
    print(len(n))

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

N,M = map(int,input().split())
N_List = list(range(1,N+1))
for i in range(M):
    st,sp = map(int,input().split())
    N_List = set(list(range(st,sp + 1))) & set(N_List)
print(len(N_List))

### FIXED CODE ###

N,M = map(int,input().split())
for i in range(M):
    st,sp = map(int,input().split())
    if i == 0:
        N_List = [st,sp]
    else:
        if st > N_List[0]:
            N_List[0] = st
        if sp < N_List[1]:
            N_List[1] = sp   
print(len(list(range(N_List[0],N_List[1]+1))))
### BUGGY CODE ###

n = int(input(''))

l = len(str(n))
s = 0
for i in range(l):
    j=10**(l-i-1)
    y = n//j
    n -= y*j
    s+=y

if s%9==0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

n = input('')

s=0
for c in n:
    s+=int(c)

if s%9==0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

num = int(input().strip())
nums = []
while num > 0:
    tmp = int(input().strip())
    if tmp in nums:
        nums.remove(tmp)
    else:
        nums.append(tmp)
    num -= 1
print(len(nums))

### FIXED CODE ###

n = input()
d = {}
for x in xrange(n):
    temp = input()
    try:
        d[temp] = (d[temp] + 1) % 2
    except:
        d[temp] = 1
print sum(d.values())
### BUGGY CODE ###

A,B,M = (int(x) for x in input().split())
a = list()
b = list()
x = list()
y = list()
c = list()
for j in input().split():
    a.append(int(j))

for j in input().split():
    b.append(int(j))
    
for i in range(M):
    tx,ty,tc = (int(j) for j in input().split())
    x.append(int(tx))
    y.append(int(ty))
    c.append(int(tc))

pat = []
mini = 200000
for i in range(len(a)):
    for j in range(len(b)):
        pat = a[i] + b[j]
        if mini > pat:
            mini = pat
for i in range(M):
    pat = a[x[i]-1] + b[y[i]-1] - c[i]
    if mini > pat:
        mini = pat

print(mini)



### FIXED CODE ###

import copy
A,B,M = (int(x) for x in input().split())
a = list()
b = list()
x = list()
y = list()
c = list()
for j in input().split():
    a.append(int(j))

for j in input().split():
    b.append(int(j))
    
for i in range(M):
    tx,ty,tc = (int(j) for j in input().split())
    x.append(int(tx))
    y.append(int(ty))
    c.append(int(tc))

pat=0
mini = 200000
ca = copy.copy(a)
cb = copy.copy(b)
a.sort()
b.sort()

mini = a[0] + b[0]

#for i in range(len(a)):
#    for j in range(len(b)):
#        pat = a[i] + b[j]
#        if mini > pat:
#            mini = pat
for i in range(M):
    pat = ca[x[i]-1] + cb[y[i]-1] - c[i]
    if mini > pat:
        mini = pat

print(mini)