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

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
follow = 0
POW = 1

for i in range(N):
  Amari_ = (int(S[N-i-1]) * POW + follow) % 2019
  amari[Amari_] += 1
  follow = Amari_
  POW *= 10
  
ans = sum(list( i * (i-1)//2 for i in amari ))
ans += amari[0]

print(ans)

### FIXED CODE ###

S = str(input())
N = len(S)

ans = 0
amari = [0] * 2019
amari[0] = 1
follow = 0
POW = 1

for i in reversed(S):
  follow += int(i) * POW
  follow %= 2019
  amari[follow] += 1
  POW *= 10
  POW %= 2019
  
print(sum( i * (i-1) // 2 for i in amari ))
### BUGGY CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]<0 and S[data[0]-1][data[1]]=='.':
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]<0 and S[data[0]+1][data[1]]=='.':
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]<0 and S[data[0]][data[1]-1]=='.':
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]<0 and S[data[0]][data[1]+1]=='.':
    q.append([data[0], data[1]+1, data[2]+1])
  return data[2]

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-1]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      tmp=f(data)
      if tmp>out:
        out=tmp
      
print(out)

### FIXED CODE ###

from collections import deque
import sys
def input():
  return sys.stdin.readline()[:-1]

H, W=map(int, input().split())
S=['#'*(W+2)]+['#'+input()+'#' for i in range(H)]+['#'*(W+2)]

def f(data):
  m[data[0]][data[1]]=data[2]
  if m[data[0]-1][data[1]]==-2 and S[data[0]-1][data[1]]=='.':
    m[data[0]-1][data[1]]=-1
    q.append([data[0]-1, data[1], data[2]+1])
  if m[data[0]+1][data[1]]==-2 and S[data[0]+1][data[1]]=='.':
    m[data[0]+1][data[1]]=-1
    q.append([data[0]+1, data[1], data[2]+1])
  if m[data[0]][data[1]-1]==-2 and S[data[0]][data[1]-1]=='.':
    m[data[0]][data[1]-1]=-1
    q.append([data[0], data[1]-1, data[2]+1])
  if m[data[0]][data[1]+1]==-2 and S[data[0]][data[1]+1]=='.':
    m[data[0]][data[1]+1]=-1
    q.append([data[0], data[1]+1, data[2]+1])

out=0
for x in range(1, H+1):
  for y in range(1, W+1):
    if S[x][y]=='#':
      continue
    q=deque()
    q.append([x, y, 0])
    m=[[-2]*(W+2) for i in range(H+2)]
    while len(q)>0:
      data=q.popleft()
      f(data)
      if data[2]>out:
        out=data[2]
      
print(out)
### BUGGY CODE ###

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

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

data = [float('inf')] * (2 * N - 1)

def update(i, val):
    i += N-1
    data[i] = val
    while i > 0:
        i = (i - 1) // 2
        data[i] = min(data[2*i+1], data[i*2+2])

for i in range(N):
    update(i, a[i])

def query(a, b, k, l, r):
    if l <= a and b <= r:
        return data[k]
    elif b <= l or r <= a:
        return float('inf')
    else:
        mid = (a + b) // 2
        lvalue = query(a, mid, 2 * k + 1, l, r)
        rvalue = query(mid, b, 2 * k + 2, l, r)
        return min(lvalue, rvalue)

ans = 0
for l in range(N):
    for r in range(l, N):
        ans += query(0, N, 0, l, r + 1)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python

from collections import defaultdict

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

cnt = 0
d = [0] * (N + 2)
for i in range(N):
    d[a[i]] = i


l = list(range(N + 2))
r = list(range(N + 2))

# print(a)
for i in range(N, 0, -1):
    di = d[i]
    cnt += i * (r[di] - di + 1) * (di - l[di] + 1)
    r[l[di] - 1] = r[di]
    l[r[di] + 1] = l[di]
    # print(i)
    # print(r)
    # print(l)
# print(r)
# print(l)
print(cnt)
### BUGGY CODE ###

# D - Integer Cards
# https://atcoder.jp/contests/abc127/tasks/abc127_d

import sys

n, m = list(map(int, sys.stdin.readline().split()))
cards = list(map(int, sys.stdin.readline().split()))
cards.sort()

combinations = []
for i in range(m):
    combinations.append(list(map(int, sys.stdin.readline().split())))

