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

import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
tree = make_tree(n)
for i in range(n):
    update(i, i, s[i][1])
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if s[i][0] + 2 * d >= s[j][0]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)

### FIXED CODE ###

import math

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def get(i):
    i += len(tree) // 2
    ans = 0
    while True:
        if i == 0:
            break
        ans += tree[i] 
        i //= 2
    return ans

def update(s, t, x):
    s += len(tree) // 2
    t += len(tree) // 2
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            tree[s] += x
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            tree[t] += x
            t = (t - 1) // 2
    return

n, d, a = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort()
tree = make_tree(n)
l = len(tree)
for i in range(n):
    tree[i + l // 2] = s[i][1]
y = [n - 1] * n
j = 0
for i in range(n):
    if j == n:
        break
    while True:
        if j == n:
            break
        if s[i][0] + 2 * d >= s[j][0]:
            j += 1
        else:
            y[i] = j - 1
            break
ans = 0
for i in range(n):
    h = get(i)
    if h > 0:
        c = math.ceil(h / a)
        ans += c
        update(i, y[i], -1 * a * c)
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0
for i in range(k+1):
    for j in range(min(s-i+1,k+1)):
        for l in range(min(s-i-j+1,k+1)):
            if i+j+l==s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
cnt = 0
for i in range(k+1):
    for j in range(min(s-i+1,k+1)):
      if 0<=s-i-j<=k:
        cnt += 1
print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
  bc = list(map(int, input().split()))
  res = bc[0]
  for bit in range(n):
    if a[bit] == res:
      a[bit] = bc[1]
  print(sum(a))


### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
count = collections.Counter(a)
q = int(input())
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s = s - (b - c) * count[b]
  
  count[c] += count[b]
  count[b] = 0
  print(s)
### BUGGY CODE ###

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

cor = pen = temp_pen = 0
temp_p = "0"
aclist=[]
res=[]
for _ in range(m):
  res.append(input().split())

for x in range(1, n+1):
  for result in res:
    if x == int(result[0]):
      if result[1] == "AC":
        cor += 1
        pen += temp_pen
        temp_pen = 0
        break
      else:
        temp_pen += 1
print(cor, pen)
 

### FIXED CODE ###

import sys
from collections import defaultdict

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

wa=defaultdict(lambda: 0)
already=set()
ac = 0
for line in sys.stdin:
  p, s = line.split()
  p = int(p)
  if p in already:
    continue

  if s == "AC":
    ac+=1
    already.add(p)
  else:
    wa[p] += 1

print(ac, sum(wa[i] for i in already))
### BUGGY CODE ###

N = int(input())
aA=sorted(set(int(_) for _ in input().split()))
N = len(aA)
def ggg(i,j):
    i %= j
    if i == 0:
        return j
    else:
        return ggg(j,i)

if len(aA) == 1:
    print(aA[0])
else:
    iMin = aA[0]
    iMax = aA[-1]
    if iMin  == 1:
        print(1)
    else:
        if max(i % iMin for i in aA) == 0:
            print(iMin)
            exit()
        else:
            iM = iMax
            for i in range(N):
                iA = aA[i]
                for j in range(i+1,N):
                    iMt = ggg(aA[j],iA)
                    if 0 < iMt and iMt < iM:
                        iM = iMt
                if iM == 1:
                    print(1)
                    exit()
            print(iM)


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

import sys
N = int(input())
if N == 1:
    print(1)
    sys.exit()

# 数列の和
def re(x):
    return x*(x+1)//2

# 二分探索
l, r = 0, N+1
exact = -1
while abs(l - r) > 1:
    mid = (l + r) // 2
    if re(mid) > N:
        r = mid
    elif re(mid) == N:
        exact = mid
    else:
        l = mid

# 途中抜けしない場合
if exact != -1:
    for i in range(1, exact + 1):
        print(i)

# する場合
else:
    temp = re(r) - N
    for i in range(1, r+1):
        if i != temp:
            print(i)

### FIXED CODE ###

import sys
N = int(input())
if N == 1:
    print(1)
    sys.exit()

# 数列の和
def re(x):
    return x*(x+1)//2

# 二分探索
l, r = 0, N+1
exact = -1
while abs(l - r) > 1:
    mid = (l + r) // 2
    if re(mid) > N:
        r = mid
    elif re(mid) == N:
        exact = mid
        break
    else:
        l = mid

# 途中抜けしない場合
if exact != -1:
    for i in range(1, exact + 1):
        print(i)

# する場合
else:
    temp = re(r) - N
    for i in range(1, r+1):
        if i != temp:
            print(i)
### BUGGY CODE ###

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

for k in range(N):
    x=A[(k)%N]^B[0]
    for i in range(1,N):
        if x!=A[(i+k)%N]^B[i]:
            break
    else:
        print(k,x)

### FIXED CODE ###

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

AX=[A[i%N]^A[(i-1)%N] for i in range(N,0,-1)]
BX=[B[i%N]^B[(i-1)%N] for i in range(N,0,-1)]
BX2=BX+BX
#print(BX2)
#print(AX)

shift=[0]*(N+1)
k=1
l=0
while k<N:
    if AX[k]==AX[l]:
        k+=1
        l+=1
        shift[k]=l
    elif l>0:
        l=shift[l]
    else:
        k+=1
        shift[k]=0
#print(shift)

ans=[]
ai=bi=0
Z=0
while bi<N:
    #print(bi,ai)
    if BX2[bi+ai]==AX[ai]:
        ai+=1
        if ai==N-1:
            print(bi,A[bi]^B[0])
            ans.append((bi+1)%N)
            bi+=ai-shift[ai]
            ai=shift[ai]
    else:
        bi+=1 if ai==0 else ai-shift[ai]
        ai=shift[ai]
### BUGGY CODE ###

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

ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            tl = [ll[i], ll[j], ll[k]]
            tl.sort()
            if tl[0] + tl[1] > tl[2]:
                ans += 1

print(ans)


### FIXED CODE ###

n = int(input())
ll = list(map(int, input().split()))
ll.sort(reverse=True)

ans = 0

for i in range(n-2):
    j = i + 1
    k = n - 1
    while k > j:
        if ll[i] < ll[j] + ll[k]:
            ans += k - j
            j += 1
        else:
            k -= 1

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

s=input()
t=input()
n=len(s)
m=len(t)
dp=[['' for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j]+s[i]
    else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i+1][j+1],key=len)
