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

s = input()
t = input()

sl = len(s)
tl = len(t)
dp = [["" for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = "".join([dp[i-1][j-1],s[i-1]])
        else:
            if len(dp[i-1][j]) > len(dp[i][j-1]):
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i][j-1]
print(dp[sl][tl])

### FIXED CODE ###

s = input()
t = input()

sl = len(s)
tl = len(t)
dp = [[0 for i in range(tl+1)] for i in range(sl+1)]

#dp[i][j] sをi文字目、tをj文字目まで求めたときの最大の長さ

for i in range(1,sl+1):
    for j in range(1,tl+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

ansl = dp[sl][tl]
i = sl
j = tl
ans = [""]*ansl
while(ansl>0):
    if s[i-1] == t[j-1]:
        ans[ansl-1] = s[i-1]
        i -= 1
        j -= 1
        ansl -= 1
    elif dp[i][j]==dp[i-1][j]:
        i -= 1
    else:
        j -= 1

print("".join(ans))
### BUGGY CODE ###

import bisect

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

a_sorted = sorted(a)

for _ in range(m):
    b, c = [int(i) for i in input().split()]
    for __ in range(b):
        if a_sorted[0] < c:
            a_sorted.pop(0)
            bisect.insort(a_sorted, c)
        else:
            break

print(sum(a_sorted))


### FIXED CODE ###

import bisect

n, m = [int(i) for i in input().split()]
a_list = [int(i) for i in input().split()]

new_cards_info = {}

for a in a_list:
    if a in new_cards_info:
        new_cards_info[a] += 1
    else:
        new_cards_info[a] = 1

for _ in range(m):
    b, c = [int(i) for i in input().split()]
    if c in new_cards_info:
        new_cards_info[c] += b
    else:
        new_cards_info[c] = b

new_cards_info = sorted(new_cards_info.items(), key=lambda x:x[0], reverse=True)

sum = 0
count = 0

for key, size in new_cards_info:
    sum += key * size
    over = count + size - n
    if over >= 0:
        sum -= key * over
        break
    count += size

print(sum)
### BUGGY CODE ###

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

for i in range(1,n+1):
  print(a.count(i))

### FIXED CODE ###

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

count = [0]*n

for i in a:
  count[i-1]+=1
for i in count:
  print(i)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10000000)


N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ 0 for i in range(N) ]  for j in range(N) ]

def func(x,y,cnt):
	ret=0
	if x==y:
		if cnt%2==0:
			ret=A[x]
			dp[x][y]=ret
			return ret
		else:
			ret=-1*A[x]
			dp[x][y]=ret
			return ret
	if cnt%2==0:
		cnt+=1
		ret=max( func(x,y-1,cnt)+A[y] , func(x+1,y,cnt)+A[x]  )
	else:
		cnt+=1
		ret=min( func(x,y-1,cnt)-A[y] ,func(x+1,y ,cnt)-A[x] )

	dp[x][y]=ret
	return ret

func(0,N-1,0)

print dp[0][N-1]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N=input()
A=map(int, sys.stdin.readline().split())

dp=[ [ None for i in range(N) ]  for j in range(N) ]


for i in range(N-1,-1,-1):
	if N%2==0:
		dp[i][i]=A[i]*-1
	else:
		dp[i][i]=A[i]


for i in range(N-2,-1,-1):
	for j in range(i+1,N):
		t=N-(j-i+1)	#残りの要素数
		if t%2==0:
			if dp[i][j] is None : dp[i][j]=float("-inf")
			dp[i][j]=max(dp[i][j] , dp[i][j-1]+A[j])
			dp[i][j]=max(dp[i][j] , dp[i+1][j]+A[i])
		else:
			if dp[i][j] is None : dp[i][j]=float("inf")
			dp[i][j]=min(dp[i][j] , dp[i][j-1]-A[j])
			dp[i][j]=min(dp[i][j] , dp[i+1][j]-A[i])

