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

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
before_first_dup_num = A.index(dup_num)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = 0
    for first_rem in range(k):
        before_first_rem = F.comb(
            before_first_dup_num, first_rem) if before_first_dup_num >= first_rem else 0
        after_dup_rem = F.comb(
            after_dup_num, k-1-first_rem) if after_dup_num >= k-1-first_rem else 0
        rem_pattern += before_first_rem*after_dup_rem
    print((all_pattern-rem_pattern+MOD) % MOD)


### FIXED CODE ###

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


import sys


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

n = int(input())
N = n+1
A = list(map(int, input().split()))
MOD = 10**9+7
already = set()
for i, l in enumerate(A):
    if l in already:
        dup_ind = i
        dup_num = l
        break
    else:
        already.add(l)
before_first_dup_num = A.index(dup_num)
after_dup_num = N-dup_ind-1

F = FactMod(n+1, MOD)
for k in range(1, n+2):
    all_pattern = F.comb(N, k)
    rem_pattern = F.comb(before_first_dup_num+after_dup_num,
                         k-1) if before_first_dup_num+after_dup_num >= k-1 else 0
    print((all_pattern-rem_pattern+MOD) % MOD)
### BUGGY CODE ###

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

ans=N
for n in range(1,41):
    for i in range(2*n,int(N**(1/n))+100):
        test=i+n*A
        q=i//n
        r=i%n
        prod=pow(q,n-r)*pow(q+1,r)
        test+=(N-1)//prod+1
        ans=min(ans,test)

print(ans)


### FIXED CODE ###

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

ans=N

for i in range(-10,10):
    x=int(N**.5)+i
    if x>0:
        test=x+A+(N-1)//x+1
        ans=min(ans,test)

for n in range(2,41):
    for i in range(2*n,int(N**(1/n))+1000):
        test=i+n*A
        q=i//n
        r=i%n
        prod=pow(q,n-r)*pow(q+1,r)
        test+=(N-1)//prod+1
        ans=min(ans,test)

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

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')
N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))


### FIXED CODE ###

N, W=map(int, input().split())
WV=[list(map(int, input().split())) for i in range(N)]
dp = [-1] * (W+1)
dp[0] = 0
for w, v in WV:
    for i in range(W, w-1, -1):
        if dp[i-w] == -1:
            continue
        dp[i] = max(dp[i], dp[i-w] + v)
print(max(dp))
### BUGGY CODE ###

FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]


dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    
N = rri()
num = int('0b'+rr(),2)
for i in range(N):
    cur_num = num ^ (1<<(N-i-1))
    print(f(cur_num))

### FIXED CODE ###

FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()

    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]
N = rri()

num = list(rr())
count = num.count('1')
pwrTwo_plus = [0] * N 
pwrTwo_plus[0] = 1 % (count+1)
if count>1:
    pwrTwo_minus = [0] * N 
    pwrTwo_minus[0] = 1 % (count-1)  
for i in range(1, N):  
    pwrTwo_plus[i] = pwrTwo_plus[i - 1] * (2 % count)  
    pwrTwo_plus[i] %= count+1
    if count>1:
        pwrTwo_minus[i] = pwrTwo_minus[i - 1] * (2 % count)  
        pwrTwo_minus[i] %= count-1

def getMod(_str, n, k, plus) :  
    
    # To store the result  
    res = 0
    i = 0
    j = n - 1
    while (i < n) :  
  
        # If current bit is 1  
        if (_str[j] == '1') :  
  
            # Add the current power of 2  
            if plus:
                res += (pwrTwo_plus[i] )  
                res %= k  
            else:
                res += (pwrTwo_minus[i] )  
                res %= k  
              
        i += 1
        j -= 1
  
    return res  
dic = {}
def f(x):
    if x in dic:
        return dic[x]
    if x== 0:
        return 0
    tmp = x% bin(x).count('1')
    dic[x] = f(tmp)+1
    return dic[x]
    

ans_1 = getMod(num, N, count+1, True)
if count>1:
    ans_2 = getMod(num, N, count-1, False)
