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

def resolve():
  N = int(input())
  X = input()

  for i in range(N):
    tar_X = list(X)
    tar_X[i] = "0" if tar_X[i] == "1" else "1"
    target_int = int(''.join(tar_X), 2)
    count = 0
    while target_int != 0:
      num_of_1 = bin(target_int).count("1")
      tmp = target_int % num_of_1
      # print("{0} % {1} = {2}".format(target_int, num_of_1, tmp))
      target_int = tmp
      count += 1
    print(count)

if __name__ == "__main__":
  resolve()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

h,n= map(int, input().split())
p = []
for i in range(n):
  z = list(map(int, input().split()))
  p.append(z)
dp = [0]*(h+10**4)
for i in range(1,h+10**4):
  dp[i] = min(dp[i-a] + b for a,b in p)
print(min(dp[h:]))

### FIXED CODE ###

import numpy as np
h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
np_ab = np.array(ab)
max_a = max(np_ab[:, 0])
dp = [0]*(h+max_a)
for i in range(1, h+max_a):
    dp[i] = min(dp[i-a] + b for a,b in ab)
print(min(dp[h:]))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import functools

MOD = 10**9 + 7  # type: int

def solve(N: int, K: int):
    def C(n: int, r: int):
        mul = lambda x, y: x * y
        fact1 = functools.reduce(mul, range(n-r+1, n+1), 1)
        fact2 = functools.reduce(mul, range(1, r+1), 1)
        return (fact1 // fact2) % MOD

    for i in range(1, K+1):
        a = C(N-K+1, i)
        b = C(K-1, i-1)
        print((a*b) % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
from math import factorial
from operator import mul

MOD = 10**9 + 7  # type: int

def solve(N: int, K: int):
    facts = [1] * (N+1)
    for i in range(2, N+1):
        facts[i] = facts[i-1] * (i)

    def C(n: int, r: int):
        upper = facts[n]
        lower = facts[r] * facts[n-r]
        return (upper // lower) % MOD

    for i in range(1, K+1):
        a = C(N-K+1, i)
        b = C(K-1, i-1)
        print((a*b) % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

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

s = input()

n = len(s)
amari = [0] * 2019
amari[0] += 1

for i in range(n):
    amari[int(s[n-i-1:]) % 2019] += 1

ans = 0
for i in amari:
    ans += i * (i - 1) // 2

print(ans)

### FIXED CODE ###

s = input()

n = len(s)
amari = [0] * 2019
amari[0] += 1
tmp = 0
digit = 1
for i in range(n):
    tmp += int(s[n-i-1]) * digit
    tmp %= 2019
    amari[tmp] += 1
    digit = (digit * 10) % 2019

ans = 0
for i in amari:
    ans += i * (i - 1) // 2

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

import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    S = input().strip()[::-1]
    MOD = 2019
    T = [0, int(S[0])]
    for d, s in enumerate(S):
        if d == 0:
            continue
        tmp = int(s) * (10**d)
        T.append((T[-1] + tmp) % MOD)

    # print(T)

    cT = Counter(T)
    # print(cT)
    ans = 0
    for k in T:
        cT[k] -= 1
        ans += cT[k]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


def inpl():
    return list(map(int, input().split()))


def main():
    S = input().strip()[::-1]
    MOD = 2019
    T = [0, int(S[0])]
    t10 = 1
    for s in S[1:]:
        t10 *= 10
        t10 %= MOD
        T.append((T[-1] + int(s) * t10) % MOD)

    # print(T)

    cT = Counter(T)
    # print(cT)
    ans = 0
    for k in T:
        cT[k] -= 1
        ans += cT[k]
    print(ans)


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

import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=dis_l[V-1]+v1
            dis_l[v0-1]=dis
            q.append((v0,V))
            break
        else:
            q.pop()
    return dis_l


log=Graph()
ans=dfs(log,1,-1)

for i in ans:
    if i%2==0:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())

#グラフの連結成分を調べる
def Graph():
    G=[[] for i in range(n)]
    #up_G=[0]*n#up_G[i]=頂点iの親
    for i in range(n-1):
        a,b,c=map(int,input().split())
        c=0 if c%2==0 else 1
        G[a-1].append((b,c))
        G[b-1].append((a,c))
    return G

#木上のDFSテンプレ
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    dis=0
    dis_l=[-1]*n
    dis_l[0]=0
    while q:
        V,P=q.pop()
        for new_v in G[V-1]:
            v0,v1=new_v
            #new_vが頂点の時はアウト
            if v0==P:continue
            if dis_l[v0-1]>=0:continue
            dis=(dis_l[V-1]+v1)%2
            dis_l[v0-1]=dis
            q.append((v0,V))

    return dis_l


log=Graph()
ans=dfs(log,1,-1)
print(*ans,sep='\n')
### BUGGY CODE ###

import itertools
[N, K] = [int(i)  for i in input().split()]
price = [int(i)  for i in input().split()]
select_sum = sum(price)
for select  in itertools.combinations(price, K):
    if sum(select) < select_sum:
        select_sum = sum(select)
print(select_sum)

### FIXED CODE ###

import itertools
[N, K] = [int(i)  for i in input().split()]
price = [int(i)  for i in input().split()]
price.sort()
sum = 0
for i in range(K):
    sum += price[i]
print(sum)
### BUGGY CODE ###

n, cap = map(int, input().split())
val =[0]*(cap+1)
for _ in range(n):
    w, v = map(int, input().split())
    for wk in range(cap,w-1,-1):
        val[wk]=max(val[wk],val[wk-w]+v)
print(val[-1])


### FIXED CODE ###

import sys
input=sys.stdin.readline

n, cap = map(int, input().split())
val =[0]*(cap+1)
def nap(n,cap):
    for _ in range(n):
        w, v = map(int, input().split())
        for wk in range(cap,w-1,-1):
            nv=val[wk-w]+v
            if val[wk]<nv:
                val[wk]=nv
    return max(val)
print(nap(n,cap))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline().rstrip()

def dfs(v,p=-1):
  for u in graph[v]:
    if u == p: continue
    ans[u] += ans[v]
    dfs(u,v)

N,Q = map(int,input().split())
graph = [[] for i in range(N+1)]
ans = [0 for i in range(N+1)]
for _ in range(N-1):
  a,b = map(int,input().split())
  graph[a].append(b)
  graph[b].append(a)

for _ in range(Q):
  p, x = map(int,input().split())
  ans[p] += x

dfs(1)
print(*ans[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input=lambda :sys.stdin.readline()

def sol():

  N,Q = map(int,input().split())
  graph = [[] for i in range(N)]
  ans = [0 for i in range(N)]
  for _ in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

  for _ in range(Q):
    p, x = map(int,input().split())
    ans[p-1] += x 
 
  def dfs(v,p=-1):
    for u in graph[v]:
      if u == p: continue
      ans[u] += ans[v]
      dfs(u,v)
  dfs(0)
  print(*ans)

sol()
### BUGGY CODE ###

N,*S=open(0).read().split()
ans=0
def is_anagram(a,b):
    a = sorted(a)
    b = sorted(b)
    return True if a==b else False

for i in range(len(S)):
    for j in range(i+1,len(S)):
        if is_anagram(S[i],S[j]):
            ans +=1
print(ans)

### FIXED CODE ###

import collections
N=int(input())
S = collections.Counter([''.join(sorted(input())) for i in range(N)])
print(sum(map(lambda x: x*(x-1)//2, S.values())))
### BUGGY CODE ###

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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    S = list(map(int, input().split()))
    odd = {}
    even = {}
    for i in range(N):
        if i % 2 == 0:
            if S[i] not in even:
                even[S[i]] = 1
            else:
                even[S[i]] += 1
        else:
            if S[i] not in odd:
                odd[S[i]] = 1
            else:
                odd[S[i]] += 1

    n = 1000000000
    for ek, ev in even.items():
        for ok, ov in odd.items():
            if ek == ok:
                n = min(n, N - max(even[ek], odd[ok]))
            else:
                n = min(n, N - even[ek] - odd[ok])
    print(n)

main()


### FIXED CODE ###

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

import sys

input = sys.stdin.readline

def main():
    N = int(input())
    S = list(map(int, input().split()))
    odd = {}
    even = {}
    for i in range(N):
        if i % 2 == 0:
            if S[i] not in even:
                even[S[i]] = 1
            else:
                even[S[i]] += 1
        else:
            if S[i] not in odd:
                odd[S[i]] = 1
            else:
                odd[S[i]] += 1

    n = 1000000000
    emk = None
    ev1 = None
    ev2 = 0
    for ek, ev in even.items():
        if emk is None:
            emk = ek
            ev1 = ev
        elif ev > ev1:
            emk = ek
            ev2 = ev1
            ev1 = ev
        elif ev > ev2:
            ev2 = ev

    omk = None
    ov1 = None
    ov2 = 0
    for ok, ov in odd.items():
        if omk is None:
            omk = ok
            ov1 = ov
        elif ov > ov1:
            omk = ok
            ov2 = ov1
            ov1 = ov
        elif ov > ov2:
            ov2 = ov

    if emk != omk:
        n = min(n, N - ev1 - ov1)
    else:
        n = min(n, N - ev1 - ov2, N - ev2 - ov1)

    print(n)

main()
### BUGGY CODE ###

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

for num in A:
    ans *= num

if ans > 1e18:
    ans = -1

print(ans)

### FIXED CODE ###

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

if 0 in A:
    ans = 0
else:
    for num in A:
        ans *= num
        if ans > 1e18:
            ans = -1
            break

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

x = int(input())
t = 1
ds = {0}
while True:
    dc = ds.copy()
    for d in dc:
        if d + t == x or d - t == x:
            break
        ds.add(d + t)
        ds.add(d - t)
    else:
        t += 1
        continue
    break

print(t)


### FIXED CODE ###

from math import ceil, sqrt

x = int(input())
print(ceil((-1 + sqrt(8 * x + 1)) / 2))
### BUGGY CODE ###

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [calc_dice_score(p) for p in p_list]

score_list = []

for i in range(n- k + 1):
    score_list.append(calc_score(dice_scores[i:i+k]))
print(max(score_list))

### FIXED CODE ###

import collections

def get_input_line():
    return list(map(int, input().split()))
n, k = get_input_line()
p_list = get_input_line()

def calc_dice_score(p):
    return 0.5*(p+1)

def calc_score(score_list):
    return sum(score_list)

dice_scores = [0] * n

max_score = 0
tmp_score = 0

for i in range(k):
    dice_scores[i] = 0.5*(p_list[i]+1)
    tmp_score += dice_scores[i]

max_score = tmp_score
for i in range(1, n- k + 1):
    dice_scores[i+k-1] = 0.5*(p_list[i+k-1]+1)
    tmp_score -= dice_scores[i-1]
    tmp_score += dice_scores[i+k-1]
    max_score = max(max_score, tmp_score)
print(max_score)
### BUGGY CODE ###

import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
n = int(readline())
A = list(map(lambda x: x.split(), read().decode().split('\n')))

ids = [[0 for j in range(n)] for i in range(n)]

v = 0
for i in range(n):
    for j in range(i, n):
        ids[i][j] = v
        v += 1


# convert match to index-node num
for i in range(n):
    for j in range(n - 1):
        a = i
        b = int(A[i][j]) - 1
        if a > b:
            a, b = b, a
        A[i][j] = ids[a][b]
        
to = [[] for i in range(v)]
for i in range(n):
    for j in range(n - 2):
        to[A[i][j]].append(A[i][j + 1])


visited = [False for i in range(v)]
calculated = [False for i in range(v)]
dp = [0 for i in range(v)]

def dfs(node):
    if visited[node]:
        if not calculated[node]:
            print(-1)
            exit()
        return dp[node]

    visited[node] = True
    dp[node] = 1
    for u in to[node]:
        dp[node] = max(dfs(u) + 1, dp[node])

    calculated[node] = True
    return dp[node]

ans = 0
for i in range(v):
    ans = max(ans, dfs(i))
print(ans)



### FIXED CODE ###

import sys
import itertools
import numpy as np

from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
N = int(readline())
A = [[-1] + [int(x) - 1 for x in row.split()][::-1] for row in readlines()]

# A.append([-1])

def f(cand):
    cand1 = set()
    can_use = []
    for n in cand:
        if A[A[n][-1]][-1] == n:
            can_use.append(n)
    for n in can_use:
        A[n].pop()
        cand1.add(n)
        if A[n][-1] != -1:
            cand1.add(A[n][-1])
    return len(can_use), cand1

answer = 0
rest = N*(N-1)
cand = set(range(N))
while True:
    answer += 1
    x, cand = f(cand)
    if x == 0:
        answer = -1
        break
    rest -= x
    if rest == 0:
        break

print(answer)
### BUGGY CODE ###

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


# エントリーポイント
PARA = {"R": (1, 0, 0), "G": (0, 1, 0), "B": (0, 0, 1)}
PARA2 = {"R": 0, "G": 1, "B": 2}


def main():
    N, S = input(int, str)
    count = [(0, 0, 0)]
    for s in reversed(S):
        left = count[-1]
        count.append(((left[0] + PARA[s][0]),
                      (left[1] + PARA[s][1]),
                      (left[2] + PARA[s][2])))
    count.reverse()
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] == S[j]:
                continue
            last = ({"R", "G", "B"} - {S[i], S[j]}).pop()
            ans += count[j + 1][PARA2[last]]
            if ((j * 2 - i < N) and S[j * 2 - i] == last):
                ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()


### FIXED CODE ###

from collections import deque, Counter as cnt
from collections import defaultdict as dd
from operator import itemgetter as ig
from bisect import bisect_right as bsr
from math import factorial, ceil, floor
import sys
sys.setrecursionlimit(1000000)

# お約束
args = None
INF = float("inf")
MOD = int(1e9 + 7)


def input(*ps):
    if type(ps[0]) is list:
        return [input(*ps[0][:-1]) for _ in range(ps[0][-1])]
    elif len(ps) == 1:
        return ps[0](next(args))
    else:
        return [p(next(args)) for p in ps]


def nlist(n, v):
    if not n:
        return [] if type(v) is list else v
    return [nlist(n[1:], v) for _ in range(n[0])]


# エントリーポイント
PARA = {"R": (1, 0, 0), "G": (0, 1, 0), "B": (0, 0, 1)}
PARA2 = {"R": 0, "G": 1, "B": 2}


def main():
    N, S = input(int, str)
    count = [(0, 0, 0)]
    for s in reversed(S):
        left = count[-1]
        count.append(((left[0] + PARA[s][0]),
                      (left[1] + PARA[s][1]),
                      (left[2] + PARA[s][2])))
    count.reverse()
    ans = 0
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            if S[i] == S[j]:
                continue
            last = ({"R", "G", "B"} - {S[i], S[j]}).pop()
            ans += count[j + 1][PARA2[last]]
            if ((j * 2 - i < N) and S[j * 2 - i] == last):
                ans -= 1
    print(ans)

    return


if __name__ == '__main__':
    args = iter(sys.stdin.read().split())
    main()
### BUGGY CODE ###

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

A.sort()

if (A[0] <= 0 and A[n-1] > 0) or (A[0] < 0 and A[n-1] >= 0):
    print(sum(list(map(abs, A))))
    while A[-2] >= 0:
        atama = A.pop(0)
        ketu = A.pop(-1)
        print(atama, ketu)
        new = atama - ketu
        A.insert(0, new)
    while len(A) != 1:
        atama = A.pop(0)
        ketu = A.pop(-1)
        print(ketu, atama)
        new = ketu - atama
        A.append(new)
elif A[0] > 0:
    atama = A.pop(0)
    tugi = A.pop(0)
    new = atama - tugi
    A.insert(0, new)
    print(sum(list(map(abs, A))))
    print(atama, tugi)
    while len(A) != 2:
        atama = A.pop(0)
        ketu = A.pop(-1)
        print(atama, ketu)
        new = atama - ketu
        A.insert(0, new)
    atama = A.pop(0)
    ketu = A.pop(-1)
    print(ketu, atama)
else:
    ketu = A.pop(-1)
    tugi = A.pop(-1)
    new = ketu - tugi
    A.append(new)
    print(sum(list(map(abs, A))))
    print(ketu, tugi)
    while len(A) != 1:
        atama = A.pop(0)
        ketu = A.pop(-1)
        print(ketu, atama)
        new = ketu - atama
        A.append(new)

### FIXED CODE ###

from collections import deque

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

A.sort()
A_d = deque(A)

if (A_d[0] <= 0 and A_d[n-1] > 0) or (A_d[0] < 0 and A_d[n-1] >= 0):
    print(sum(list(map(abs, A_d))))
    while A_d[-2] >= 0:
        atama = A_d.popleft()
        ketu = A_d.pop()
        print(atama, ketu)
        new = atama - ketu
        A_d.appendleft(new)
    while len(A_d) != 1:
        atama = A_d.popleft()
        ketu = A_d.pop()
        print(ketu, atama)
        new = ketu - atama
        A_d.append(new)
elif A_d[0] > 0:
    atama = A_d.popleft()
    tugi = A_d.popleft()
    new = atama - tugi
    A_d.appendleft(new)
    print(sum(list(map(abs, A_d))))
    print(atama, tugi)
    while len(A_d) != 2:
        atama = A_d.popleft()
        ketu = A_d.pop()
        print(atama, ketu)
        new = atama - ketu
        A_d.appendleft(new)
    atama = A_d.popleft()
    ketu = A_d.pop()
    print(ketu, atama)
else:
    ketu = A_d.pop()
    tugi = A_d.pop()
    new = ketu - tugi
    A_d.append(new)
    print(sum(list(map(abs, A_d))))
    print(ketu, tugi)
    while len(A_d) != 1:
        atama = A_d.popleft()
        ketu = A_d.pop()
        print(ketu, atama)
        new = ketu - atama
        A_d.append(new)
### BUGGY CODE ###

p = 10**9+7
def pow(x,m):
    if m==0:
        return 1
    if m==1:
        return x
    if m%2==0:
        return (pow(x,m//2)**2)%13
    else:
        return (x*(pow(x,(m-1)//2)**2)%13)%13
S = input().strip()
n = len(S)
A = [0 for _ in range(n)]
for i in range(n):
    A[i] = pow(10,i)
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if S[i]!="?":
            a = int(S[i])
            b = (a*A[n-1-i])%13
            dp[i+1][j] = dp[i][(j-b)%13]
        else:
            for k in range(10):
                b = (k*A[n-1-i])%13
                dp[i+1][j] = (dp[i+1][j]+dp[i][(j-b)%13])%p
print(dp[n][5])

### FIXED CODE ###

p = 10**9+7
S = input().strip()
n = len(S)
dp = [[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(13):
        if S[i]!="?":
            dp[i+1][(10*j+int(S[i]))%13] = dp[i][j]
        else:
            for k in range(10):
                dp[i+1][(10*j+k)%13] = (dp[i+1][(10*j+k)%13]+dp[i][j])%p
print(dp[n][5])
### BUGGY CODE ###

s=input()
l=len(s)
se=dict()
for i in range(l):
    k=int(s[i:l])%2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

### FIXED CODE ###

s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    #print(0)
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)
### BUGGY CODE ###

n = int(input())
adjacency_list = [list(map(int, input().split())) for i in range(n)]
egde = []
for u in range(n):
    for v in range(u):
        egde.append([adjacency_list[u][v], u, v])
egde.sort()

ans = 0
for d, u, v in egde:
    for w in range(n):
        if w == u or w == v:
            continue
        d2 = adjacency_list[u][w] + adjacency_list[w][v]
        if d > d2:
            print(-1)
            exit()
        elif d == d2:
            break
    else:
        ans += d

print(ans)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))