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

from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
q = deque()
maps = []
inf = 10 ** 7
for h in range(H):
  line = list(input())
  for w in range(W):
    if line[w] == '#':
      q.append([h,w])
  maps.append([0 if x == '#' else inf for x in line])
maps = np.array(maps)

count = 0
for i in range(H*W):
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and maps[nx][ny] != 0:
        maps[nx][ny] = 0
        nq.append([nx,ny])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(i)

### FIXED CODE ###

# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
from collections import deque
import copy
 
def main():
  H, W = list(map(int, input().split()))
  L = [[j=="#" for j in input()] for i in range(H)]
  q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])
  cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  result = 0
  while True:
    nq = deque()
    while q:
      i, j = q.popleft()
      if i > 0 and not L[i-1][j]:
        L[i-1][j] = True
        nq.append((i-1, j))
      if j > 0 and not L[i][j-1]:
        L[i][j-1] = True
        nq.append((i, j-1))
      if i < H-1 and not L[i+1][j]:
        L[i+1][j] = True
        nq.append((i+1, j))
      if j < W-1 and not L[i][j+1]:
        L[i][j+1] = True
        nq.append((i, j+1))
    if nq:
      q = copy.copy(nq)
    else:
      break    
    result += 1
  print(result)
 
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()

for i in range(q):
  l,r=map(int,input().split())
  
  string=s[l-1:r]
  print(string.count("AC"))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
num=[0]
be=""

for i in range(n):
  if be=="A" and s[i]=="C":
    num.append(num[-1]+1)
    
  else:
    num.append(num[-1])
    
  be=s[i]
    
for i in range(q):
  l,r=map(int,input().split())
  
  print(abs(num[l]-num[r]))
### BUGGY CODE ###

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

lst1 = [int(input()) for i in range(M)]

from functools import lru_cache
@lru_cache(maxsize=None)

def fib(n):
  a, b = 1, 2
  for i in range(1,n+1):  
    if (i == 1):
      if (i in lst1):
        a, b = 0, 1
    else:
      if (i in lst1):
        a, b = 0, a
      else:
        a, b = b, b+a
  return a