print(dp[-1][-1])

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for _ in range(m+1)] for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    if s[i]==t[j]:dp[i+1][j+1]=dp[i][j]+1
    else:dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j],dp[i+1][j+1])
ans=''
while n*m:
  if s[n-1]==t[m-1]:
    ans+=s[n-1]
    n-=1
    m-=1
  else:
    if dp[n-1][m]>dp[n][m-1]:n-=1
    else:m-=1
print(ans[::-1])
### BUGGY CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	@lru_cache(None)
	def dfs(tight, i, tot):
		if i == len(x):
			return 1 if tot == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(ntight, i + 1, (tot + dig) % d)
		return cnt % MOD

	ans += dfs(1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

### FIXED CODE ###

from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1] - 1) % MOD
	print(ans)
	stdout.close()

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

intLine=lambda:map(int,input().split())
h,n=intLine()
dp=[10**9]*(h+1)
dp[0]=0
for _ in range(n):
  a,b=intLine()
  for j in range(h+1):
    dp[j]=min(dp[j],dp[max(0,j-a)]+b)
print(dp[h])

### FIXED CODE ###

h,n,*t=map(int,open(0).read().split())
dp=[10**18]*(h+1)
dp[0]=0
for a,b in zip(*[iter(t)]*2):
    for j in range(h+1):
        dp[j]=min(dp[j],dp[max(0,j-a)]+b)
