Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(250000)

from scipy.special import comb
# a = comb(n, r)

def main():
    # a,b,c,d = map(int, input().split())
    n = int(input())

    # temp = (10 ** 9 + 7)
    # sum = 0
    # if n >= 2:
    #     for i in range(2, n+1):
    #         a = int(comb(i, 2)) * 2
    #         a = (a * 8**(i-2)) % temp
    #         sum = sum + a
    # else:
    #     print(0)

    print(10**n - 9**n*2 + 8**n % (10 ** 9 + 7))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(250000)

from scipy.special import comb
# a = comb(n, r)

def main():
    # a,b,c,d = map(int, input().split())
    n = int(input())

    sum = 10**n - 9**n*2 + 8**n
    # temp = (10 ** 9 + 7)
    # sum = 0
    # if n >= 2:
    #     for i in range(2, n+1):
    #         a = int(comb(i, 2)) * 2
    #         a = (a * 8**(i-2)) % temp
    #         sum = sum + a
    # else:
    #     print(0)

    print(sum % (10 ** 9 + 7))

main()
# -*- coding: utf-8 -*-
N = int(input())
A = int(input())
B = int(input())

outValue = 0
for n in range(N+1):
    inputList = [int(c) for c in str(n)]
    if A <= sum(inputList) <= B:
        outValue += n

print(outValue)

### FIXED CODE ###

# -*- coding: utf-8 -*-
strList = list(map(int, input().split()))

N = strList[0]
A = strList[1]
B = strList[2]

outValue = 0
for n in range(N+1):
    strList = [int(c) for c in str(n)]
    if A <= sum(strList) <= B:
        outValue += n

print(outValue)
k, a, b = map(int, input().split())
ans = 0
def sousa(t, bis): # 残りターン数、所持ビスケット数、所持金はゼロまで全部買った後
    req = max(a - bis, 0) + 2 # 売買に必要なターン数
    # print(t, bis, req)
    if t< req: # 残りターン不足
        print(bis + t)
        return 
    elif req >= b - a: # 売買の成果が叩く成果以下なら売買する意味なし
        print(bis + t)
        return bis + t
    else: # 売買する
        sousa(t - req, bis + ((req - 2) - a + b)) # 売買の結果
import sys
sys.setrecursionlimit(500000)
sousa(k, 1)

### FIXED CODE ###

k, a, b = map(int, input().split())

def uru(t, bis): # すぐ売れるとき
    c = min(t, int(bis/a)*2) # 売り買いの回数
    return int(c/2)*2, bis + (b - a)*int(c/2)

def sousa(t, bis): # 残りターン数、所持ビスケット数、所持金はゼロまで全部買った後
    req = max(a - bis, 0) + 2 # 売買に必要なターン数
    # print(t, bis, req)
    if t< req: # 残りターン不足
        print(bis + t)
        return 
    elif req >= b - a + (req - 2): # 売買の成果が叩く成果以下なら売買する意味なし
        print(bis + t)
        return
    elif bis > a: # すぐ売れるとき
        sousa(t - uru(t, bis)[0], uru(t, bis)[1])
    else: # 売買する
        sousa(t - req, bis + ((req - 2) - a + b)) # 売買の結果

import sys
sys.setrecursionlimit(5000000)
sousa(k, 1)
from collections import deque
import sys
input=sys.stdin.readline

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False for _ in range(w)]+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    loc = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for i in range(w):
        a = input()
        for j in range(h):
            if a[j] == '#':
                q.append([i, j, 0])
                counts[j+1][i+1] = True

    while q:
        x, y, z = q.popleft()
        for i, j in loc:
            x0 = x+j
            y0 = y+i
            if not counts[y0+1][x0+1]:
                counts[y0+1][x0+1] = True
                q.append([x0, y0, z+1])
    print(z)

cal()


### FIXED CODE ###

from collections import deque