print dp[0][N-1]
### BUGGY CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
t = [None for _ in range(n)]
prev = ''
for i in range(n):
  if t[i] is not None:
    continue
  if prev == 'R' and s[i] == 'L':
    j = i
    while t[j] == 'L' and j < n:
      t[j] = (j - (i - 1), i - 1)
      j += 1
    j = i - 1
    while t[j] == 'R' and j > 0:
      t[j] = (j - (i - 1), i - 1)
      j -= 1
  prev = s[i]
for i in range(n):
  p = i
  if s[p] == 'R':
    p += 1
    prev = 'R'
  else:
    p -= 1
    prev = 'L'
  count = 1
  while True:
    if t[p] is not None:
      fp = t[p][0]
      fcount = count + t[p][1]
      t[i] = (fp, fcount)
      if fcount % 2 == 0:
        result[fp] += 1
      else:
        result[fp - 1] += 1
      break
    if s[p] == 'R':
      p += 1
      prev = 'R'
    else:
      if prev == 'R':
        t[i] = (p, count)
        if count % 2 == 0:
          result[p] += 1
        else:
          result[p - 1] += 1
        break
      p -= 1
      prev = 'L'
    count += 1
print(' '.join(map(str, result)))


### FIXED CODE ###

s = input()
n = len(s)
result = [0 for _ in range(n)]
start = 0
c = 'R'
for i in range(1, n):
  if s[i] != c:
    if c == 'R':
      result[i - 1] += (i - start) // 2 + (i - start) % 2
      result[i] += (i - start) // 2
      c = 'L'
    else:
      result[start] += (i - start) // 2 + (i - start) % 2
      result[start - 1] += (i - start) // 2
      c = 'R'
    start = i
result[start] += (n - start) // 2 + (n - start) % 2
result[start - 1] += (n - start) // 2
print(*result)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    start = time.time()
    n,m = LI()
    e = collections.defaultdict(list)
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [False] * n
    def g(i,c):
        if b[i] != False:
            if c == False:
                return True
            return b[i] == c
        if c == False:
            c = 0
        b[i] = c
        for r,d in e[i]:
            if time.time() - start > 1.5:
                return True
            if not g(r,c+d):
                return False
        return True

    for i in range(n):
        if not g(i,False):
            return 'No'
    return 'Yes'


print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = [[] for _ in range(n)]
    if m > 0:
        for _ in range(m):
            l,r,d = LI()
            e[l-1].append((r-1,d))
            e[r-1].append((l-1,-d))

    b = [None] * n

    for i in range(n):
        if not b[i] is None:
            continue
        b[i] = 0
        q = [i]
        qi = 0
        nq = []
        while True:
            if len(q) == qi:
                if not nq:
                    break
                q = nq
                qi = 0
                nq = []
            j = q[qi]
            qi += 1
            c = b[j]
            for r,d in e[j]:
                if b[r] is None:
                    b[r] = c+d
                    nq.append(r)
                else:
                    if b[r] != c+d:
                        return 'No'

    return 'Yes'


print(main())
### BUGGY CODE ###

from bisect import bisect_left as lower_bound
def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(101111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,111111):
  ans=min(ans,dp[i])
print(ans)

### FIXED CODE ###

def IN(): return map(int,input().split())
ans = pow(2,31); mod = pow(10,9)+7
h,n=IN()
A=[]; dp=[pow(2,31)]*111111
for i in range(n):
  x,y=IN()
  A.append((x,y))
dp[0]=0
for a,b in A:
  for i in range(h+1111):
    dp[i+a]=min(dp[i+a],dp[i]+b)
for i in range(h,11111):
  ans=min(ans,dp[i])
print(ans)
### BUGGY CODE ###

nx = input()
nx = nx.split()
n = int(nx[0])
x = int(nx[1])
burgers = [None] * 51
burgers[0] = "P"
burgers[1] = "BPPPB"
burgers[2] = "BBPPPBPBPPPBB"
i = 3
while i<=50:
  burgers[i] = "B" + burgers[i-1] + "P" + burgers[i-1] + "B"
  i+=1