for i in range(N):
    if num[i] =='0':
        cur_count = count+1
    else:
        cur_count =count-1
    if cur_count ==0:
        print(0)
    else:
        if num[i] =='0':
            cur_num = ans_1
            cur_num += pwrTwo_plus[N-1-i]
            cur_num %= cur_count
            print(f(cur_num)+1)
        else:
            cur_num = ans_2
            cur_num -=pwrTwo_minus[N-1-i] 
            cur_num %= cur_count
            print(f(cur_num)+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2000000)
n = int(input())
a=[[]for i in range(n)]
for i in range(n-1):
  x = int(input())
  x-=1
  a[x].append(i+1)
  
dp=[0]*n
huka = [0]*n
def dfs(x,y):
  huka[x]=y
  for i in a[x]:
    dfs(i,y+1)
dfs(0,0)
ya = []
for i in range(n):
  ya.append([huka[i],i])
ya.sort()
ya=ya[::-1]
for i in range(n):
  bb=ya[i][1]
  tmp=[]
  for j in a[bb]:
    tmp.append(dp[j])
  tmp.sort()
  tmp=tmp[::-1]
  for i in range(1,len(tmp)+1):
    tmp[i-1]+=i
  if tmp==[]:
    tmp.append(0)
  dp[bb]=max(tmp)
print(dp[0])

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)
n = int(input())
a=[[]for i in range(n)]
for i in range(n-1):
  x = int(input())
  x-=1
  a[x].append(i+1)
  
dp=[0]*n
ya = [[0,i] for i in range(n)]
def dfs(x,y):
  ya[x][0]=y
  for i in a[x]:
    dfs(i,y+1)
dfs(0,0)
ya.sort(key=lambda x:-x[0])
tmp=[]
for i in range(n):
  bb=ya[i][1]
  for j in a[bb]:
    tmp.append(dp[j])
  tmp.sort(key=lambda x:-x)
  dai =0
  for j in range(len(tmp),0,-1):
    cc=tmp.pop()
    cc+=j
    dai=max(dai,cc)
  dp[bb]=dai
print(dp[0])
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(input())
a = []
ape = 1
for i in range(1,n):
     if p[i-1] != p[i]:
          a.append(ape)
          ape = 1
     else:
          ape += 1
a.append(ape)

def count(a,k,i,start):#start = p[0],a[i]からスタート
     ans = 0
     if start == '1':
          if i%2 == 0:
               for j in range(2*k+1):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
          else:
               for j in range(2*k):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
     else:
          if i%2 == 1:
               for j in range(2*k+1):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
          else:
               for j in range(2*k):
                    if i+j>=len(a):
                         break
                    ans += a[i+j]
     return ans

ans = 0
for i in range(len(a)):
     ans = max(count(a,k,i,p[0]), ans)
print(ans)

### FIXED CODE ###

#参考　https://atcoder.jp/contests/abc124/submissions/4948803
from itertools import accumulate

n, k = map(int,input().split())
p = list(input())
a = []
pre = '1'
cnt = 0
for i in range(n):
     if pre != p[i]:
          a.append(cnt)
          cnt = 1
          pre = p[i]
     else:
          cnt += 1
a.append(cnt)
if pre == '0':
     a.append(0)

w = 2*k+1

if w >= len(a):
     print(n)
else:
     acc = list(accumulate(a))
     ans = 0
     acc = [0] + acc
     for i in range(0,len(a)-w+1,2):
          ans = max(ans,acc[i+w]-acc[i])
     print(ans)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        while p % (2**n) == 0:
            ans *= 2
            p //= (2**n)
        x = 3
        while x**n <= p:
            while p % (x**n) == 0:
                ans *= x
                p //= (x**n)
            x += 2
        print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from math import log
def main():
    n, p = map(int, input().split())
    if n == 1:
        print(p)
    else:
        ans = 1
        if n > int(log(p, 2))+2:
            print("1")
            sys.exit()
        if p % (2**n) == 0:
            while p % (2**n) == 0:
                ans *= 2
                p //= (2**n)
        for i in range(3, 10**6+1, 2):
            while p % (i**n) == 0:
                ans *= i
                p //= (i**n)
        print(ans)

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

N, W = map(int, input().split())
values = [0 for i in range(W)]
for i in range(N):
#  print(values)
  w, v = map(int, input().split())
  values = values[:w-1] + [max(values[j], v + values[max(0, j-w)]) for j in range(w-1, W)]

print(values[-1])

### FIXED CODE ###