def cal():
    h, w = map(int, input().split())
    q = deque()
    counts = [[True for _ in range(w+2)]]+[[True]+[False]*w+[True] for _ in range(h)]+[[True for _ in range(w+2)]]
    for i in range(h):
        a = input()
        for j in range(w):
            if a[j] == '#':
                q.append([i+1, j+1, 0])
                counts[i+1][j+1] = True

    while q:
        x, y, z = q.popleft()    
        if not counts[x+1][y]:
            counts[x+1][y] = True
            q.append([x+1, y, z+1])
        if not counts[x-1][y]:
            counts[x-1][y] = True
            q.append([x-1, y, z+1])
        if not counts[x][y+1]:
            counts[x][y+1] = True
            q.append([x, y+1, z+1])
        if not counts[x][y-1]:
            counts[x][y-1] = True
            q.append([x, y-1, z+1])
    print(z)
    

cal()
n = int(input())
a = 2
b = 1
for i in range(n-1):
    c = a+b
    a = b
    b = c
print(c)

### FIXED CODE ###

n = int(input())
a = 2
b = 1
if n == 1:
    print(b)
else:
    for i in range(n-1):
        c = a+b
        a = b
        b = c
    print(c)
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n = ni()
i = ni()

print(n - i + 1)

### FIXED CODE ###

