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

"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*pow(10,i)%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*pow(10,i)%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
print(dp[-1][5])

### FIXED CODE ###

"""
dp[i][j] => 下からi桁目まで見る。あまりがjになるような数。
"""
mod = 10**9 +7
S = input()
S = S[::-1]
N = len(S)
dp = [[0]*13 for _ in range(N+1)]
dp[0][0] = 1
by = 1
for i in range(N):
    s = S[i]
    for j in range(13):
        if s == "?":
            for k in range(10):
                rest = k*by%13
                dp[i+1][(j+rest)%13] += dp[i][j]
                dp[i+1][(j+rest)%13] %= mod
        else:
            rest = int(s)*by%13
            dp[i+1][(j+rest)%13] += dp[i][j]
            dp[i+1][(j+rest)%13] %= mod
    by = by*10%13
print(dp[-1][5])
### BUGGY CODE ###

import math
Q_SIZE = math.pow(10,5) 
Q = int(input())

Check_Prime = [-1 for i in range(int(Q_SIZE))]
Count_like = [0 for i in range(int(Q_SIZE//2))]

C_Range_L = 0 
C_Range_R = 0

def check_range(L,R):
    for i in range(L,R+1,2):
        if(Check_Prime[i] < 0):
            if isprime(i):
                Check_Prime[i] = 1
                n = int((i+1)/2)
                if(Check_Prime[n] < 0):
                    if(isprime(n)) : 
                        Count_like[i//2] = 1
                elif(Check_Prime[n] == 1):
                    Count_like[i//2] = 1
            else:
                Check_Prime[i] = 0
                
        elif(Check_Prime[i] == 1):
            n = int((i+1)/2)
            if(Check_Prime[n] < 0):
                if(isprime(n)) : 
                    Count_like[i//2] = 1
            elif(Check_Prime[n] == 1):
                Count_like[i//2] = 1

def isprime(n): 
    if n < 2 : return False 
    if n == 2 : return True 
    if n % 2 == 0 : return False

    for i in range(3,int(math.sqrt(n))+1,2):
        if n % i == 0:
            return False
    return True

for i in range(Q): 
    l,r = map(int, input().split())

    if(C_Range_L == 0 and C_Range_R == 0):
        check_range(l,r)
        C_Range_L = l
        C_Range_R = r

    if(C_Range_L > l):
        check_range(l,C_Range_L)
        C_Range_L = l

    if(r > C_Range_R):
        check_range(C_Range_R,r)
        C_Range_R = r

    print(sum(Count_like[l//2:r//2+1]))

### FIXED CODE ###

import math
Q_SIZE = int(math.pow(10,5))
Q = int(input())

Check_Prime = [True for i in range(Q_SIZE+1)]
Count_like = [0 for i in range(Q_SIZE//2)]

Check_Prime[0] = False
Check_Prime[1] = False

for i in range(2,Q_SIZE+1):
    if(Check_Prime[i] == True):
        for j in range(i+i,Q_SIZE+1,i):
            Check_Prime[j] = False
            
for i in range(1,Q_SIZE//2):
    if(Check_Prime[i*2+1] == True and Check_Prime[int(((i*2+1)+1)/2)] == True):
        Count_like[i] = Count_like[i-1] + 1
    else:
        Count_like[i] = Count_like[i-1]

for i in range(Q):
    l,r = map(int,input().split())
    if( l == 1):
        print(Count_like[r//2] - Count_like[l//2])
    else:
        print(Count_like[r//2] - Count_like[l//2 - 1])
### BUGGY CODE ###

N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    c = "BW".index(c); a = int(a)
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + P[i][0]
for i in range(N):
    dp[0][i+1] = dp[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = min(dp[i][j+1] + P[i][j+1], dp[i+1][j] + Q[j][i+1])
print(dp[N][N])


### FIXED CODE ###

from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])
### BUGGY CODE ###

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, T = map(int, input().split())
I = np.array(read().split(), dtype = np.int64)
A = I[::2]
B = I[1::2]

sort_ind = np.argsort(A)
A = A[sort_ind]
B = B[sort_ind]

DP = np.zeros([N-1, T], dtype = np.int64)
DP[0,A[0]:] = B[0]

for i in range(1, N-1):
	for j in range(T):
		if j - A[i] >= 0:
			DP[i,j] = max(DP[i-1, j], DP[i-1,j-A[i]] + B[i])
		else:
			DP[i,j] = DP[i-1,j]

tmp = 0
for i in reversed(range(N)):
	tmp = max(B[i], tmp)
	B[i] = tmp

C = DP[:,T-1] + B[1:]
print(np.max(C))

### FIXED CODE ###

N, T = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
AB.sort(key = lambda x: x[0])

DP = [[0] * T for _ in range(N-1)]

for i in range(N-1):
	for j in range(T):
		if i == 0:
			if j >= AB[0][0]:
				DP[i][j] = AB[0][1]
		else:
			if j >= AB[i][0]:
				DP[i][j] = max(DP[i-1][j], DP[i-1][j-AB[i][0]] + AB[i][1])
			else:
				DP[i][j] = DP[i-1][j]

ans = 0
tmp = 0

for i in reversed(range(N-1)):
	tmp = max(tmp, AB[i+1][1])
	ans = max(ans, DP[i][T-1] + tmp)

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

mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    # ele in cur can choose ele in last which is smaller than it
    # person says i can choose person says i-1 who is in front of him
    # cur and last are naturally increase order
    if len(cur) > len(last):
        a = 0
        while True:
            a += 1 
    ans = 1
    minus = 0
    for i in cur:
        count = 0
        for j in last:
            if j < i:
                count += 1
        ans *= count-minus
        minus += 1
    return ans
    # j = 0
    # ans = 1
    # for i in range(len(cur)):
    #     while j < len(last):
    #         if last[j] < cur[i]:
    #             j += 1
    #         else:
    #             break
    #     ans *= (j-i)
    # return ans

memo.append([-1,-1,-1]) # for convenience
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    # if len(memo[i]) == 1:  # mistake why???
    #     break

print(ans)

### FIXED CODE ###

mo = 1000000007
n = int(input())
A = [int(s) for s in input().split()]
maxLen = 0
for a in A:
    if a > maxLen:
        maxLen = a
maxLen += 1
memo = [[]for i in range(maxLen)]
for index,a in enumerate(A):
    memo[a].append(index)

def calc(cur,last):
    # ele in cur can choose ele in last which is smaller than it
    # person says i can choose person says i-1 who is in front of him
    # cur and last are naturally increase order
    ans = 1
    minus = 0
    for i in cur:
        count = 0
        for j in last:
            if j < i:
                count += 1
        ans *= count-minus
        minus += 1
    return ans
    # j = 0
    # ans = 1
    # for i in range(len(cur)):
    #     while j < len(last):
    #         if last[j] < cur[i]:
    #             j += 1
    #         else:
    #             break
    #     ans *= (j-i)
    # return ans

memo.append([-1,-1,-1]) # for convenience
ans = 1
for i in range(maxLen):
    ans *= calc(memo[i],memo[i-1])
    ans %= mo
    # if len(memo[i]) == 1:
    #     break

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

NK=input().split()
N=int(NK[0])
K=int(NK[1])
Hlis=list(map(int,input().split()))
ans=0

if K>=N:
    print(0)
else:
    for i in range(N-K):
        mini=Hlis.index(min(Hlis))
        ans+=Hlis[mini]
        Hlis.pop(mini)
    print(ans)

### FIXED CODE ###

NK=input().split()
N=int(NK[0])
K=int(NK[1])
Hlis=list(map(int,input().split()))
ans=0

if K>=N:
    print(0)
else:
    Hlis.sort()
    for i in range(N-K):
        ans+=Hlis[i]
    print(ans)
### BUGGY CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


def get_primes(n):
    root_n = int(n ** 0.5)
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, root_n + 1):
        if not is_prime[i]:
            continue
        # i の倍数の素数判定をFalseにする
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]


def a(n):
    return 7 * (1 + ((10**n - 10) // 9))


INF = float('inf')


k = I()
if k % 2 == 0:
    print(-1)
    exit()

ans = 1
while True:
    if a(ans) % k == 0:
        break
    ans += 1
print(ans)


### FIXED CODE ###

import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


k = I()
ans = -1
a = [0] * (k+1)
a[1] = 7 % k
for i in range(2, k+1):
    a[i] = (a[i-1]*10 + 7) % k

for i in range(1, k+1):
    if a[i] == 0:
        print(i)
        exit()
print(-1)
### BUGGY CODE ###

x = int(input())
for i in range(10**8):
    if i**5 == x:
        print(i,0)
        break
    elif i**5 == x-1:
        print(i,-1)
        break
    elif i**5 == x+1:
        print(i,1)

### FIXED CODE ###

import sys
x = int(input())
a = []
b = []
t = 0
for i in range(-1000,1000):
    t = i**5
    a.append([t,i])
    b.append([t,i])
    
for i in a:
    for j in b:
        if i[0]-j[0] == x:
            print(i[1],j[1])
            sys.exit()
### BUGGY CODE ###

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

for i in range(N):ans *= A[i]
 
if ans>10**18:print(-1);
else:print(ans)

### FIXED CODE ###

import sys
N = int(input())
x = list(map(int,input().split()))
 
z = 1
if 0 in x:
  print(0)
  sys.exit()
  
for a in x:
  z = a*z
  if z > 10**18:
    print(-1)
    sys.exit()
  
print(z)
### BUGGY CODE ###

from collections import deque, defaultdict
n, x, y = map(int, input().split())
x -= 1
y -= 1
edges = [[] for _ in range(n)]
edges[x].append(y)
edges[y].append(x)
for i in range(n-1):
    edges[i].append(i+1)
    edges[i+1].append(i)


def bfs(init_v):
    queue = deque([init_v])
    INF = 10**10
    dist = [INF]*n
    dist[init_v] = 0
    while queue:
        v = queue.popleft()
        for v2 in edges[v]:
            if dist[v2] <= dist[v]+1:
                continue
            dist[v2] = dist[v]+1
            dd[dist[v2]] += 1
            queue.append(v2)


dd = defaultdict(int)
for i in range(n):
    bfs(i)

for i in range(1, n):
    print(dd[i]//2)

### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1
GRAPH = [[0]*n for _ in range(n)]

def shortest_path(i, j):
    if i <= x <= y <= j:
        return min(j-i, x-i+j-y+1)
    elif x <= i <= y <= j:
        return min(j-i, i-x+j-y+1)
    elif x <= i <= j <= y:
        return min(j-i, i-x+y-j+1)
    elif i <= x <= j <= y:
        return min(j-i, x-i+y-j+1)
    else:
        return j-i


ans = [0]*(n-1)
for i in range(n):
    for j in range(i+1, n):
        path = shortest_path(i, j)-1
        ans[path] += 1
print(*ans, sep="\n")
### BUGGY CODE ###

from fractions import gcd
# 最小公倍数
def lcm(x, y):
    return x // gcd(x, y) * y

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i]) 


sums = 0
mod = 10 ** 9 + 7
for i in range(N):
    sums += x // A[i]
    sums %= mod

print(sums)


### FIXED CODE ###

from fractions import gcd
# 最小公倍数
def lcm(x, y):
    return x // gcd(x, y) * y

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

x = A[0]
for i in range(N):
    x = lcm(x, A[i]) 


sums = 0
mod = 10 ** 9 + 7
for i in range(N):
    sums += x // A[i]

print(sums % mod)
### BUGGY CODE ###

import sys

from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, n))
# 小さすぎても怒られるので

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

toru = [0] * (n+1)
def dfs(ns, prev, now, toru):
    end = defaultdict(int)
    k = cs[now]
    end[k] = 1
    s = 1 # nowで終わるパスの種類
    for u in ns[now]:
        if u==prev:
            continue
        tmp_end, tmp_toru, tmp_s = dfs(ns, now, u, toru)
        # toruの更新
        for kk, vv in tmp_end.items():
            if kk not in end:
                toru[kk] += vv * s
            else:
                toru[kk] += vv * s + end[kk] * (tmp_s+1) - ((vv+1) * end[kk])
        for kk, vv in end.items():
            if kk not in tmp_end:
                toru[kk] += vv * tmp_s
        # end, sの更新
        end[k] += tmp_s
        for kk,vv in tmp_end.items():
            if k!=kk:
                end[kk] += tmp_end[kk]
        s += tmp_s
    toru[k] += 1
#     print(now, prev, end, toru, s)
    return end, toru, s
end, toru, s = dfs(ns, prev=-1, now=1, toru=toru)

for item in toru[1:]:
    print(item)

### FIXED CODE ###


import sys
# 小さすぎても怒られるので
from collections import defaultdict
n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

cs = [0] + [int(c) for c in input().split()]
ns = defaultdict(set)
for _ in range(n-1):
    a,b = [int(c) for c in input().split()]
    ns[a].add(b)
    ns[b].add(a)

ans = [0] * (n+1) # kを通らないパスの総数
minus = [0] * (n+1) # uの部分木のうち
minus0 = defaultdict(int)
st = {k: [] for k in range(1, n+1)}
nextu = {}
def dfs(u, prev, ans):
    global minus, st, minus0
    k = cs[u]
    st[k].append(u)
    ss = 1
    for v in ns[u]:
        if v==prev:
            continue
        nextu[u] = v
        s = dfs(v, u, ans)
        ss += s
        tmp = s - minus[v]
        ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    st[k].pop()
    if st[k]:
        minus[nextu[st[k][-1]]] += ss
    else:
        minus0[k] += ss
#     print(ss)
    return ss

dfs(1, -1, ans)
for k in range(1, n+1):
    tmp = n - minus0[k]
    ans[k] += (int(tmp * (tmp - 1) / 2) + tmp)
    
total = int(n * (n+1) / 2)
for i in range(1, n+1):
    print(total - ans[i])
### BUGGY CODE ###

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

for vlen in range(N // 2, -1, -1):
    for l1 in range(N - vlen * 2 + 1):
        for l2 in range(l1 + vlen, N):
            if S[l1:l1 + vlen] == S[l2:l2 + vlen]:
                print(vlen)
                exit()
print(0)


### FIXED CODE ###

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

dp = [[None for j in range(N)] for i in range(N)]
vlen = 0
for i in range(N-1):
    for j in range(i + 1, N):
        if S[i] != S[j]:
            dp[i][j] = 0
        elif i - 1 >= 0 and j - 1 >= 0:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = 1
        if i + dp[i][j] <= j:
            vlen = max(vlen, dp[i][j])
print(vlen)
### BUGGY CODE ###

import itertools
import math
n = int(input())
a = []
for i in range(1, n+1):
  a += [i]*3
xyz_list = list(set(list(itertools.combinations(a, 3))))
xyz_list.sort()
nn = int(math.sqrt(n/6))
dic = {}
for i in range(1, n+1):
  dic[i] = 0
for xyz in xyz_list:
  x, y, z = xyz[0], xyz[1],xyz[2]
  if x > nn and y > nn and z > nn:
    break
  sum1 = x**2 + y**2 + z**2 + x*y + y*z + z*x
  if sum1 in dic:
    if len(set(xyz)) == 1:
      dic[sum1] += 1
    elif len(set(xyz)) == 2:
      dic[sum1] += 3
    else:
      dic[sum1] += 6
for i in range(1, n+1):
  print(dic[i])

### FIXED CODE ###

import itertools
n = int(input())
dic = {}
for x in range(1, 101):
  for y in range(1, 101):
    for z in range(1, 101):
      f_xyz = x**2 + y**2 + z**2 + x*y + y*z + z*x
      if f_xyz in dic:
        dic[f_xyz] += 1
      else:
        dic[f_xyz] = 1
for i in range(1, n+1):
  if i in dic:
    print(dic[i])
  else:
    print(0)
### BUGGY CODE ###

n = str(input())
ans = 0
m = len(str(n))
for i in range(0,m-4):
    for j in range(i+5,m+1):
        k = n[i:j]
        if int(k) % 2019 == 0:
             ans += 1
print(ans)

### FIXED CODE ###

import collections
n = str(input())
ans,m,div = 0,0,[]
for i,j in enumerate(reversed(n)):
    m=(m+int(j)*pow(10,i,2019))%2019
    div.append(m)
div.append(0)
c = collections.Counter(div)
values, counts = zip(*c.most_common())
for i in range(0,len(counts)):
    ans += counts[i] *(counts[i]-1) /2
print(int(ans))
### BUGGY CODE ###

H, W, M = map(int,input().split())

X = [0] * H
Y = [0] * W

A = []
while M:
    M -= 1
    x, y = map(int,input().split())
    x, y = x -1, y -1
    A.append((x, y))
    X[x] += 1
    Y[y] += 1

def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = False
for i in xms:
    for j in yms:
        if not (i, j) in A:
            ans = True
            break
  
cnt = xm + ym         
print(cnt if ans else cnt - 1)

### FIXED CODE ###

import sys

input = sys.stdin.readline
H, W, M = map(int,input().split())
q=set(tuple(map(lambda x :int(x)-1,input().split())) for _ in range(M))

X = [0] * H
Y = [0] * W

for i, j in q:
    X[i] += 1
    Y[j] += 1
    
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]

xm = max(X)
ym = max(Y)
xms = my_index_multi(X, xm)
yms = my_index_multi(Y, ym)

ans = xm + ym - 1

bl = False
for i in xms:
    for j in yms:
        if not (i, j) in q:
            print(ans + 1)
            sys.exit()
            bl = True
            
print(ans)
### BUGGY CODE ###

T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())
  if d<b or a<b:
    print('No')
    continue
  if b-1<=c:
    print('Yes')
    continue
  if d%b<b-c and  d%b!=0:
    print('No')
    continue
  visited=[]
  while True:
    if a>c:
      a = c+(a-c)%b
    if a>c and a<b:
      print('No')
      break
    elif a == c:
      if c in visited:
        print('Yes')
        break
      visited.append(a)
    else:
      a = a-b
      if a in visited:
        print('Yes')
        break
      visited.append(a)
    a+=d



### FIXED CODE ###

import fractions
T = int(input())

for i in range(T):
  a, b, c, d = map(int, input().split())

  if d<b or a<b:
    print('No')
    continue

  if b-1<=c:
    print('Yes')
    continue

  gcd=fractions.gcd(d,b)
  e=b-gcd+a%gcd
  if e>c:
    print('No')
  else:
    print('Yes')
### BUGGY CODE ###

s,t=input(),input()
rs=[""for _ in range(26)]
rt=[""for _ in range(26)]
def a(n):return [chr(ord('a')+i)for i in range(26)].index(n)
for i in range(len(s)):
  ss,tt=a(s[i]),a(t[i])
  if rs[ss]=="":rs[ss]=t[i]
  elif rs[ss]!=t[i]:print("No");exit()
  if rt[tt]=="":rt[tt]=s[i]
  elif rt[tt]!=s[i]:print("No");exit()
print("Yes")

### FIXED CODE ###

s,t=input(),input()
rs=[""for _ in range(26)]
rt=[""for _ in range(26)]
def a(n):return [chr(ord('a')+i)for i in range(26)].index(n)
for i in range(len(s)):
  ss,tt=a(s[i]),a(t[i])
  if rs[ss]=="":rs[ss]=t[i]
  elif rs[ss]!=t[i]:print("No");exit()
  if rt[tt]=="":rt[tt]=s[i]
  elif rt[tt]!=s[i]:print("No");exit()
print("Yes")
### BUGGY CODE ###

n,k = map(int, input().split())
ls = [j for j in range(n+1)]
a = 1
for i in range(k,n+1):
    if (n + 1) -2*i >= 0:
        a += sum(ls[n+1-i:]) - sum(ls[:i]) + 1
    else:
        a += sum(ls[i:]) - sum(ls[:n-i+1]) + 1
print(a)

### FIXED CODE ###

n,k = map(int,input().split())
a = 1
for i in range(k,n+1):
    a += n*i - i**2 + i + 1
print(a%(10**9+7))
### BUGGY CODE ###

x=int(input())
i=1;
while True:
   if x==0:
     break
   print(f"Case {i}: {x}")


### FIXED CODE ###

i = 0
while True:
    x = int(input()); i += 1
    if x == 0: break
    print("Case {}: {}".format(i, x))
### BUGGY CODE ###

def resolve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    from collections import defaultdict, deque
    matrix = [[0]*N for _ in range(N)]
    for i in range(N-1):
        matrix[i][i+1] = matrix[i+1][i] = 1
    matrix[X][Y] = matrix[Y][X] = 1

    ans = [0] * N
    for i in range(N):
        queue = deque([(i, 0)])
        d = [float('inf')] * N
        while queue:
            node, dist = queue.popleft()
            if d[node] != float('inf'):
                continue
            d[node] = dist
            for adj in range(N):
                if matrix[node][adj]:
                    queue.append([adj, dist+1])
        for j in range(N):
            ans[d[j]] += 1
    for i in range(1, N):
        print(ans[i]//2)
resolve()

### FIXED CODE ###

def resolve():
    N, X, Y = map(int, input().split())
    from collections import defaultdict
    dist = defaultdict(int)
    for i in range(1, N):
        for j in range(i+1, N+1):
            _dist = min(j-i, abs(X-i) + 1 + abs(j-Y), abs(Y-i) + 1 + abs(j-X))
            dist[_dist] += 1
    for i in range(1, N):
        print(dist[i])

resolve()
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
l,r=0,0
for i in range(k):
    B=np.zeros(n,dtype=np.int64)
    for x,y in enumerate(list(A)):
        l=max(0,x-y)
        r=min(n-1,x+y)
        B[l:r+1]+=1
    A=B
print(*A,sep=' ')

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(n):
    for sum_w in range(w+1):
        if sum_w + ws[i] <= w:
            dp[i+1][sum_w + ws[i]] = max(dp[i+1][sum_w + ws[i]],
                                         dp[i][sum_w]+v[i])
        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])
print(dp[-1][-1])


### FIXED CODE ###

n, w = map(int, input().split())
s = [list(map(int, input().split())) for i in range(n)]
ws = [x[0] for x in s]
v = [x[1] for x in s]

dp = [[0]*(w+1) for _ in range(n+1)]

for sum_w in range(w+1):
    for i in range(1, n+1):
        if ws[i-1] <= sum_w:
            dp[i][sum_w] = max(dp[i-1][sum_w], dp[i-1][sum_w-ws[i-1]]+v[i-1])
        else:
            dp[i][sum_w] = dp[i-1][sum_w]

print(dp[-1][-1])