print(dp[h])
### BUGGY CODE ###

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


def calc(yv, idx):
    max_value = abs(yv - A[-1])
    max_value = max(max_value, min([abs(A[i]-A[-1]) for i in range(idx, n)]))

    for i in range(idx+1, n-1):
        max_value = max(max_value, calc(A[i], i+1))

    memo[idx] = max_value
    return max_value


memo = {}
print(calc(w, 0))

### FIXED CODE ###

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

if n == 1:
    print(abs(A[0]-w))
else:
    print(max(abs(A[-1]-w), abs(A[-2]-A[-1])))
### BUGGY CODE ###

A, B, N = map(int, input().split())
c = 0
t = -10
for i in range(N + 1):
    a = (i * A) // B - A * (i // B)
    c = max(c, a)
    if t > a:
        print(c)
        break
    t = a
else:
    print(c)


### FIXED CODE ###

A, B, N = map(int, input().split())
X = min(N, B - 1)
print(A * X // B - A * (X // B))
### BUGGY CODE ###

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

a.sort(reverse=True)

arrival = 1
ans = 0

while arrival < N:
    score = a.pop(0)
    if arrival == 1:
        ans += score
        arrival += 1
    else:
        ans += score*min(2, N - arrival)
        arrival += 2

print(ans)

### FIXED CODE ###

from collections import deque

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

A.sort(reverse=True)

a = deque(A)

arrival = 1
ans = 0

while arrival < N:
    score = a.popleft()
    if arrival == 1:
        ans += score
        arrival += 1
    else:
        ans += score*min(2, N - arrival)
        arrival += 2

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

N, W = map(int, input().split())
w, v = [0] * N, [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (W + 1) for _ in range(N + 1)]
# dp[i][j](j=0,1,...,W)の値が求まっている状態で、dp[i+1][j]を更新することを考える
for i in range(N):
    for j in range(W + 1):
		# 品物(w[i],v[i])を選ぶとき、j-w[i]>=0に限って、価値v[i]が加算される
        if j - w[i] >= 0:
            dp[i + 1][j] = dp[i][j - w[i]] + v[i]
		# 品物(w[i],v[i])を選ばないとき、何も加算しない
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
#print(dp)

print(dp[N][W])

### FIXED CODE ###

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

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    tmp = bin(a)[2:]
    ret_r = [0] * n
    for i, t in enumerate(tmp[::-1]):
        ret_r[i] = int(t)
    return ret_r


def calc_sum(a, n_1_ls, n_1_max):
    '''
    aはxorしてから和を取りたい数
    n_1_lsは各桁の1の数
    n_1_maxは最大1は何個あり得るか
    '''
    a_binary = ret_binary(a)
    ret = 0
    for i, (aa, n_1) in enumerate(zip(a_binary, n_1_ls)):
        if aa == 0:
            ret += (2**i) * n_1
        else:
            ret += (2**i) * (n_1_max - n_1)
    return ret


def add_koko(lsa, lsb):
    return [a + b for a, b in zip(lsa, lsb)]


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for i in range(N - 2, -1, -1):
    a = A[i]
    a_pre = A[i + 1]
    n_1_ls = add_koko(n_1_ls, ret_binary(a_pre))
    n_1_max += 1
    tmp = calc_sum(a, n_1_ls, n_1_max)
    ans += tmp
    ans %= MOD

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


n = 60
N = read_a_int()
A = read_ints()


def ret_binary(a: int):  # 逆順で返すことに注意
    ret_r = [0] * n
    for i in range(n):
        bit = a % 2
        a = a // 2
        ret_r[i] = bit
    return ret_r


MOD = 10**9 + 7

n_1_max = 0
n_1_ls = [0] * n
ans = 0
for a in A:
    tmp = ret_binary(a)
    for i in range(n):
        n_1_ls[i] += tmp[i]


for i, n_1 in enumerate(n_1_ls):
    num_sonoketa = n_1 * (N - n_1)
    ans += (((2**i) % MOD) * num_sonoketa)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
*X,=map(int,input().split())

import bisect

i=bisect.bisect_left(X,0)
L=max(0, bisect.bisect_right(X,0)-K)
R=min(N-1, bisect.bisect_left(X,0)+K-1)

ans=float('inf')
for i in range(L,R-K+2):
    t=0
    s=X[i:i+K]
    if s[-1]<=0:
        t+=abs(s[0])
    elif 0<=s[0]:
        t+=s[-1]
    else:
        t+=min(abs(s[0]),s[-1])*2+max(abs(s[0]),s[-1]) 
    # print(s,t)
    ans=min(ans,t)
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
*X,=map(int,input().split())

import bisect

i=bisect.bisect_left(X,0)
L=max(0, bisect.bisect_right(X,0)-K)
R=min(N-1, bisect.bisect_left(X,0)+K-1)

ans=float('inf')

for i in range(L,R-K+2):
    t=0
    l=X[i]
    r=X[i+K-1]
    if r<=0:
        t=abs(l)
    elif 0<=l:
        t=r
    else:
        t=min(abs(l),r)*2+max(abs(l),r) 
    # print(X[i:i+K],t)
    ans=min(ans,t)
print(ans)
### BUGGY CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    def decom(n) -> list:
        ret = []

        d = 2
        cnt = 0
        while n % d == 0:
            n //= d
            cnt += 1
        ret.append((d, cnt))

        d = 3
        while n > 1:
            cnt = 0
            while n % d == 0:
                n //= d
                cnt += 1
            ret.append((d, cnt))
            d += 1

        return ret

    dlis = decom(M)

    cal = Calc(max_value=N + 30, mod=MOD)

    ans = 1
    for _, cnt in dlis:
        ans = (ans * cal.combination(N + cnt - 1, cnt)) % MOD
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10 ** 9 + 7


def prime_factorization(n):
    i = 2
    res = []
    while i * i <= n:
        cnt = 0
        while n % i == 0:
            n /= i
            cnt += 1
        if cnt > 0:
            res.append(cnt)
        i += 1
    if n > 1:
        res.append(1)
    return res


def comb(a, b):
    b = min(b, a - b)
    if b < 0:
        return 0
    elif b == 0:
        return 1
    elif b == 1:
        return a
    else:
        return (a % MOD) * pow(b, MOD - 2, MOD) % MOD * comb(a - 1, b - 1) % MOD


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

ans = 1
for power in prime_factorization(M):
    ans *= comb(N - 1 + power, power)
    ans %= MOD

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

from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = []
  for i in range(h):
    tmp = input()
    maze.append(tmp)
  l = [[0]*w for _ in range(h)]
  r = [[0]*w for _ in range(h)]
  u = [[0]*w for _ in range(h)]
  d = [[0]*w for _ in range(h)]
  cur = 0
  for i in range(h):
    cur = 0
    for j in range(w):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      l[i][j] = cur
  for i in range(h):
    cur = 0
    for j in range(w-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      r[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      d[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      u[i][j] = cur      
  ans = 0
  for i in range(h):
    for j in range(w):
      now = l[i][j]+r[i][j]+u[i][j]+d[i][j] -3
      ans = max(now,ans)
  print(ans)
solve()

### FIXED CODE ###

from collections import deque
def solve():
  h,w = (int(i) for i in input().split())
  maze = []
  for i in range(h):
    tmp = input()
    maze.append(tmp)
  l = [[0]*w for _ in range(h)]
  r = [[0]*w for _ in range(h)]
  u = [[0]*w for _ in range(h)]
  d = [[0]*w for _ in range(h)]
  cur = 0
  for i in range(h):
    cur = 0
    for j in range(w):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      l[i][j] = cur
  for i in range(h):
    cur = 0
    for j in range(w-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      r[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      d[i][j] = cur
  for j in range(w):
    cur = 0
    for i in range(h-1,-1,-1):
      if maze[i][j] == ".":
        cur += 1
      else:
        cur = 0
      u[i][j] = cur      
  ans = 0
  for i in range(h):
    for j in range(w):
      now = l[i][j]+r[i][j]+u[i][j]+d[i][j] -3
      ans = max(now,ans)
  print(ans)
solve()
### BUGGY CODE ###

n,k=map(int,input().split())
a=tuple(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l+=[min(l[j]+abs(b-a[j])for j in range(max(0,i-k),i))]
print(l[-1])


### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l=[0]
for i in range(1,n):
  b=a[i]
  l.append(min(l[j]+abs(b-a[j])for j in range(i-min(k,i),i)))
print(l[-1])
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
arr = [r, g, b]
arr.sort()
ans = 0
for i in range(n // arr[2] + 1):
    if arr[2] * i > n:
        break
    for j in range(n // arr[1] + 1):
        tmp = arr[2] * i + arr[1] * j
        if tmp > n:
            break
        else:
            if tmp == n:
                ans += 1
            elif n - tmp > 0 and (n - tmp) % arr[0] == 0:
                ans += 1

print(ans)


### FIXED CODE ###

R, G, B, n = map(int, input().split())
ans = 0
for r in range(n // R + 1):
    Rr = R * r
    for g in range((n - Rr) // G + 1):
        tmp = Rr + G * g
        if (n - tmp) % B == 0:
            ans += 1
print(ans)
### BUGGY CODE ###

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


def send_query(n):
    print(n)
    resp = int(input())
    return resp


N = int(input())
l = 0
r = N-1
l_cur = send_query(0)
if l_cur == "Vacant":
    print(0)
    exit()
r_cur = send_query(N-1)
if r_cur == "Vacant":
    print(N-1)
    exit()

l = 0
cur = l_cur
r = N-1
while True:
    mid = (l+r)//2+1
    resp = send_query(mid)
    if resp == "Vacant":
        print("ans->", mid)
        break
    elif resp == cur:
        if (mid-l+1) % 2 == 1:
            r = mid-1
        else:
            l = mid+1
    else:
        if (mid-l+1) % 2 == 1:
            l = mid-1
        else:
            r = mid+1
    cur = resp


### FIXED CODE ###

n = int(input())
s = [0]*(n+1)

print(0)
a = input()
if a == "Vacant":
    exit()
s[0] = a
s[n] = a

l = 0
r = n
while True:
    m = (r+l)//2
    print(m)
    a = input()
    if a == "Vacant":
        exit()

    s[m] = a
    if s[l] == s[r]:
        if s[l] == s[m]:
            if (m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if (m-l) % 2 == 1:
                l = m
            else:
                r = m
    else:
        if s[l] == s[m]:
            if(m-l) % 2 == 1:
                r = m
            else:
                l = m
        else:
            if(m-l) % 2 == 1:
                l = m
            else:
                r = m
### BUGGY CODE ###

n=int(input())
d={}
for i in range(n):
    s=input()
    if s not in d.values():
        d[len(d)]=s

print(len(d))

### FIXED CODE ###

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

for i in range(n):
    a[i]=input()
a=sorted(a)
ans=1
for i in range(n-1):
    if a[i]!=a[i+1]:
        ans+=1
print(ans)
### BUGGY CODE ###

n = int(input())
table = [0] * (n + 1)
 
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        table[j] += 1
ans = 0
 
for i in range(1,len(table)):
    ans += i * table[i]
 
print(ans)

### FIXED CODE ###

n = int(input())
table = [0] * (n + 1)

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

for i in range(1,len(table)):
    ans += i * table[i]

print(ans)