print(fib(N)  % 1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
D=[1] * (n + 1)
for _ in range(m):
    D[int(input())] = 0
for i in range(n+1):
    if i > 1:
        D[i] = (D[i-1] + D[i-2]) % 1000000007 * D[i]
print(D[i])
### BUGGY CODE ###

import itertools
n=int(input())
S=input()

number=list(itertools.combinations(S,3))
print(len(set(number)))

### FIXED CODE ###

n=int(input())
S=input()

ans=0
for i in range(10):
  for j in range(10):
    for k in range(10):
      idxi=S.find(str(i))
      if idxi==-1:
        continue
      idxj=S.find(str(j),idxi+1)
      if idxj==-1:
        continue
      idxk=S.find(str(k),idxj+1)
      if idxk==-1:
        continue
      ans+=1
print(ans)
### BUGGY CODE ###

from fractions import gcd

mod = 10**9 + 7

N = int(input())
A = input().split()
num = 1
for n in A:
    num = (num*int(n))//gcd(num,int(n))

t = 0
for n in A:
    t = (t + num//int(n)) % mod
print(t)

### FIXED CODE ###

from fractions import gcd

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

    N = int(input())
    A = input().split()
    AP = set(A)
    num = 1
    for n in AP:
        num = (num*int(n))//gcd(num,int(n))

    t = 0
    for n in A:
        t = (t + num//int(n))
    print(t%mod)


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

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = []
for i in range(M):
  danger.append(int(input()))
l = [1, 1]
for i in range(1, N):
  if i in danger:
    l[1] = 0
  l = [l[1] % Num, (l[0] + l[1]) % Num]
  if l == [0, 0]:
    break
if N in danger:
  l[1] = 0
print(l[1])

### FIXED CODE ###

Num = 10 ** 9 + 7
N, M = map(int, input().split())
danger = -1
if M != 0:
  danger = int(input())
count = 1
l = [1, 1]
for i in range(1, N):
  if i == danger:
    l[1] = 0
    if count < M:
      danger = int(input())
      count += 1
  l = [l[1] % Num, l[0] + l[1]]
  if l == [0, 0]:
    break
if N == danger:
  l[1] = 0
print(l[1] % Num)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
maze=[[0]*n for i in range(n)]
for i in range(m):
    r,l=map(int,input().split())
    maze[r-1][l-1]=1
    maze[l-1][r-1]=1

stamp=[-1]*n
queue=deque([0])
while queue:
    d=queue.popleft()
    for i in range(n):
        if maze[d][i]==1 and stamp[i]==-1:
            stamp[i]=d
            queue.append(i)

print("Yes")
for i in range(1,n,1):
    print(stamp[i]+1)

### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
maze=[[]for i in range(n)]
for i in range(m):
    r,l=map(int,input().split())
    maze[r-1].append(l-1)
    maze[l-1].append(r-1)

stamp=[-1]*n
queue=deque([0])
while queue:
    d=queue.popleft()
    for i in maze[d]:
        if stamp[i]==-1:
            stamp[i]=d
            queue.append(i)

print("Yes")
for i in range(1,n,1):
    print(stamp[i]+1)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

N = int(input())
edge = np.array([tuple(map(int, input().split())) for _ in range(N - 1)]).T
Q, K = map(int, input().split())
query = [tuple(map(int, input().split())) for _ in range(Q)]

matr = csr_matrix((edge[2], (edge[0] - 1, edge[1] - 1)), (N, N))
way = dijkstra(matr, indices=K - 1, directed=False).astype(np.int64)
for x, y in query:
    print(way[x - 1] + way[y - 1])

### FIXED CODE ###

from collections import deque

N = int(input())

T = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b, c = map(int, input().split())
    T[a - 1].append((b - 1, c))
    T[b - 1].append((a - 1, c))
Q, K = map(int, input().split())

# dfs
table = [0] * N
D = deque([K - 1])
visited = set()
while D:
    v = D.pop()
    visited.add(v)
    for x, d in T[v]:
        if x not in visited:
            table[x] = table[v] + d
            D.append(x)

for _ in range(Q):
    x, y = map(int, input().split())
    print(table[x - 1] + table[y - 1])
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0,N):
    for j in range(i,N):
        if S[i] != S[j]:
            for k in range(j,N):
                if  j-i != k-j and S[i] != S[k] and S[j] != S[k]:
                    ans += 1
print(ans)

### FIXED CODE ###

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

# それぞれ違う文字の組み合わせの数
ans = S.count('R')*S.count('G')*S.count('B')

# j-i!=k-jの組み合わせ
for i in range(0, N-2):
    for j in range(i+1, N-1):
        k = j+j-i
        if k < N:
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                ans -= 1

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

K,S=map(int,input().split())

c=0

for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                c+=1

print(c)
                


### FIXED CODE ###

K,S=map(int,input().split())

c=0

for i in range(K+1):
    for j in range(K+1):
        if i+j+K>=S and i+j<=S:
            c+=1

print(c)
### BUGGY CODE ###

from collections import Counter
N = int(input())
S = list(input())
c = Counter(S)
# print('c', c)

if len(c) != 3:
    print(0)
    exit()

con1 = 1
for v in c.values():
    con1 *= v

not_con2 = 0
for d in range(3001):
    for i in range(3001):
        j = i + d
        k = j + d
        if N - 1 < k:
            continue
        # print('S', S[i], S[j], S[k], i, j, k)
        if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
            not_con2 += 1

# print('not_con2', not_con2)
ans = con1 - not_con2
print(ans)


### FIXED CODE ###

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

if len(S) <= 3:
    print(0)
    exit()

sorted_S = sorted(S)
c = [0, 0, 0]
j = 0
for i in range(len(sorted_S) - 1):
    if sorted_S[i] != sorted_S[i + 1]:
        if j == 0:
            c[j] = i + 1
            j += 1
        else:
            c[j] = (i + 1) - c[j - 1]
            j += 1

# print('c', c, j)
if j != 2:
    print(0)
    exit()
c[2] = N - c[0] - c[1]

condition1 = c[0] * c[1] * c[2]
# print('condition1', condition1)

condition2 = 0
for i in range(N):
    for d in range(N // 2 + 2):
        j = i + d
        k = j + d
        if j >= N or k >= N:
            continue
        # print('i, j, k', i, j, k)
        if (S[i] != S[j]) and (S[j] != S[k]) and (S[k] != S[i]):
            condition2 += 1
ans = condition1 - condition2
print(ans)
### BUGGY CODE ###

from itertools import combinations


_ = input()
s = input()
seen = set()
for x in combinations(s, 3):
    if x not in seen:
        seen.add(x)

print(len(seen))

### FIXED CODE ###

N = int(input())
S = input()
 
ans = 0
for i in range(1000):
    s = str(i).zfill(3)
 
    index = 0
    for j in range(N):
        if s[index] == S[j]:
            index += 1
        if index == 3:
            ans += 1
            break
print(ans)
### BUGGY CODE ###

N = int(input())
s = []
for _ in range(N):
    s.append(sorted(input()))

count = 0
for i in range(N-1):
    for j in range(i+1, N):
        if s[i] == s[j]:
            count+=1

print(count)

### FIXED CODE ###

N = int(input())
S = {}

for i in range(N):
    str = ''.join(sorted(input()))
    if str in S.keys():
        S[str] += 1
    else:
        S.setdefault(str, 1)

cnt = 0
for v in S.values():
    cnt += (v * (v-1) // 2)

print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
A=[]
B=[]
for i in [0]*N:
 h=input()
 if h in A:
  B[A.index(h)]+=1
 else:
  A.append(h)
  B.append(1)
d=max(B)
C=[]
for i in range(len(B)):
 if B[i]==d:
  C.append(A[i])
C.sort()
for i in range(len(C)):
 print(C[i],end='')


### FIXED CODE ###

N=int(input())
dic={}
for i in range(N):
 a=input()
 if a in dic:
  dic[a]+=1
 else:
  dic[a]=1
c=max(dic.values())
keys = [k for k, v in dic.items() if v == c]
keys.sort()
for j in range(len(keys)):
 print(keys[j])
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    num = list(range(1, n+1))

    for i in range(1, n+1):
        for index, j in enumerate(a, 1):
            if i == j:
                print(index, sep="", end=" ")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))     # 出席番号順
    turn = [0]*(n+1)

    for index, j in enumerate(a, 1):
        turn[j] = index
    print(*turn[1:], sep=" ")


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

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
AA =[]
c =False
for a in input().strip().split():
    a = int(a)
    if not c:
        AA.append(a)
        if len(AA) == k:
            c = True
    else:
        base = AA[0]
        next = a
        if next - base > 0:
            print("Yes")
        else:
            print("No")
        AA = AA[1:]
        AA.append(a)


### FIXED CODE ###

n, k = map(int, input().split())
AA =[int(a) for a in input().split()]


for b, t in zip(AA, AA[k:]):
    if t > b:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

K = int(input())
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
r = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    ab = calcgcd(a, b)
    for c in range(1, K+1):
      g = calcgcd(ab, c)
      r += g
print(r)


### FIXED CODE ###

K = int(input())
def calcgcd(a, b):
  if a > b:
    a, b = b, a
  while a > 0:
    a, b = b%a, a
  return b
r = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    ab = calcgcd(a, b)
    for c in range(1, K+1):
      g = calcgcd(ab, c)
      r += g
print(r)
### BUGGY CODE ###

input()
words = input().split(" ")
for w in words:
  if words.count(w) >= 2:
    print("NO")
    exit()
print("YES")

### FIXED CODE ###

len1 = int(input())
len2 = len(set(input().split(" ")))
if len1 == len2:
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

def main():
    N = int(input())
    for n in range(1, N+1):
        cur = 0
        for x in range(1, N+1):
            if n < x**2:
                break
            for y in range(1, N+1):
                if n < x**2 + y**2 + x*y:
                    break
                for z in range(1, N+1):
                    if n < x**2 + y**2 + z**2 + x*y + y*z + z*x:
                        break
                    if n == x**2 + y**2 + z**2 + x*y + y*z + z*x:
                        cur += 1
        print(cur)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    ans = [0]*(N+1)
    for x in range(1, N+1):
        if N < x**2:
            break
        for y in range(1, N+1):
            if N < x**2 + y**2 + x*y:
                break
            for z in range(1, N+1):
                if N < x**2 + y**2 + z**2 + x*y + y*z + z*x:
                    break
                ans[x**2 + y**2 + z**2 + x*y + y*z + z*x] += 1

    print(*ans[1:], sep="\n")


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

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意
n,q = [int(i) for i in readline().split()]
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = map(int,input().split())
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = map(int,input().split())
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline #文字列入力のときは注意

n,q = [int(i) for i in readline().split()]
p = []
x = []
arr = [[] for i in range(n)]
ans = [0 for i in range(n)]
omosa = [0 for i in range(n)]

for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    arr[a-1].append(b-1)
    arr[b-1].append(a-1)
for i in range(q):
    tmpp,tmpx = [int(i) for i in readline().split()]
#    p.append(tmpp-1)
#    x.append(tmpx)
    omosa[tmpp-1] += tmpx

#for i in range(q):
#    omosa[p[i]] +=x[i]

def dfs(start, oya, weight): #weightは自分より上のノードの重さの和
    ans[start] = weight + omosa[start]
    for child in arr[start]:
        if child != oya:
            dfs(child, start, ans[start])
 
dfs(0,-1,0)
print(*ans)
### BUGGY CODE ###

L,R=map(int,input().split())

ans=2018
i=L
while i<R:
    j=i+1
    while j<=R:
        if i*j%2019==0:
            ans=0
            break
        else:
            ans=min(ans,i*j%2019)
            j+=1
    i+=1

print(ans)

### FIXED CODE ###

L,R=map(int,input().split())

ans=2018
i=L
while i<R:
    j=i+1
    while j<=R:
        if i*j%2019==0:
            ans=0
            break
        else:
            ans=min(ans,i*j%2019)
            j+=1
    i+=1
    if ans==0:
        break

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

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    ans = 0
    while que:
        # print(A)
        # print(len(que))
        q = []
        for h, w in que:
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for d in range(4):
                nh = min(max(0, h + dx4[d]), H - 1)
                nw = min(max(0, w + dy4[d]), W - 1)

                if A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        que = q

        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    checked = [[False] * W for _ in range(H)]
    ans = 0

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' and not checked[h][w]:
                que.append((h, w))
                checked[h][w] = True
    while que:
        next_que = []
        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and A[next_h][next_w] == '.' and not checked[next_h][next_w]:
                    A[next_h][next_w] = '#'
                    checked[h][w] = True
                    next_que.append((next_h, next_w))
        que = next_que
        if que:
            ans += 1

    print(ans)


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

from queue import Queue
INF = 10 ** 6 + 1
H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1-1][y1-1] = 0
tx = [1,0,-1,0]
ty = [0,1,0,-1]

q = Queue()
q.put([x1-1,y1-1,0])

while not q.empty():
    x, y, k = q.get()
    if x == x2 - 1 and y == y2 - 1:
        break
    for i in range(4):
        nx = x
        ny = y
        for _ in range(K):
            nx += tx[i]
            ny += ty[i]
            if (not (0 <= nx <= H-1 and 0 <= ny <= W-1)) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
                break
            D[nx][ny] = k + 1
            q.put([nx, ny, k+1])

if D[x2-1][y2-1] == INF:
    print(-1)
else:
    print(D[x2-1][y2-1])

### FIXED CODE ###

from queue import Queue
INF = 10 ** 6 + 1
H, W, K = map(int,input().split())
x1, y1, x2, y2 = map(int,input().split())
MAP = []
for _ in range(H):
    MAP.append(list(input()))
D = [[INF for i in range(W)] for j in range(H)]
D[x1-1][y1-1] = 0
tx = [1,0,-1,0]
ty = [0,1,0,-1]

q = Queue()
q.put([x1-1,y1-1,0])

while not q.empty():
    x, y, k = q.get()
    if x == x2 - 1 and y == y2 - 1:
        break
    for i in range(4):
        nx = x
        ny = y
        for _ in range(K):
            nx += tx[i]
            ny += ty[i]
            if (not (0 <= nx <= H-1 and 0 <= ny <= W-1)) or MAP[nx][ny] == '@' or D[nx][ny] < k + 1:
                break
            if D[nx][ny] == k + 1:
                continue
            D[nx][ny] = k + 1
            q.put([nx, ny, k+1])

if D[x2-1][y2-1] == INF:
    print(-1)
else:
    print(D[x2-1][y2-1])
### BUGGY CODE ###

S = input()
ans = 0
i = 0
f = False
while i < len(S):
  t = 0
  for j in range(i+4,len(S)+1):
    if int(S[i:j]) % 2019 == 0:
      ans += 1
      t = j-i-1
      f = True
  if f:
    i += t
    f = False
  else:
    i += 1
print(ans)

### FIXED CODE ###

S = input()[::-1]
digits = 1
num, ans = 0, 0
mod_list = [0] * 2019
mod_list[0] = 1

for c in S:
  num += int(c) * digits
  mod_list[num % 2019] += 1
  digits *= 10
  digits %= 2019

for i in range(2019):
  ans += mod_list[i] * (mod_list[i] - 1) // 2
  
print(ans)
### BUGGY CODE ###

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

Ai_i = []

for i in range(len(A)):
    Ai_i.append(A[i] - (i+1))

#max_abs = 0
#for i in range(len(Ai_i)):
#    if abs(Ai_i[i]) > max_abs:
#        max_abs = abs(Ai_i[i])

min_ = min(Ai_i)
max_ = max(Ai_i)

if min_ <= 0 and max_ <= 0:
    max_ = max([abs(min_), abs(max_)])

if min_ >= 0 and max_ >= 0:
    min_ = min([-abs(min_), -abs(max_)])    

min_abs = float("inf")
min_index = 0

for b in range(min_, max_+1):
    abss = []
    for i in range(len(Ai_i)):
        abss.append(abs(Ai_i[i] + b))
    abs_sum = sum(abss)
    if abs_sum < min_abs:
        min_abs = abs_sum

print(min_abs)

### FIXED CODE ###

from math import ceil, floor
import statistics

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

Ai_i = [0 for i in range(len(A))]

for i in range(len(A)):
    Ai_i[i] = A[i] - (i+1)

n = 5

b_ceil = ceil(sum(Ai_i) / len(Ai_i))

bs = list(range(b_ceil-n, b_ceil+n))

bs = [int(statistics.median(Ai_i))]
abss_ls = [ 0 for i in range(len(bs)) ]
for i in range(len(bs)):
    for j in range(len(Ai_i)):
        abss_ls[i] += abs(Ai_i[j] - bs[i])

min_abs = min(abss_ls)
print(min_abs)
### BUGGY CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)

### FIXED CODE ###



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

Rcnt = 0
Gcnt = 0

excep = 0

for i in range(len(S)):
    if S[i] == 'R':
        Rcnt += 1
    elif S[i] == 'G':
        Gcnt += 1
    for j in range(1, len(S)):
        if i+j+j < len(S) and S[i] != S[i+j]:
            if S[i] != S[i+j+j] and S[i+j] != S[i+j+j]:
                excep += 1
        elif i+j+j >= len(S):
            break

print(Rcnt * Gcnt * (N - Rcnt - Gcnt) - excep)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    bisect.insort(STX, (X, S, T))

kensaku = dict()
for i in range(Q):
    D.append(int(input()))
    kensaku[D[-1]] = i

dist = [10000000000000 for i in range(Q)]

for i in range(N):
    s = STX[i][1] - STX[i][0]
    t = STX[i][2] - STX[i][0] - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    for j in range(a, b):
        dist[kensaku[D[j]]] = min(dist[kensaku[D[j]]], STX[i][0])
    del D[a:b]


for i in range(Q):
    if dist[i] > 100000000000:
        print(-1)
    else:
        print(dist[i])

### FIXED CODE ###

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 9)