N, W = map(int, input().split())
values = [0 for i in range(W)]
for i in range(N):
#  print(values)
  w, v = map(int, input().split())
  values = values[:w-1] + [max(values[j], v + values[max(0, j-w)]) for j in range(w-1, W)]

print(values[-1])
### BUGGY CODE ###

# http://tsutaj.hatenablog.com/entry/2017/03/29/204841
class SegmentTree:
    def __init__(self, v, func, init_val):
        self.func = func
        self.init_val = init_val

        sz = len(v)

        self.n = 1
        while self.n < sz:
            self.n *= 2

        self.node = [self.init_val for _ in range(2 * self.n - 1)]
        # 元配列 v をセグメント木で表現する
        # 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        # セグメント木全体で必要なノード数は 2n - 1 個である

        for i in range(sz):
            self.node[i + self.n - 1] = v[i]
        # 最下段に値を入れたあとに、下の段から順番に値を入れる

        for i in range(self.n - 2, -1, -1):
            self.node[i] = self.func(self.node[2 * i + 1], self.node[2 * i + 2])
        # 値を入れるには、自分の子の 2 値を参照すれば良い

    def update(self, x, val):
        x += self.n - 1
        # 最下段のノードにアクセスする

        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = min(self.node[2 * x + 1], self.node[2 * x + 2])
        # 最下段のノードを更新したら、あとは親に上って更新していく

    # 要求区間 [a, b) 中の要素の最小値を答える
    # k := 自分がいるノードのインデックス
    # 対象区間は [l, r) にあたる

    def get_val(self, a, b, k=0, l=0, r=-1):
        if r < 0: r = self.n
        # 最初に呼び出されたときの対象区間は [0, self.n)

        if r <= a or b <= l: return self.init_val
        # 要求区間と対象区間が交わらない -> 適当に返す

        if a <= l and r <= b: return self.node[k]
        # 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う

        vl = self.get_val(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.get_val(a, b, 2 * k + 2, (l + r) // 2, r)
        return self.func(vl, vr)
        # 要求区間が対象区間の一部を被覆 -> 子について探索を行う
        # 左側の子を vl ・ 右側の子を vr としている
        # 新しい対象区間は、現在の対象区間を半分に割ったもの


def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)


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

st = SegmentTree(v=a, func=gcd, init_val=0)

g = max(gcd(st.get_val(0, drop_idx), st.get_val(drop_idx + 1, N)) for drop_idx in range(N))
print(g)


### FIXED CODE ###

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)


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

g_left = []
g_right = []

t = a[0]
for i in range(N):
    t = gcd(t, a[i])
    g_left.append(t)

t = a[-1]
for i in range(N - 1, -1, -1):
    t = gcd(t, a[i])
    g_right.append(t)

g_right.reverse()

g = 1
for i in range(1, N - 1):
    g = max(g, gcd(g_left[i - 1], g_right[i + 1]))
g = max(g, g_left[N - 2])
g = max(g, g_right[1])

print(g)
### BUGGY CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for i in range(len(ans)):
	if i in A:
		continue
	if(i+1 < len(ans) and i+1 not in A):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and i+2 not in A):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
A = []
for i in range(M):
	curr = int(input())
	A.append(curr)

mod = 1000000007

ans = [0] * (N + 1)

ans[0] = 1

for a in A:
	ans[a] = -1

for i in range(len(ans)):
	if ans[i] == -1:
		continue
	if(i+1 < len(ans) and ans[i+1] != -1):
		ans[i+1] += ans[i]
		ans[i+1] %= mod
	if(i+2 < len(ans) and ans[i+2] != -1):
		ans[i+2] += ans[i]
		ans[i+2] %=mod

print(ans[N])
### BUGGY CODE ###

from collections import defaultdict
from scipy.sparse.csgraph import shortest_path
import numpy as np
N, X, Y = map(int, input().split())
edges = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    edges[i][i + 1] = 1
    edges[i + 1][i] = 1
X -= 1
Y -= 1
edges[X][Y] = 1
edges[Y][X] = 1
res = shortest_path(np.array(edges))
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i+1, N):
        ans[int(res[i][j])] += 1
for k in range(1, N):
    print(ans[k])

### FIXED CODE ###