result = burgers[n][:x-1]
print(result.count("P"))

### FIXED CODE ###

def stack(layer, length):
  if layer==1:
    return "BPPPB"[:length].count("P")
  else:
    if length==(lengths[layer-1]+1)/2:
      return ps[layer-2]+1
    elif length<(lengths[layer-1]+1)/2:
      return stack(layer-1, length-1)
    else:
      return ps[layer-2]+1+stack(layer-1, length-lengths[layer-2]-2)
    
inp = input().split()
layer = int(inp[0])
length = int(inp[1])
lengths = [5]
ps = [3]
for i in range(49):
  lengths.append(lengths[i]*2+3)
  ps.append(ps[i]*2+1)
print(stack(layer, length))
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

dp=[0]*(w+1)

for i in range(n):
 for j in range(w,-1,-1):
  if j+l[i][0]<=w:
   dp[j+l[i][0]]=max(dp[j+l[i][0]],dp[j]+l[i][1])

print(max(dp))

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]

dp=[0]*(w+1)

for i in range(n):
 for j in range(w,-1,-1):
  if j+l[i][0]<=w:
   dp[j+l[i][0]] =max(dp[j+l[i][0]],dp[j]+l[i][1])

print(max(dp))
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
cs = [0]
ans = 0
for i in range(d[-1]):
  cs.append(cs[i]+d.count(i))

ans = cs.count(n/2)
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
cs = [0]
ans = 0
l= 0
for i in range(d[-1]):
  temp = 0
  while(True):
    if i == d[l]:
      temp += 1
      l += 1
    else:
      break

  cs.append(cs[i]+temp)

ans = cs.count(n/2)
print(ans)
### BUGGY CODE ###

n0 = int(1e5)+1
x = [0]*n0

n = int(input())
a0 = list(map(int,input().split()))
q = int(input())
bcs = []
for i in range(q):
    bcs.append(list(map(int,input().split())))

for a in a0:
    x[a] += 1

for bc in bcs:
    x[bc[1]] += x[bc[0]]
    x[bc[0]] = 0
    sum0 = 0
    for i in range(n0):
        sum0 += i*x[i]
    print(sum0)

### FIXED CODE ###

n0 = int(1e5)+1
x = [0]*n0

n = int(input())
a0 = list(map(int,input().split()))
q = int(input())
bcs = []
for i in range(q):
    bcs.append(list(map(int,input().split())))

for a in a0:
    x[a] += 1
sum0 = sum(a0)

for bc in bcs:
    sum0 = sum0 + bc[1]*x[bc[0]] - bc[0]*x[bc[0]]
    x[bc[1]] += x[bc[0]]
    x[bc[0]] = 0
    print(sum0)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[]
for i in range(n):
  if i%2==0:
    b.append(a[i])
  else:
    b.insert(0,a[i])
if n%2==0:
  print(' '.join(map(str, b)))
else:
  print(' '.join(map(str, list(reversed(b)))))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b0=[]
b1=[]
for i in range(n):
  if i%2==0:
    b0.append(a[i])
  else:
    b1.append(a[i])
if n%2!=0:
  b0=list(reversed(b0))
  b=b0+b1
  print(' '.join(map(str, b)))
else:
  b1=list(reversed(b1))
  b=b1+b0
  print(' '.join(map(str, b)))
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))
i, j = 0, 1
while i < len(lst):
    if lst[i] != j:
        lst.pop(i)
    else:
        i += 1
        j += 1

if not lst:
    print(-1)
else:
    print(n - len(lst))


### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))
i = 1
for j in lst:
    if i == j:
        i += 1

print(-1 if i == 1 else n - i + 1)
### BUGGY CODE ###

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
a.append(0)
mod = 10**9+7

dp = [0] * (n+1)
dp[0] = 1

#print(test_a)
for i in range(1, n+1):
    if i in a:
        continue
    dp[i] = dp[i] + dp[i-1]
    if i > 1:
        dp[i] = dp[i] + dp[i-2]