N, Q = list(map(int, input().split()))
STX=[]
D=[]
for i in range(N):
    S, T, X = list(map(int, input().split()))
    STX.append((X, S, T))
STX = sorted(STX, key=lambda x: x[0])

for i in range(Q):
    D.append(int(input()))

skip = [-1]*Q

dist = [-1]*Q

for X, S, T in STX:
    s = S - X
    t = T - X - 1
    a = bisect.bisect_left(D, s)
    b = bisect.bisect_right(D, t)
    #print(D)
    j = a
    while j < b:
        if skip[j] == -1:
            skip[j] = b
            dist[j] = X
            j+=1
        else:
            j=skip[j]


for i in range(Q):
    print(dist[i])
### BUGGY CODE ###

n = int(input())
ListL = [int(i) for i in input().split()]

ListL.sort()

ans = 0
for i in range(n-2):
	a = ListL[i]
	for j in range(i+1, n-1):
		b = ListL[j]
		maxC = a + b - 1
		minC = abs(a-b) + 1
		for k in range(j+1, n):
			c = ListL[k]
			if(c < minC):
				continue
			elif(c > maxC):
				break
			else:
				ans += 1

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
ListL = [int(i) for i in input().split()]

ListL.sort()
ans = 0

for i in reversed(range(2, n)):
	a = ListL[i]
	for j in reversed(range(1, i)):
		b = ListL[j]
		index = bisect.bisect_right(ListL, a-b)
		#print(a, b)
		if (index >= j):
			break
		else:
			ans += j - index

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

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

counter = 0
sum = 0
rest = K
while True:
    #print("counter: ", counter, "sum: ", sum, "rest: ", rest)
    if rest == 0:
        break

    if counter < A:
        #print("Add 1")
        sum += 1
    elif counter < A + B:
        #print("Do nothing")
        pass
    else:
        #print("Subtract 1")
        sum -= 1
    counter += 1
    rest -= 1
print(sum)


### FIXED CODE ###

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


if 0 < K <= A:
    print(K)
elif A < K < A + B:
    print(A)
else:
    C_num = K - (A + B)
    print(A - C_num)