from collections import defaultdict
N, X, Y = map(int, input().split())
d = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
    for j in range(i+1, N):
        d[i][j] = d[i][j-1] + 1
X -= 1
Y -= 1
for i in range(N-1):
    for j in range(i + 1, N):
        diff = abs(X - i) + abs(Y - j) + 1
        if diff < d[i][j]:
            d[i][j] = diff
#print(d)
ans = defaultdict(int)
for i in range(N-1):
    for j in range(i + 1, N):
        ans[d[i][j]] += 1
for k in range(1, N):
    print(ans[k])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    blocks_table[a-1] += [b-1]
    blocks_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    friend = [i]
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = friends_table[i][:]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

for i in range(N):
    print(len(set(friends_candidate[i]).difference(set(friends_table[i] + blocks_table[i])))-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M, K = map(int, input().split())
friends_table = [[] for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    friends_table[a-1] += [b-1]
    friends_table[b-1] += [a-1]

group_list = [i for i in range(N)]
friends_candidate = [[] for i in range(N)]

for i in range(N):
    # すでにDFS済み
    if i != group_list[i]:
        continue
    next_stack = [i]
    friend = [i]
    while next_stack:
        u = next_stack.pop(-1)
        for v in friends_table[u]:
            # 訪問済み
            if i == group_list[v]:
                continue
            friend += [v]
            group_list[v] = i
            next_stack += [v]
    for f in friend:
        friends_candidate[f] = friend

blocks_table = [[] for i in range(N)]
for _ in range(K):
    a, b = map(int, input().split())
    if group_list[a-1] == group_list[b-1]:
        blocks_table[a-1] += [b-1]
        blocks_table[b-1] += [a-1]

for i in range(N):
    print(len(friends_candidate[i]) - len(friends_table[i]) - len(blocks_table[i])-1)
### BUGGY CODE ###

import collections

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

c = collections.Counter(A)

def count(c, x):
    ret = 0
    for k, v in c.items():
        if k == x:
            v -= 1
        ret += v*(v-1)//2
    return ret

def count_list(c):
    keys = c.keys()
    ret = {}
    for key in keys:
        ret[key] = count(c, key)
    return ret

counts = count_list(c)
for i in range(N):
    print(counts[A[i]])


### FIXED CODE ###

import collections

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

c = collections.Counter(A)

def count_list(c):
    modify = {}
    ret = 0
    for k, v in c.items():
        a = v*(v-1)//2
        b = (v-1)*(v-2)//2
        ret += a
        modify[k] = -a + b
    return ret, modify

counts, modify = count_list(c)
for a in A:
    print(counts + modify[a])
### BUGGY CODE ###

n, m = map(int, input().split(" "))
cards = [0] * n

for i in range(m):
    l, r = map(int, input().split(" "))
    for j in range(l-1, r):
        cards[j] += 1

ans = 0
for card in cards:
    if card == m:
        ans += 1
print(ans)

### FIXED CODE ###

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

s, e = 1, n
for i in range(m):
    l, r = map(int, input().split(" "))
    if s < l: s = l
    if e > r: e = r

print(e-s+1 if s <= e else 0)
### BUGGY CODE ###

def d():
    S = str(input())
    Q = int(input())

    for i in range(Q):
        # print(S)
        q = list(input().split())

        if q[0] == '1':
            if len(S) > 1:
                S = S[::-1]
        elif q[0] == '2':
            if q[1] == '1':
                S = q[2] + S
            elif q[1] == '2':
                S = S + q[2]
            else:
                raise ValueError(
                    'F({}) is {}, which is invalid!'.format(i, q[1]))
        else:
            raise ValueError('T({}) is {}, which is invalid!'.format(i, q[0]))

    print(''.join(S))


##########
d()


### FIXED CODE ###

def d():
    from collections import deque
    S = deque(str(input()))
    Q = int(input())
    rvs = False

    for i in range(Q):
        q = list(input().split())

        if q[0] == '1':
            rvs = not rvs
        elif q[0] == '2':
            if q[1] == '1':
                if rvs:
                    S.append(q[2])
                else:
                    S.appendleft(q[2])
            elif q[1] == '2':
                if rvs:
                    S.appendleft(q[2])
                else:
                    S.append(q[2])
            else:
                raise ValueError(
                    'F({}) is {}, which is invalid!'.format(i, q[1]))
        else:
            raise ValueError('T({}) is {}, which is invalid!'.format(i, q[0]))

    if rvs:
        ans = list(S)[::-1]
    else:
        ans = list(S)
    print(''.join(ans))


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

N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = [[0] * (W+1) for _ in range(N+1)]
for i in range(N):
    w, v = wv[i]
    for j in range(W+1):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])
        if j-w >= 0:
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-w] + v)
print(dp[N][W])