import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda x: [ni() for _ in range(x)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda x: [na() for _ in range(x)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda x: [ns() for _ in range(x)]
nas = lambda: stdin.readline().split()

n, i = na()

print(n - i + 1)
str=input()
list=["a","b","c"]
if str[1] in list:
  list.remove(str[1])
  if str[2] in list:
    list.remove(str[2])
    if str[3] i list:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")
 

### FIXED CODE ###

str=input()
list=["a","b","c"]
if str[0] in list:
  list.remove(str[0])
  if str[1] in list:
    list.remove(str[1])
    if str[2] in list:
      print("Yes")
    else:
      print("No")
  else:
    print("No")
else:
  print("No")
import heapq
n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    k=heapq.heappop(a)
    print(k)
    heapq.heappush(a,int(k/2))
    print(a)
print(-sum(a))    

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
a=[-int(i) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    k=heapq.heappop(a)
    heapq.heappush(a,-(abs(k)//2))
print(-sum(a))
def main():
    n,m = map(int,input().split())
    flag = [False for i in range(n+1)]
    AC = 0
    WA = 0
    for i in range(m):
        input_line = input().split()
        p,s = int(input_line[0]), input_line[1]
        if flag[p] == False:
            if s == "AC":
                AC += 1
                flag[p] = def main():
    n,m = map(int,input().split())
    flag = [False for i in range(n+5)]
    AC = 0
    WA = [0 for i in range(n+5)]
    _WA = 0
    for i in range(m):
        input_line = input().split()
        p,s = int(input_line[0]), input_line[1]
        if flag[p] == False:
            if s == "AC":
                AC += 1
                _WA += WA[p]
                flag[p] = True
            else:
                WA[p] += 1
    print(AC,_WA)
    return


if __name__ == "__main__":
    main()
            else:
                WA += 1
    print(AC,WA)
    return 0


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,m = map(int,input().split())
    flag = [False for i in range(n+5)]
    AC = 0
    WA = [0 for i in range(n+5)]
    _WA = 0
    for i in range(m):
        input_line = input().split()
        p,s = int(input_line[0]), input_line[1]
        if flag[p] == False:
            if s == "AC":
                AC += 1
                _WA += WA[p]
                flag[p] = True
            else:
                WA[p] += 1
    print(AC,_WA)
    return


if __name__ == "__main__":
    main()
import sys
n = int(input())
x = int(input(),2)
if bin(x).count('1')+1 > 1000:
    sys.setrecursionlimit(bin(x).count('1')+1)
    
ans = [0]*(bin(x).count('1')+1)
for i in range(1,len(ans)):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
for i in range(n):
    y = x^(1<<(n-i-1))
    t = y % bin(y).count('1')
    print(1+ans[t])

### FIXED CODE ###

n = int(input())
X = input()
x = int(X,2)
bitx = bin(x).count('1')
 
ans = [0]*(bitx+2)
for i in range(1,bitx+2):
    ans[i] = 1 + ans[i%bin(i).count('1')]
#print(ans)
l = []
bitp = bitx + 1
bitm = bitx - 1
xmp = 0
xmm = 0


if bitx != 1:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
            xmm += pow(2, n-(i+1), bitm)
    for i in range(n):
        if X[i] == '1':
            xm = (xmm - pow(2,n-i-1,bitm)) % bitm
            l.append(str(1+ans[xm]))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
else:
    for i in range(n):
        if X[i] == '1':
            xmp += pow(2, n-(i+1), bitp)
    for i in range(n):
        if X[i] == '1':
            l.append(str(0))
        else:
            xm = (xmp + pow(2,n-i-1,bitp))%bitp
            l.append(str(1+ans[xm]))
 
print('\n'.join(l))
import math
a,b,c = map(int,input().split())

L = a + 2 * math.sqrt(a*b) + b

if L < c :
    ans = 'Yes'
else :
    ans = 'No'

print(ans)

### FIXED CODE ###

A = list([1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, \
    1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51])
K = int(input())

ans = A[K-1]

print (ans)
import itertools

L = int(input(), 2)

count = 0
# (a, b)の組み合わせ
products = itertools.product(range(L+1), range(L+1))
for p in products:
    s = p[0] + p[1]
    if s <= L:
        # XOR
        if s == (p[0] ^ p[1]):
            count += 1
            # a, bが異なる値ならば、組み合わせ数+1
            #if a != b:
            #    count += 1

#print(count)
print(count % (10**9 + 7))

### FIXED CODE ###

L=input()
length=len(L)
inf=10**9+7
a=2
b=1
for i in range(1,len(L)):
	if L[i]=="0":
		b=b*3%inf
		continue
	else:
		b=(b*3+a)%inf
		a=a*2%inf
print((a+b)%inf)
import fractions

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

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
A_list = divisor(A)
B_list = divisor(B)

box = []

for i in A_list:
  if i in B_list:
    box.append(i)

box = box.sort()
    
tmp = []

for l in range(len(box)-1):
  for m in range((l+1),len(box)):
    if fractions.gcd(box[l],box[m]) != 1:
      tmp.append(box[m])
      
print(len(box)-len(set(tmp)))

### FIXED CODE ###

#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

print (ans)
a = list(map(int, input().split()))

if len(set(a)) =< 2:
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

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

if len(set(a)) == 2:
  print('Yes')
else:
  print('No')
n=input()
for i in range(n):
    a=input()
    b=input()
    if str(a+b)>80:
        print overflow
    else:
        print a+b

### FIXED CODE ###

n=input()
for i in range(n):
    a=input()
    b=input()
    if len(str(a+b))>80:
        print "overflow"
    else:
        print a+b
n,k = [int(x) for x in input().split()] 
count=0
for i in range(n):
  x=int(input())
  if x>=k:
    count=count+1
print(count)

### FIXED CODE ###

n,k = [int(x) for x in input().split()]
cnt=0
list  = input().split()
for num in list:
    if int(num)>=k: cnt=cnt+1
print(cnt)
a=input()
if a=Sunny:
  print(Cloudy)
elif a=Cloudy:
  print(Rainy)
else:
  print(Sunny)


### FIXED CODE ###

a=input()
if a=="Sunny":
  print("Cloudy")
elif a=="Cloudy":
  print("Rainy")
else:
  print("Sunny")
n = input()

color = [0 for i in range(n)]
d = [0 for i in range(n)]
f = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
t = 0

def dfsv(u):
  color[u] = 1
  t += 1
  d[u] = t
  for v in range(n):
    if M[u][v] == 1 and color[v] == 0:
      dfsv(v)
  color[u] = 2
  t += 1
  f[u] = t

def dfs():
  for u in range(n):
    if color[u] == 0:
      dfsv(u)
  for u in range(n):
    print u+1, d[u], f[u]

for i in range(n):
  X = map(int, raw_input().split())
  for j in range(X[1]):
    M[X[0]-1][X[2+j]-1] = 1

dfs()
    

### FIXED CODE ###

n = int(raw_input())
 
d = [0 for i in range(n)]
f = [0 for i in range(n)]
G = [0 for i in range(n)]
M = [[0 for i in range(n)] for j in range(n)]
col = [0 for i in range(n)]
t = [0]
 
def DFS_visit(u):
    col[u] = 1
    t[0] += 1
    d[u] = t[0]
    for v in range(n):
        if M[u][v] == 1 and col[v] == 0:
            DFS_visit(v)
    col[u] = 2
    t[0] += 1
    f[u] = t[0]
 
def DFS():
    for u in range(n):
        if col[u] == 0:
            DFS_visit(u)
    for u in range(n):
        print'{0} {1} {2}'.format(u+1, d[u], f[u])
     
for i in range(n):
    X = map(int, raw_input().split())
    for j in range(X[1]):
        M[X[0]-1][X[2+j]-1] = 1
 
DFS()
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)] # 始点からの距離
      dist[i][j] = 0 # 始点を定義
      stack = deque([(i, j)]) # 始点を"先入れ先出し"の配列に入れる
      
      while stack:
      # BFS
      # * 計算量 O(4HW:辺の数)
      si, sj = stack.popleft() 
        # "先入れ先出し"
        # * ⇔後入れ後出し。DFS
        #   si, sj = stack.pop()
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        # 経路に重みがない場合、BFSでは先に入れた方がそのマスに対する最短経路になる...☆
        # * DFSを使用すると更新の必要があり、
        #    計算量が(4HW*HW:辺の数×グリッドの数)->TLE
        # ** 木だと経路は1つしかないため、BFSもDFSも計算量は同じ
        #     グラフでは基本的にBFS推奨[要出典]
        # * 経路に重みがある場合も更新の必要があり、計算量はO(4HW*HW)
        # ** Dijkstra法を使えば、計算量はO(4HW+HWlogHW)
        #     O(E + VlogV): E -> Edge, V -> Vertex
          if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and S[ni][nj] != "#":
            if dist[ni][nj] > dist[si][sj] + 1:
              dist[ni][nj] = dist[si][sj] + 1
              stack.append((ni, nj))
          # ☆より、最短経路をとるマスからの隣接が次の最短経路の候補となる
          # すでに最短経路を取っているものは排除
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      # * 添え字被りに注意
      
print(answer)


### FIXED CODE ###

from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
 
INF = 10**15
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)]
      dist[i][j] = 0
      stack = deque([(i, j)])
      
      while stack:
        s = stack.popleft()
        si, sj = s
        for di, dj in d:
          if 0 <= si + di <= H - 1 and 0 <= sj + dj <= W - 1 and S[si + di][sj + dj] != "#":
            if dist[si + di][sj + dj] > dist[si][sj] + 1:
              dist[si + di][sj + dj] = dist[si][sj] + 1
              stack.append((si + di, sj + dj))
      #print(dist)
 
      max_dist = 0
      for ii in range(H):
        #print(dist[ii])
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      #print("")
      answer = max(max_dist, answer)
      
print(answer)
a,b=map(str,input().split())
c.d=map(int,input().split())
e=str(input())
if a==e:
    print(c-1,d)
else:
    print(c,d-1)
 

### FIXED CODE ###

a,b=map(str,input().split())
c,d=map(int,input().split())
e=str(input())
if a==e:
    print(c-1,d)
else:
    print(c,d-1)
n = input()

a = map(int, raw_input().split())

a.sort()
a.reverse()
f = 1
tmp = [0]
ct = 0

while len(a) != 0:
    nxt = a.pop(0)
    key = a.pop(0)
    if key == nxt:
        tmp.append(key)
	ct += 1
    	if ct == 2:
            break
    key = nxt

if len(tmp) > 2:
    print tmp[1] * tmp[2]
else:
    print 0
    

### FIXED CODE ###

x, a, b = map(int, raw_input().split())

if abs(x - a) < abs (x - b):
    print "A"
else:
    print "B"
from collections import Counter
l = list(input())
x = Counter(l)
for i in x:
    if i%2==1:
        print("No")
else:
    print("Yes")

### FIXED CODE ###

from collections import Counter
x = Counter(input()).values()
a = 0
for i in x:
    if i%2==1:
        a = 1

if a==1:
    print("No")
else:
    print("Yes")
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

print((ri() * (ri() - 1)) // 2)

### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.buffer.readline().rstrip()
rs = lambda: sys.stdin.buffer.readline().split()
ri = lambda: int(sys.stdin.buffer.readline())
rm = lambda: map(int, sys.stdin.buffer.readline().split())
rl = lambda: list(map(int, sys.stdin.buffer.readline().split()))

a = ri()
print((a * (a - 1)) // 2)
a,b = int(input().split())

print(max(a+b,a-b,a*b))


### FIXED CODE ###

a,b = map(int,input().split())

print(max(a+b,a-b,a*b))
N, M = map(int,input().split()) 

row_list = []

for i in range(M):
    d = list(map(int,input().split())) 
    row_list.append(Row(i, d[0], d[1]))

def zeroPadding(num):
    return "%06d"%num

class Row:
    def __init__(self, i, pref_id, year):
        self.i = i
        self.pref_id = pref_id
        self.year = year
        self.city_id = -1
        
    def __str__(self):
        return "{i: %d, pref_id: %d, year: %d, city_id: %d}"%(self.i, self.pref_id, self.year, self.city_id)
        
    def set_city_id(self, city_id):
        self.city_id = city_id
            
    def get_sort_key(self):
        return zeroPadding(self.pref_id ) + zeroPadding(self.year ) 
            
    def get_str(self):
        return zeroPadding(self.pref_id ) + zeroPadding(self.city_id)

row_list = sorted(row_list, key=lambda x: x.get_sort_key())

now_pref_id = -1
cnt = 1

result = []
for i, row in enumerate(row_list):
    if row.pref_id != now_pref_id:
        now_pref_id = row.pref_id
        cnt = 1
    
    row.set_city_id(cnt)
    row_list[i] = row
    cnt += 1

[print(x.get_str()) for x in sorted(row_list, key=lambda x: x.i)]

### FIXED CODE ###

def zeroPadding(num):
    return "%06d"%num

def zeroPadding10(num):
    return "%010d"%num

class Row:
    def __init__(self, i, pref_id, year):
        self.i = i
        self.pref_id = pref_id
        self.year = year
        self.city_id = -1
        
    def __str__(self):
        return "{i: %d, pref_id: %d, year: %d, city_id: %d}"%(self.i, self.pref_id, self.year, self.city_id)
        
    def set_city_id(self, city_id):
        self.city_id = city_id
            
    def get_sort_key(self):
        return zeroPadding(self.pref_id ) + zeroPadding10(self.year) 
            
    def get_str(self):
        return zeroPadding(self.pref_id ) + zeroPadding(self.city_id)

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

row_list = []

for i in range(M):
    d = list(map(int,input().split())) 
    row_list.append(Row(i, d[0], d[1]))

row_list = sorted(row_list, key=lambda x: x.get_sort_key())

now_pref_id = -1
cnt = 1

result = []
for i, row in enumerate(row_list):
    if row.pref_id != now_pref_id:
        now_pref_id = row.pref_id
        cnt = 1
    
    row.set_city_id(cnt)
    row_list[i] = row
    cnt += 1

[print(x.get_str()) for x in sorted(row_list, key=lambda x: x.i)]
def solve(ashiba, N, K):
    dp = [float('inf')] * N
    dp[0] = 0
    for i in range(1, len(ashiba)):
        paths = [dp[j]+abs(ashiba[j]-ashiba[i]) for j in range(max(0, i-K), i)]
        dp[i] = min(paths)
    return dp[-1]


N, K = map(int, input().split())
ashiba = [int(i) for i in input().split()]
ans = solve(ashiba, N, K)
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
https://atcoder.jp/contests/dp/tasks/dp_a

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, ashiba):
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(dp[i-1] + abs(ashiba[i] - ashiba[i-1]), dp[i-2] + abs(ashiba[i] - ashiba[max(i-2, 0)]))
    return dp[-1]


def main(args):
    N = int(input())
    ashiba = [int(a) for a in input().split()]
    ans = solve(N, ashiba)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b, c, k = list(map(int, readline().split()))
    s = [1] * a + [0] * b + [-1] * c
    ans = sum(s[::k])
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    a, b, c, k = list(map(int, readline().split()))
    if a + b >= k:
        print(min(a, k))
    else:
        print(a - (k - a - b))


if __name__ == '__main__':
    main()
nums = []

for i in range(5):
  nums.append(input())

k = input()

for i in range(5):
  for j in range(5-i)[1:]:
    if nums[j] - nums[i] > k:
      print ":("
      return

print "Yay!"
return
      

### FIXED CODE ###

import sys

nums = []

for i in range(5):
  nums.append(int(input()))

k = int(input())

for i in range(5):
  for j in range(5-i)[1:]:
    if nums[j] - nums[i] > k:
      print(":(")
      sys.exit()

print("Yay!")
N, M = (int(i) for i in input().split(' '))
py=[]
p =[]

# 全都市を配列に代入
for i in range(M):
    p = [i]
    p.extend([int(j) for j in input().split(' ')])
    py.append(p)

# 全N個の県について調べる
Npy = []
for i in range(1,N+1):
    # 県i
    pyi = [j for j in py if j[1] == i] # 県iの市リスト
    pyi.sort(key=lambda x: x[2]) # 県iの市を生まれた年でソート
    l = len(pyi)
    cnt = 0
    for k in range(1,l+1):
        pyi[k-1][2] = k
    Npy.extend(pyi)

Npy.sort(key=lambda x: x[0])

for t in Npy:
    print('{0:0>8}{1:0>8'.format(t[1],t[2]))
    

### FIXED CODE ###

N, M = (int(i) for i in input().split(' '))
py=[]
p =[]

# 全都市を配列に代入
for i in range(M):
    p = [i]
    p.extend([int(j) for j in input().split(' ')])
    py.append(p)

# 設立年で一度ソートする
py.sort(key = lambda x: x[2])
pcid = [1] * N # 各県の都市ID

for i in range(M):
    p = py[i][1] # 県ID
    py[i][2] = pcid[p-1]
    pcid[p-1] += 1

py.sort(key=lambda x:x[0])
for t in py:
    print('{0:0>6}{1:0>6}'.format(t[1],t[2]))
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

sat = sum(B)
for i in range(N-1):
    if A[i]+1==A[i+1]:
        sat += C[A[i-1]]
print(sat)


### FIXED CODE ###

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

sat = sum(B)
for i in range(N-1):
    if A[i]+1==A[i+1]:
        sat += C[A[i]-1]
print(sat)
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

x,y = map(int,input().split())
print(lcm(x,y))

### FIXED CODE ###

from fractions import gcd
import math
def lcm(x, y):
    return (x * y) // gcd(x, y)

x,y = map(int,input().split())
print(lcm(x,y))
a,b,c = map(int,input().split())
if a > b:
	A = a
	a = b
	b = A

yoru = 1    ＃寄り道する
if a < c and b > c:
	yoru = 1
else:
	yoru = 0
if yoru == 1:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

a,b,c = map(int,input().split())
if a > b:
	A = a
	a = b
	b = A

yoru = 1    
if a < c and b > c:
	yoru = 1
else:
	yoru = 0
if yoru == 1:
	print("Yes")
else:
	print("No")
a, b= (int(i) for i in input().split())
print b + a

### FIXED CODE ###

L,R = input().split()
k = R + L
print (k)