combinations = sorted(combinations, key=lambda x: x[1])
combinations.reverse()
# c[i]より小さい数があればb[i]枚まで入れ替えていい
for element in combinations:
    cnt = 0
    for i in range(len(cards)):
        if cards[i] < element[1] and cnt < element[0]:
            cards[i] = element[1]
            cnt += 1

print(sum(cards))

### FIXED CODE ###

# D - Integer Cards
# https://atcoder.jp/contests/abc127/tasks/abc127_d

import sys

n, m = list(map(int, sys.stdin.readline().split()))
cards = list(map(int, sys.stdin.readline().split()))

combinations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

cards.sort()
combinations.sort(key=lambda x: x[1], reverse=True)

i = 0
for b, c in combinations:
    for k in range(i, min(n, i + b)):
        if cards[k] < c:
            cards[k] = c
            i += 1
        else:
            break

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

import collections

s = input()

mod = 2019
n = len(s)
t = [0]*(n+1)
for i in range(1,n+1):
    t[i] = (t[i-1] + int(s[n-i]) * (10**(i-1) % mod)) % mod
# t[i-1] == t[j] mod2019　のとき、i番~j番目が2019の倍数
c = collections.Counter(t)
num = c.values()
ans = 0
for i in num:
    ans += i*(i-1) // 2

print(ans)

### FIXED CODE ###

import collections

s = input()

mod = 2019
n = len(s)
t = [0]*(n+1)
for i in range(1,n+1):
    t[i] = (t[i-1] + int(s[n-i]) * pow(10, i-1, mod)) % mod
c = collections.Counter(t)
num = c.values()
ans = 0
for i in num:
    ans += i*(i-1) // 2

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

from collections import deque

n, m, k = map(int, input().split())
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
for _ in range(k):
    c, d = map(int, input().split())
    c, d = c-1, d-1
    l[d].add(c)
    l[c].add(d)

q = deque()
ans = [0] * n
for i in range(n):
    e = [0] * n
    z = [0] * n
    e[i] = 1
    for j in f[i]:
        q.appendleft(j)
        e[j] = 1
    for j in l[i]:
        z[j] = 1
    while q:
        v = q.pop()
        for j in f[v]:
            if e[j] == 0:
                q.appendleft(j)
                e[j] = 1
                if z[j] == 0:
                    ans[i] += 1
print(' '.join(list(map(str, ans))))

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n
    
    def root(self, x):
        if self.parents[x] < 0:
            return x
        else:
            return self.root(self.parents[x])
    
    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return
        else:
            if x > y:
                x, y = y, x
            self.parents[x] += self.parents[y]
            self.parents[y] = x
            return

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

u = UnionFind(n)
f = [set() for _ in range(n)]
l = [set() for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    f[a].add(b)
    f[b].add(a)
    u.unite(a, b)
for c, d in cd:
    c, d = c-1, d-1
    l[c].add(d)
    l[d].add(c)
ans = [0] * n
for i in range(n):
    r = u.root(i)
    bl = 0
    for j in l[i]:
        if u.root(j) == r:
            bl += 1
    ans[i] = -u.parents[r] - len(f[i]) - bl - 1
print(' '.join(list(map(str, ans))))
### BUGGY CODE ###


def main():
    t = input()
    if t == "1":
        print(1)
        exit(0)
    li = [int(v) for v in input().split(' ')]
    s_li = sorted(li)
    count = 0
    ind = 0
    for v in range(s_li[0] - 1, s_li[-1] + 1):
        t_c = 0
        t_c += s_li.count(v - 1)
        t_c += s_li.count(v)
        t_c += s_li.count(v + 1)
        if t_c > count:
            count = t_c
    print(count)



if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
### BUGGY CODE ###

import bisect

n = input()
a = []
n = int(n)

for i in range(n):
    a.append(int(input()))

# それぞれの色の最大値を入れる筒のリスト
t = []

for i in a:
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i)
    # print(i, idx)
    if idx == 0:
        bisect.insort_left(t, i)
    # 効率的な色の探索
    else:
        t[idx-1] = i
    # print(t)

print(len(t))


### FIXED CODE ###

import bisect

n = int(input())
a = [int(input()) for _ in range(n)]
# それぞれの色の最大値を入れる筒のリスト
t = [a[-1]]

for i in reversed(a[:-1]):
    # それぞれの色のどの値よりも小さかったとき
    idx = bisect.bisect_left(t, i+1)
    # print(i, idx)
    if idx == len(t):
        t.append(i)
    # 効率的な色の探索
    else:
        t[idx] = i
    # print(t)