### FIXED CODE ###

import numpy as np
N, W = map(int, input().split())
wv = [map(int, input().split()) for i in range(N)]
dp = np.zeros((N+1, W+1), dtype = np.int)
for i, (w, v) in enumerate(wv):
    dp[i+1] = np.maximum(dp[i+1], dp[i])
    dp[i+1][w:] = np.maximum(dp[i+1][w:], dp[i][:-w] + v)
print(dp[N][W])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for i in set(A):
  dic[i]=A.count(i) 
def ans(k,dic):
  dic[A[k-1]]+=-1
  c=0
  for i in dic.values():
    c+=i*(i-1)/2
  dic[A[k-1]]+=1  
  return int(c)
for k in range(1,N+1):
  print(ans(k,dic))
      

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dic={}
for a in A:
  if a in dic:
    dic[a]+=1
  else:
    dic[a]=1
   

c=0
for i in dic.values():
  c+=i*(i-1)/2
for j in range(1,N+1):
  d=c-dic[A[j-1]]+1
  print(int(d))
### BUGGY CODE ###

N=int(input())
A=[]
for i in range(N):
  S=input()
  A.append(S)
ans=0
for i in range(N):
  x=0
  for j in range(N):
    for k in range(N):      
      if A[j][k-i]!=A[k][j-i]:
        x=1
  if x==0:
    ans+=1
print(ans*N)

### FIXED CODE ###

N=int(input())
A=[]
for i in range(N):
  S=input()
  A.append(S)
ans=0
for i in range(N):
  x=0
  for j in range(N):
    for k in range(N):      
      if A[j][k-i]!=A[k][j-i]:
        x=1
  if x==0:
    ans+=1
print(ans*N)
### BUGGY CODE ###

S = input()[::-1]
MOD = 2019

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

for i,s in enumerate(S):
    r += int(s)*((10**i)%MOD)
    r %= MOD
    C[r] += 1

a = 0
for c in C:
    a += c*(c-1)/2

print(int(a))


### FIXED CODE ###

S = input()[::-1]
MOD = 2019

r = 0
C = [0 for _ in range(MOD)]
C[0] = 1

for i,s in enumerate(S):
    r += int(s)*pow(10,i,MOD)
    r %= MOD
    C[r] += 1

a = 0
for c in C:
    a += c*(c-1)/2

print(int(a))
### BUGGY CODE ###

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

stack=[]
for i in range(len(b)):
    if b[i]==i+1:
        stack.append([[i+1],b[:i]+b[i+1:]])

while len(stack)>0:
    s,c = stack.pop()
    if len(c)==0:
        for i in range(N):
            print(s[-i-1])
        exit()
    for i in range(len(c)):
        if c[i]==i+1:
            stack.append([s+[i+1],c[:i]+c[i+1:]])
print(-1)


### FIXED CODE ###

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

ans=[]

while len(b)>0:
    r=-1
    for i in range(len(b)):
        if b[i]==i+1:
            r=i
    if r==-1:
        print(-1)
        exit()
    ans.append(r+1)
    b=b[:r]+b[r+1:]

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

S = input()
n = len(S)
T = {}
T['0']=1
t = 0
ans = 0
for i in range(n):
    t = (t + (int(S[-i-1]))*(10**i))%2019
    if str(t) in T: T[str(t)] +=1
    else: T[str(t)]=1
for v in T.values():
    ans +=int(( int(v)*(int(v)-1))/2)
print(ans)

### FIXED CODE ###

S = input()
T = [0]*2019
T[0]=1
t = 0
ans = 0
dig = 1
for i in range(len(S)):
    t = (t + (int(S[-i-1]))*dig)%2019
    dig = (dig*10)%2019
    T[t] += 1
for j in T:
    ans +=int(j*(j-1)/2)
print(ans)