#print(dp)
print(dp[-1]%mod)


### FIXED CODE ###

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

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

stairs = [i for i in range(1, n+1)]
a = [0 for _ in range(m)]
for i in range(m):
  a[i] = int(input())
a = set(a)
  
mod = 10**9+7
dp = [0] * (n+1)
dp[0] = 1

#print(test_a)
for i in range(1, n+1):
    if i in a:
        continue
    dp[i] = dp[i] + dp[i-1]
    if i > 1:
        dp[i] = dp[i] + dp[i-2]

#print(dp)
print(dp[-1]%mod)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(N):
    B[i] += A.count(i+1)

#for i in range(N):
    if B[i] > 0:
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for i in range(Q)]
B = [K-Q]*N

for i in range(Q):
    B[A[i]-1] += 1
    
for i in range(N):
#if A.count(i+1) > S :
#      B[i] += S + A.count(i+1)

    if B[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

L, R = map(int, input().split())

m = 2019
for i in range(L, R):
  for j in range(i+1, R+1):
    i %= 2019
    j %= 2019
    m = min(m, i*j % 2019)
    if m == 0: break
      
print(m)
    

### FIXED CODE ###

L, R = map(int, input().split())
 
m = 2019
flag = False
for i in range(L, R):
  for j in range(i+1, R+1):
    m = min(m, i*j % 2019)
    if m == 0: 
      flag = True
      break
  if flag: break
      
print(m)
### BUGGY CODE ###

import collections
import itertools
def main():
    N = int(input())
    A = list(map(int, input().split()))

    for i in range(N):
        coll = collections.Counter(A)
        coll[A[i]] -= 1
        ans = 0
        for j in range(1,N+1):
            c = coll[j]
            if c>1:
                ans += len(list(itertools.combinations([i for i in range(c)],2)))
        print(ans)

main()


### FIXED CODE ###

from operator import mul
from functools import reduce
import collections

def combinations_count(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom

def main():
    N = int(input())
    A = list(map(lambda x:x-1 ,map(int, input().split())))

    coll = collections.Counter(A[1:])
    counter = [0]*N
    comb = [0]*N
    sum1 = 0
    for i in range(N):
        c=coll.get(i,0)
        counter[i] = c
        if c>1:
            comb[i] = combinations_count(c,2)
            sum1 += comb[i]
    print(sum1)

    for i in range(1,N):
        # ボールA[i-1]を復活させて、ボールA[i]を除外
        n = counter[A[i-1]]
        if n>=1:
            sum1 += n
        counter[A[i-1]] += 1
        n = counter[A[i]]
        if n>=2:
            sum1 -= n-1
        counter[A[i]] -= 1
        print(sum1)

main()
### BUGGY CODE ###

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

# R,G,Bのそれぞれのインデックスをリストで取得する
r_index = []
g_index = []
b_index = []
for i in range(len(S)):
  if S[i]=='R':
    r_index.append(i)
  elif S[i]=='G':
    g_index.append(i)
  else:
    b_index.append(i)

#　全組み合わせ(制約1)
rgb_num = len(r_index) * len(g_index) * len(b_index)

# 組み合わせを全探索して、制約2に当てはまるものをカウントする(i, j, k)
ck = 0
for r in r_index:
  for g in g_index:

    # x < y
    if r < g :
      x, y = r, g
    else:
      x,y = g, r
    
    # (i, j, k) = (x, y, b) or (x, b, y) or (b, x, y)
    # (x, y, b)
    i = x
    j = y
    if (j*2 -i) in b_index:
      ck += 1

    # (x, b, y)
    i = x
    k = y
    if (i + k) / 2 in b_index:
      ck += 1

    # (b, x, y)
    j = x
    k = y
    if (j*2 -k) in b_index:
      ck += 1

print(rgb_num - ck)

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(S)

ans = cnt['R'] * cnt['G'] * cnt['B']

for i in range(N):
  for j in range(i+1, N):
    k = j + j - i
    if k < N :
      if (S[i] == S[j]) or (S[j] == S[k]) or (S[k] == S[i]) :
        continue
      ans -= 1

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

h,w=map(int,input().split())
L=[]
for inp in range(h):
    L.append(input())
#print(L)

#left
grid_l=[]
for y in range(h):
    grid_l.append([])
    n=0
    for x_chr in L[y]:
        if x_chr=="#":
            n=0
        else:
            n+=1
        grid_l[y].append(n)
    
#print(grid_l)

grid_r=[]
for y in range(h):
    grid_r.append([])
    n=0
    for x_chr in L[y][::-1]:
        if x_chr=="#":
            n=0
        else:
            n+=1
        grid_r[y].append(n)
    grid_r[y].reverse()
    
#print(grid_r)

grid_u=[]
for y in range(h):
    grid_u.append([])
for x in range(w):
    n=0
    for y in range(h):
        if L[y][x]=="#":
            n=0
        else:
            n+=1
        grid_u[y].append(n)

#print(grid_u)

grid_d=[]
for y in range(h):
    grid_d.append([])
for x in range(w):
    n=0
    for y in range(h):
        if L[h-y-1][x]=="#":
            n=0
        else:
            n+=1
        grid_d[h-y-1].append(n)

#print(grid_d)

def score(x,y):
    sc=grid_l[y][x]+grid_r[y][x]+grid_u[y][x]+grid_d[y][x]
    return sc

grid=[]
res=0
for y in range(h):
    for x in range(w):
        res=max(res,score(x,y))
#print(grid)
print(max(res-3,0))
        

### FIXED CODE ###

h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())

tab=[[0 for i in range(w)] for q in range(h)]

cnt=0
for i in range(h):
    cnt=0
    for q in range(w):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for i in range(h):
    cnt=0
    for q in range(w-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt

print(max([max(col) for col in tab])-3)
### BUGGY CODE ###

import numpy as np
import math

a = [1, 10, 100, 1000, 1924, 1069, 595, 1912, 949, 1414, 7, 70, 700, 943, 1354, 1426, 127, 1270, 586, 1822, 49, 490,
     862, 544, 1402, 1906, 889, 814, 64, 640, 343, 1411, 1996, 1789, 1738, 1228, 166, 1660, 448, 442, 382, 1801, 1858,
     409, 52, 520, 1162, 1525, 1117, 1075, 655, 493, 892, 844, 364, 1621, 58, 580, 1762, 1468, 547, 1432, 187, 1870,
     529, 1252, 406, 22, 220, 181, 1810, 1948, 1309, 976, 1684, 688, 823, 154, 1540, 1267, 556, 1522, 1087, 775, 1693,
     778, 1723, 1078, 685, 793, 1873, 559, 1552, 1387, 1756, 1408, 1966, 1489, 757, 1513, 997, 1894, 769, 1633, 178,
     1780, 1648, 328, 1261, 496, 922, 1144, 1345, 1336, 1246, 346, 1441, 277, 751, 1453, 397, 1951, 1339, 1276, 646,
     403, 2011, 1939, 1219, 76, 760, 1543, 1297, 856, 484, 802, 1963, 1459, 457, 532, 1282, 706, 1003, 1954, 1369, 1576,
     1627, 118, 1180, 1705, 898, 904, 964, 1564, 1507, 937, 1294, 826, 184, 1840, 229, 271, 691, 853, 454, 502, 982,
     1744, 1288, 766, 1603, 1897, 799, 1933, 1159, 1495, 817, 94, 940, 1324, 1126, 1165, 1555, 1417, 37, 370, 1681, 658,
     523, 1192, 1825, 79, 790, 1843, 259, 571, 1672, 568, 1642, 268, 661, 553, 1492, 787, 1813, 1978, 1609, 1957, 1399,
     1876, 589, 1852, 349, 1471, 577, 1732, 1168, 1585, 1717, 1018, 85, 850, 424, 202]

length = 224
mod = 2019
cont = [0 for _ in range(length)]
sums = [0 for _ in range(length)]
count = 0
s = list(map(int, input()))
s.reverse()
n = len(s)
for i in range(n):
    m = s[i]
    for j in range(min(i + 1, length)):
        sums[j] += m * a[(i-j) % length]
        if i > j:
            sums[j] %= mod
            if i % length == j:
                if sums[j - 1] == 0:
                    cont[j] += 1
                else:
                    cont[j] = 0
            if sums[j] == 0:
                count += cont[j] + 1
print(count)


### FIXED CODE ###

s = input()
n = len(s)
table = [0 for _ in range(n + 1)]
for i in range(n):
    table[-2 - i] = (int(s[-1 - i]) * pow(10, i, 2019) + table[-1 - i]) % 2019
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort()
    F.sort(reverse=True)
    r = A[-1]*F[0]
    l = -1
    while(r-l > 1):
        tmp = (l+r)//2
        k = 0
        for x, y in zip(A, F):
            if x*y > tmp:
                k += x - (tmp // y)
            #k += max(0, x - (tmp // y))
        if K >= k:
            r = tmp
        else:
            l = tmp
    print(r)
main()


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
data_x = [0]*N
res = [0]*N

def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  return data

def ruiseki_f(y, k):
  ruiseki = [0]*k
  ruiseki[0] = y[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + y[i+1]
  return ruiseki

for i in range(K):
  Flag = False
  data_x = imosu(List,N)
  List = ruiseki_f(data_x,N)
  if List.count(N) == N:
      Flag = True
  #print(Flag)
  if Flag:
    break
res = List
print(*res)

### FIXED CODE ###

N,K=map(int,input().split())
List = list(map(int, input().split()))
 
def imosu(x,k):
  data = [0]*k
  for i in range(k):
    first = i-x[i]
    last = i+x[i]
    if first < 0:
      first = 0
    data[first] += 1
    if last+1 < k:
      data[last+1] +=-1
  ruiseki = [0]*k
  ruiseki[0] = data[0]
  for i in range(k-1):
    ruiseki[i+1] = ruiseki[i] + data[i+1]
  return ruiseki
 
for i in range(K):
  List = imosu(List,N)
  if List.count(N) == N:
    break
print(*List)
### BUGGY CODE ###

#!/usr/bin/env python3

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

count = 0
for i in range(N):
    flag = True
    for j in range(i):
        if flag == False:
            break
        if P[i] > P[j]:
            flag = False
    if flag:
        count += 1

print(count)


### FIXED CODE ###

#!/usr/bin/env python3

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

count = 0
min_prev = P[0] + 1
for i in range(N):
    if P[i] < min_prev:
        min_prev = P[i]
        count += 1

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

X, Y = map(int, input().split(' '))

i = min(X, Y)
cond = False
if X != Y:
    while i <= 1000000000:
        if (i % X) == 0:
            if (i % Y) != 0:
                cond = True
                break
        i += 1

if cond:
    print(i)
else:
    print(-1)

### FIXED CODE ###

X, Y = map(int, input().split(' '))

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

if X < Y:
    print(X)
elif X % Y == 0:
    print(-1)
elif gcd(X, Y) == 1:
    print(X)
else:
    tmp = X * gcd(X, Y)
    if tmp % Y != 0:
        print(tmp)
    else:
        print(X * int(X / gcd(X, Y)))
### BUGGY CODE ###

a, b = map(int, input().split())                                                                               

ans = 0 
for i in range(a, b+1):
    ans ^= i
print(ans)

### FIXED CODE ###

a, b = map(int, input().split())                                                                               

ans = 0 
def f(n):
    if n % 2 == 1:
        num_pairs = (n + 1) // 2
        return num_pairs % 2 
    else:
        num_pairs = (n + 1) // 2
        return (num_pairs % 2) ^ n 

print(f(a-1) ^ f(b))