print(len(t))
### BUGGY CODE ###

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

DP = dict()
DP[W] = 0
DPpre = dict()

def maxv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    DPpre, DP = DP, DPpre
    for i in DPpre:
        maxv(i, DPpre[i])
        if i - w >= 0:
            maxv(i-w, DPpre[i]+v)

print(max((DP[x] for x in DP)))


### FIXED CODE ###

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break
### BUGGY CODE ###

n=int(input())
l=list(map(int, input().split()))
tester=True
for i in range(n):
    for j in range(n):
        if i!=j:
            if l[i]==l[j]:
                tester=False
                break
            
if tester==True:
    print('YES')
else:
    print('NO')




### FIXED CODE ###

n=int(input())
l=list(map(int, input().split()))
s=set(l)
if len(l)==len(s):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

for i in range(N):
    print((order.index(i+1))+1, end=' ')

### FIXED CODE ###


N    = int(input())
order=list(map(int,input().split()))
output=[0]*N

for i in range(N):
    output[order[i]-1]=i+1

print(' '.join(map(str,output)))
### BUGGY CODE ###

import copy
def main():
    N,M=map(int,input().split())
    dp=[float("inf") for _ in range(2**N)]
    dp[0]=0
    for _ in range(M):
        a,b=map(int,input().split())
        C=list(map(int,input().split()))
        for v in range(2**N):
            nv=copy.copy(v)
            for c in C:
                bi=2**(c-1)
                if (v//bi)%2==0:
                    nv+=bi
            dp[nv]=min(dp[nv],dp[v]+a)
    if dp[-1]==float("inf"):
        print(-1)
    else:
        print(dp[-1])
main()

### FIXED CODE ###

N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

import sys
from functools import reduce
input = sys.stdin.readline

# python > pypy
MOD = 10**9 + 7
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

lcm_ = a[0]
for i in range(n):
    lcm_ = lcm(lcm_, a[i])

b = list(map(lambda x: lcm_//x, a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

MAX = 1000001

mod = 1000000007

prime = [0 for i in range(MAX)]

max_map = dict()

# function to return a^n

def power(a, n):

    if n == 0:
        return 1
    p = power(a, n // 2) % mod
    p = (p * p) % mod

    if n & 1:
        p = (p * a) % mod
    return p

# function to find the smallest prime
# factors of numbers upto MAX


def sieve():
    prime[0], prime[1] = 1, 1
    for i in range(2, MAX):
        if prime[i] == 0:
            for j in range(i * 2, MAX, i):
                if prime[j] == 0:
                    prime[j] = i
            prime[i] = i

# function to return the LCM modulo M


def lcmModuloM(arr, n):

    for i in range(n):
        num = arr[i]

        temp = dict()

        # temp stores mapping of prime factors
        # to its power for the current element
        while num > 1:

            # factor is the smallest prime
            # factor of num
            factor = prime[num]

            # Increase count of factor in temp
            if factor in temp.keys():
                temp[factor] += 1
            else:
                temp[factor] = 1

            # Reduce num by its prime factor
            num = num // factor

        for i in temp:
            # store the higest power of every prime
            # found till now in a new map max_map
            if i in max_map.keys():
                max_map[i] = max(max_map[i], temp[i])
            else:
                max_map[i] = temp[i]

    ans = 1

    for i in max_map:

        # LCM is product of primes to their
        # higest powers modulo M
        ans = (ans * power(i, max_map[i])) % mod
    return ans


def rep_sqr(base, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 0:
        return (rep_sqr(base, k / 2, mod) ** 2) % mod
    else:
        return (rep_sqr(base, k - 1, mod) * base) % mod

# a^(-1) == a^(m-2)


def flt(a, mod):
    return rep_sqr(a, mod-2, mod)

# Driver code
sieve()

# python > pypy
MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

DP = [[0] * (S+1) for _ in range(N+1)]
Pre = [[[] for _ in range(S+1)] for _ in range(N+1)]

DP[0][0] = 1
Pre[0][0].append([-1])

for i, a in enumerate(A):
    for j in range(S+1):
        b = DP[i][j]
        if b > 0:
            DP[i + 1][j] += DP[i][j]
            for P in Pre[i][j]:
                Pre[i+1][j].append(P)
        if a + j <= S:
            DP[i + 1][j + a] += DP[i][j]
            for P in Pre[i][j]:
                Pre[i + 1][j+a].append(P + [i])
ans = 0
for L in Pre[N][S]:
    ans += pow(2, N - len(L) + 1, mod)
    ans %= mod

print(ans % mod)

### FIXED CODE ###

import numpy as np

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
f = np.zeros(3100, np.int64)

ans = 0
f[0] = 1
for a in A:
    g = f.copy()
    f[a:] += g[:-a]
    f += g
    f %= mod

print(f[S])
### BUGGY CODE ###

m = 1000000007

factorials = [1]

for i in range(1,1000001):
    factorials.append((factorials[-1]*i) % m)

n = int(input())

if n == 1:
    print(0)
else:

    singles = 0
    for i in range(1,n+1):

        comb = (factorials[n] * pow(factorials[n-i],m-2,m) * pow(factorials[i],m-2,m)) % m
        singles += (comb * pow(8,n-i,m)) % m

    temp = pow(10,n,m) - pow(8,n,m) - 2*singles
    print(temp % m)

### FIXED CODE ###

m = 1000000007
 
factorials = [1]
 
for i in range(1,1000001):
    factorials.append((factorials[-1]*i) % m)
 
n = int(input())
 
if n == 1:
    print(0)
else:
    temp = pow(10,n,m) - (2*pow(9,n,m) - pow(8,n,m))
    print(temp % m)
### BUGGY CODE ###


s = input()

n = len(s)

check = [False]*n


rem = 0

# 0 search
for i in range(n):
    if s[i]== '1':
        continue


    # 1 search
    for j in range(n):
        if s[j] == '0':
            continue

        if check[j]:
            continue

        check[i], check[j] = True, True
        rem += 2
        break

print(rem)

        


### FIXED CODE ###


s = input()

n = len(s)

stack = [ s[0] ]

rem = 0
# print(stack)

# 0 search

ss = len(stack)

for i in range(1,n):


    if ss==0 or stack[-1] == s[i]:

        stack.append(s[i])
        ss+=1
        
        continue


    if len(stack) > 0:
        stack.pop()
        ss -= 1

        i+=1
        rem +=2


print(rem)
### BUGGY CODE ###

n = input()
nums = list(input().split(' '))
if [x for x in set(nums) if nums.count(x) > 1]:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

n = input()
nums = list(input().split(' '))
if len(nums) != len(set(nums)):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

n = int(input())
s = input()
lst = [str(a) + str(b) + str(c) for a in range(10) for b in range(10) for c in range(10)]

count = 0
for num in lst:
    pos = 0
    for tmp in s:
        if num[pos] == tmp:
            pos += 1
            if pos == 3:
                count += 1
                break
print(count)


### FIXED CODE ###

n = int(input())
s = input()
lst = ["{:03}".format(i) for i in range(1000)]
count = 0
for num in lst:
    pos = 0
    np = num[pos]
    for tmp in s:
        if np == tmp:
            if pos == 2:
                count += 1
                break
            pos += 1
            np = num[pos]
print(count)
### BUGGY CODE ###

N = int(input())
num_list = list(map(int,input().split()))
q = int(input())

for i in range(q):
  key,rep = map(int,input().split())
  while key in num_list:
    num_list.remove(key)
    num_list.append(rep)
  print(sum(num_list))
    
    

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100001
 
for i in A:
    table[i] += 1
 
for i in range(Q):
    B, C = map(int,input().split())
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    S.append(s)

for s in S:
    print(s)
### BUGGY CODE ###

n,k = map(int,input().split())
while n > k/2:
  n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
m = n
m = m%k
if m > int(k/2):
  ans = abs(m-k)
else:
  ans = m
print(ans)
### BUGGY CODE ###

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

k_idx = K - 1
term_val_arr = []
ans_arr = []
for i in range(N - K + 1):
    val = 1
    for j in range(K):
        val *= a_arr[k_idx - j]
    term_val_arr.append(val)
    if i != 0:
        if term_val_arr[i - 1] < term_val_arr[i]:
            ans_arr.append('Yes')
        else:
            ans_arr.append('No')
    k_idx += 1
for i in ans_arr:
    print(i)

### FIXED CODE ###

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

k_idx = K - 1
ans_arr = []
for i in range(N - K):
    if a_arr[i] < a_arr[k_idx + 1]:
        ans_arr.append('Yes')
    else:
        ans_arr.append('No')
    k_idx += 1
for i in ans_arr:
    print(i)
### BUGGY CODE ###

from sys import stdin

if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    memo = set()
    cnt = 0
    for i in range(len(S)):
        for j in range(i+3,len(S)):
            if j == i+3:
                mod = int(S[len(S)-j-1:len(S)-i])%3
            else:
                mod = (mod+int(S[len(S)-j-1]))%3
            if mod == 0:
                _ = int(S[len(S)-j-1:len(S)-i])
                if _%2019==0:
                    cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

s = input()
t = input()
a = len(s)
b = len(t)
dp = [[""]*(b+1) for _ in range(a+1) ]
for i in range(a):
  for j in range(b):
    if s[i]==t[j]:
      if len (dp[i][j]+s[i])>len(dp[i+1][j+1]):
        dp[i+1][j+1] = dp[i][j]+s[i]
    else:
      if len (dp[i+1][j])>len(dp[i][j+1]):
        dp[i+1][j+1]=dp[i+1][j]
      else:
        dp[i+1][j+1]=dp[i][j+1]
print(dp[a][b])
        

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  ans = []
  ans_append = ans.append
  s = input()
  t = input()
  a = len(s)
  b = len(t)
  dp = [[0]*(b+1) for _ in range(a+1)]
  prev_w = [[None]*(b+1) for _ in range(a+1)]
  for i in range(a):
    for j in range(b):
      if s[i]==t[j]:
        if dp[i][j]+1>dp[i+1][j+1]:
          dp[i+1][j+1] = dp[i][j]+1
          prev_w[i+1][j+1] = (i,j)
      else:
        if dp[i+1][j]>dp[i][j+1]:
          dp[i+1][j+1]=dp[i+1][j]
          prev_w[i+1][j+1] = (i+1,j)
        else:
          dp[i+1][j+1]=dp[i][j+1]
          prev_w[i+1][j+1] = (i,j+1)
  while a!=0 and b !=0:
    l = dp[a][b]
    a,b=prev_w[a][b]
    if l>dp[a][b]:
      ans_append(s[a])
  ans ="".join(ans)
  ans =ans[::-1]
  print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

L, R = map(int, input().split())
ans = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if i * j % 2019 < ans:
            ans = i * j % 2019
        if ans == 0:
            break
print(ans)
            

### FIXED CODE ###

# coding: utf-8
# Your code here!
L, R = map(int, input().split())
ans = 2019
for i in range(L, R):
    for j in range(i + 1, R + 1):
        if i * j % 2019 < ans:
            ans = i * j % 2019
        if ans == 0:
            break
    if ans == 0:
        break
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
koremade = 0
for i in range(N):
  count[i]  = A.count(i + 1)
  koremade += count[i]
  if koremade == N:
    break
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0] * N
for i in range(N):
  count[A[i] - 1]  += 1
  
nanimo = 0 
for i in range(N):
  nanimo += count[i] * (count[i] - 1) // 2
for i in range(N):
  tekito = count[A[i] - 1]
  if tekito == 2:
    s = nanimo - 1
  elif tekito == 1:
    s = nanimo
  else:
    s = nanimo -  ((tekito * (tekito - 1) //2) - ((tekito - 1) * (tekito - 2) //2))
  print(s)
### BUGGY CODE ###

#D
#入力
S=input()
Q=int(input())
#Query=[]
#for i in range(Q):
#    Query.append(list(input().split()))
    
    
#処理
t=0
for j in range(Q):
    i=list(input().split())
    if i[0]=="1":
        t+=1
    elif i[0]=="2":
        if t%2==1:
            S=S[::-1]
        t=0
        if i[1]=="1":
            S=i[2]+S
        elif i[1]=="2":
            S=S+i[2]
if t%2==1:
    S=S[::-1]
print(S)

### FIXED CODE ###

#D
#入力
S=input()
Q=int(input())
#Query=[]
#for i in range(Q):
#    Query.append(list(input().split()))
    
    
#処理
t=0
b=""
a=""
for j in range(Q):
    i=list(input().split())
    if i[0]=="1":
        t+=1
    elif i[0]=="2":
        if t%2==0:
            if i[1]=="1":
                b=i[2]+b
            elif i[1]=="2":
                a=a+i[2]
        elif t%2==1:
            if i[1]=="1":
                a=a+i[2]
            elif i[1]=="2":
                b=i[2]+b
if t%2==0:
    print(b+S+a)
    
else:
    print(a[::-1]+S[::-1]+b[::-1])