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

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  n=len(pt)
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

print(ans)

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

def Z_algo(S):
  n=len(S)
  A=[0]*n
  A[0]=n
  i=1
  j=0
  while i<n:
    while i+j<n and S[j]==S[i+j]: j+=1
    A[i]=j
    if j==0:
      i+=1
      continue
    k=1
    while i+k<n and k+A[k]<j:
      A[i+k]=A[k]
      k+=1
    i+=k
    j-=k
  return A

def dfs(pt,v,visited):
  if visited[v]==True:
    return -1,visited
  S = [v]
  now = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if i != v:
        visited[i] = True
        now += 1
        S.append(i)
      else:
        print(-1)
        exit()
  return now,visited

s = str(input())
t = str(input())

ls = len(s)
lt = len(t)

s2 = t + s*(lt//ls +2)
A = Z_algo(s2)

B = [False]*ls
for i in range(ls):
  if A[i+lt]>=lt:
    B[i]=True

pt = [[] for _ in range(ls)]
for i in range(ls):
  if B[i]==True:
    pt[i].append((i+lt)%ls)

visited = [False]*ls

ans = 0
for v in range(ls):
  if B[v]:
    tmp,visited = dfs(pt,v,visited)
    if tmp>ans:
      ans = tmp

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

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import lil_matrix, csr_matrix
N = int(input())
L = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N-1):
  a, b, c = map(int, input().split())
  L[a-1][b-1] = c
  L[b-1][a-1] = c
L = csr_matrix(L)
L = floyd_warshall(L, 0)
Q, K = map(int, input().split())
K -= 1
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print (int(L[x][K] + L[K][y]))

### FIXED CODE ###

from collections import defaultdict as dd
from collections import deque
N = int(input())
D =dd(list)
for i in range(N-1):
  a, b, c = map(int, input().split())
  D[a-1].append((b-1, c))
  D[b-1].append((a-1, c))

Q, K = map(int, input().split())
K -= 1
L = [0 for _ in range(N)]
q = deque([])
q.append(K)
while len(q) > 0:
  a = q.pop()
  for b, c in D[a]:
    if L[b] == 0:
      L[b] = L[a] + c
      q.append(b)

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

from collections import defaultdict
import sys
import math
from datetime import datetime


class TreeNode:
    def __init__(self):
        self.val = 0
        self.vertex = []
trees = []
def make_trees(n, A, B):
    global trees
    trees = []
    for i in range(n):
        trees.append(TreeNode())
    for i in range(len(A)):
        a = A[i]-1
        b = B[i]-1
        trees[a].vertex.append(b)
    return trees

def dfs(node: TreeNode, x: int):
    if node:
        node.val += x
        for i in node.vertex:
            dfs(trees[i], x)


def sol(n, q, A, B, P, X):
    make_trees(n, A, B)
    for i in range(len(P)):
        p = P[i]-1
        x = X[i]
        t = trees[p]
        # dfs, give point x
        dfs(t, x)
    #
    return " ".join([str(t.val)  for t in trees])
    #return n, q, A, B, P, X



do_submit = True
#do_submit = False

def input_parse(input_str):
    lines = [x.strip() for x in input_str.split("\n") if x.strip()]
    parsed_lines = [list(map(str, line.split())) for line in lines]
    print(parsed_lines)
    n = int(parsed_lines[0][0])
    q = int(parsed_lines[0][1])
    A = []
    B = []
    P = []
    X = []
    for i in range(1, n-1+1):
        a = int(parsed_lines[i][0])
        b = int(parsed_lines[i][1])
        A.append(a)
        B.append(b)
    for i in range(n, 1+n+q-1):
        p = int(parsed_lines[i][0])
        x = int(parsed_lines[i][1])
        P.append(p)
        X.append(x)

    # S = parsed_lines[1][0]
    # return n, k, S
    return n, q, A, B, P, X


if not do_submit:
    n, q, A, B, P, X = input_parse("""
    4 3
    1 2
    2 3
    2 4
    2 10
    1 100
    3 1
    """)
    print(sol(n, q, A, B, P, X))

    n, q, A, B, P, X = input_parse("""
        6 2
        1 2
        1 3
        2 4
        3 6
        2 5
        1 10
        1 10
    """)
    print(sol(n, q, A, B, P, X))

else:
    # n = int(input().strip())
    # q = int(input().strip())
    n, q = list(map(int, input().split()))
    A = []
    B = []
    P = []
    X = []
    for i in range(n-1):
        a, b = list(map(int, input().split()))
        # a = int(input().strip())
        # b = int(input().strip())
        A.append(a)
        B.append(b)
    for i in range(q):
        p, x = list(map(int, input().split()))
        # p = int(input().strip())
        # x = int(input().strip())
        P.append(p)
        X.append(x)
    print(sol(n, q, A, B, P, X))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
n, q = map(int, input().split())
 
ki = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    ki[a].append(b)
    ki[b].append(a)
# print(ki)
 
cnt = [0] * (n + 1)
for i in range(q):
    p, x = map(int, input().split())
    cnt[p] += x
 
 
# print(cnt)
 
 
def d(y, parent):
    for i in ki[y]:
        if i == parent:
            continue
        cnt[i] += cnt[y]
        d(i, y)
 
 
d(1, -1)
print(*cnt[1:])
### BUGGY CODE ###

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


shusseki_jun = [str(A.index(str(i))+1) for i in range(1,N+1)]
print(' '.join(shusseki_jun))


### FIXED CODE ###

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

shusseki_jun=[' ' for _ in range(N)]
for i in range(N):
    ind = A[i]
    shusseki_jun[int(ind)-1] = str(i+1)

print(' '.join(shusseki_jun))
### BUGGY CODE ###

S = input()

dp = [[0,0,0,0,0,0,0,0,0,0,0,0,0] for i in range(len(S) + 2)]
INF = 10**9 + 7
for num, dig in enumerate(S):
    if num == 0:
        if dig == '?':
            dp[num] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
        else:
            dp[num] = [0,0,0,0,0,0,0,0,0,0,0,0,0]
            dp[num][int(dig)] = 1

    elif dig == '?':
        for j in range(10):
            for i in range(13):
                dp[num][(i * 10 + j) % 13] += dp[num - 1][i] % INF
                dp[num][(i * 10 + j) % 13] %= INF

    else:
        for i in range(13):
            dp[num][(i*10 + int(dig))%13] += dp[num - 1][i] % INF
            dp[num][(i * 10 + int(dig)) % 13] %= INF

print(dp[len(S)-1][5])

### FIXED CODE ###

S = input()

dp = [[0,0,0,0,0,0,0,0,0,0,0,0,0] for i in range(len(S) + 2)]
INF = 10**9 + 7
for num, dig in enumerate(S):
    if num == 0:
        if dig == '?':
            dp[num] = [1,1,1,1,1,1,1,1,1,1,0,0,0]
        else:
            dp[num] = [0,0,0,0,0,0,0,0,0,0,0,0,0]
            dp[num][int(dig)] = 1

    elif dig == '?':
        for j in range(10):
            for i in range(13):
                dp[num][(i * 10 + j) % 13] += dp[num - 1][i] % INF
                dp[num][(i * 10 + j) % 13] %= INF

    else:
        for i in range(13):
            dp[num][(i*10 + int(dig))%13] += dp[num - 1][i] % INF
            dp[num][(i * 10 + int(dig)) % 13] %= INF

print(dp[len(S)-1][5])
### BUGGY CODE ###

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

ans = 0
div_v = 10 ** 9 + 7
for i in range(N-1):
    for j in range(i+1, N):
        ans += A[i] ^ (A[j]) 
print(ans % div_v)

### FIXED CODE ###

# python3.4.2用
import math
import fractions
import collections
import itertools
import heapq
import string
import sys
import copy
import numpy as np
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')

N = iin()
A = np.array(sys.stdin.readline().split(), np.int64)

two_factor = 1
ans = 0
for i in range(60):
    B = A >> i & 1
    ones = np.count_nonzero(B)
    zeros = N - ones
    zeroone_cmb = ones*zeros%MOD
    ans = (ans + (zeroone_cmb*two_factor%MOD))%MOD
    two_factor = (two_factor*2)%MOD

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

import sys
import itertools
from collections import Counter

sys.setrecursionlimit(10**6)

def DFS(i,v,d):
  global dist
  
  if d > N:
    return
  # 頂点vに隣接する頂点でvより大きいものが未発見
  for u in adj[v]:
    # distは最短距離なので上書き禁止
    if i != u:
      #print(i,u,d)
      if dist[i][u] > d:
        dist[i][u] = d
        dist[u][i] = d
        # その先は追加で探索
      DFS(i,u,d+1)

N, X, Y = map(int, input().split())

# 隣接リストを作成する
adj = [[] for _ in range(N)]

# adjに入力
for i in range(N-1):
  adj[i].append(i+1)
  adj[i+1].append(i)

# X,Yをadj入力
adj[X-1].append(Y-1)
adj[Y-1].append(X-1)

# 頂点間の最短距離を保持するdist
dist = [[10**9 for _ in range(N)] for _ in range(N)]
for i in range(N):
  DFS(i,i,1)

  
# print(dist)
# distを１次元化
dist = list(itertools.chain.from_iterable(dist))
c = Counter(dist)

# 結果出力
for k in range(1,N):
  print(c[k]//2)
  

### FIXED CODE ###

N, X, Y = map(int, input().split())
ans = [0] * N

for i in range(N):
  for j in range(i+1, N):
    tmp = min(j-i, abs(X-1-i) + 1 + abs(Y-1-j))
    ans[tmp] += 1

for k in range(1,N):
  print(ans[k])
### BUGGY CODE ###

s = input()
t = input()
m = len(s)
n = len(t)

dp = [[-1]*(n+1) for i in range(m+1)]
dp[0][0] = 0
for i in range(n+1):
    dp[0][i] = 0
for i in range(m+1):
    dp[i][0] = 0
ans = [[""]*(n+1) for i in range(m+1)]
for i in range(1,m+1):
    for j in range(1,n+1):
        if s[i-1] == t[j-1]:
            ans[i][j] = ans[i-1][j-1] + t[j-1]
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            if dp[i-1][j] < dp[i][j-1]:
                dp[i][j] = dp[i][j-1]
                ans[i][j] = ans[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]
                ans[i][j] = ans[i-1][j]

print(ans[m][n])

### FIXED CODE ###

s = input()
t = input()
s_length = len(s)
t_length = len(t)

dp = [[0 for j in range(t_length+1)] for i in range(s_length+1)]
#dp[i][j] = s[:i]とt[:j]に置けるLCS
for i in range(s_length):
    for j in range(t_length):
        if s[i] == t[j]:
            dp[i+1][j+1] = dp[i][j]+1
        else:
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])

#print(dp)
#print(dp[s_length][t_length])

ans = ""
i = s_length
j = t_length
while i>0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        ans = s[i] + ans

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

r,g,b,n = map(int, input().split())

count = 0
r,g,b = sorted([r, g, b], reverse=True)

for i in range(n // r + 1):
    total = r * i
    for j in range((n - total)//g + 1):
        total = r * i + g * j
        for k in range((n - total)//b + 1):
            total = r * i + g * j + b * k
            if total == n:
                count += 1

print(count)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

count = 0
r, g, b = sorted([r, g, b], reverse=True)


for i in range(n // r + 1):
    rc = r * i
    for j in range((n - rc) // g + 1):
        gc = g * j
        if (n - rc - gc) % b == 0:
            count += 1
print(count)
### BUGGY CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
a=0
for i in range(n):
    for j in range(i+1,n):
        a=a+c[i]*c[j]
print(a%(10**9+7))

### FIXED CODE ###

n=int(input())
c = list(map(int, input().rstrip().split()))
ans=0
b=10**9+7
sum1=0
for i in range(n):
    ans=(ans+c[i]*sum1)%b
    sum1=(sum1+c[i])%b

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

N, M= map(int, input().split())
L1, R1= map(int, input().split())
Ans = list(range(L1, R1+1))

for x in range(M-1):
    L, R = map(int, input().split())
    List = list(range(L, R+1))
    Ans = list(set(Ans) & set(List))

print(len(Ans))

### FIXED CODE ###

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

for x in range(M-1):
    L, R = map(int, input().split())
    if L > L1:
        L1 = int(L)
    if R < R1:
        R1 = int(R)

if R1 == L1:
    print("1")
if L1 > R1:
    print("0")
if L1 < R1: 
	print(R1-L1+1)
### BUGGY CODE ###

import sys

input = sys.stdin.readline


def binary_search(a, key):
    """Meguru type binary search"""
    ng = -1
    ok = len(a)

    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if a[mid] >= key:
            ok = mid
        else:
            ng = mid

    return ok


def solve(N, L):
    L.sort()
    ans = 0
    for a in range(N - 2):
        for b in range(a + 1, N - 1):
            c = binary_search(L, L[a] + L[b]) - 1
            ans += c - b
    return ans


def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = solve(N, L)
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.readline


def main():
    N = int(input())
    L = list(map(int, input().split()))

    L.sort()
    ans = 0
    for i in range(N - 1):
        a = L[i]
        for j in range(i + 1, N):
            k = bisect_left(L, a + L[j])
            ans += (k - 1 - j)

    print(ans)


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

import numpy as np

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

scores = np.array([k for _ in range(n)])

for _ in range(q):
  a = int(input())
  scores -= 1
  scores[a-1] += 1

for s in scores:
  if s > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

d = {}

for _ in range(q):
  a = int(input())
  d[a-1] = d.get(a-1, 0) + 1

scores = [k-q for _ in range(n)]
for key in d:
  scores[key] += d[key]

for s in scores:
  if s > 0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

n, m = map(int, input().split())
s = input()
t = input()
if n == m and s == t:
    print(n)
elif max(n, m) % min(n, m) == 0:
    print(-1)
else:
    LCM = lcm(n, m)
    for i in range(1, m + 1):
        L = LCM * i
        x = ["" for i in range(L)]
        no = 0
        for i in range(n):
            x[i * L // n] = s[i]
        for i in range(m):
            if x[i * L // m] and x[i * L // m] != t[i]:
                no = 1
                break
            else:
                x[i * L // m] = t[i]
        if no:
            continue
        print(L)
        exit()

### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

n, m = map(int, input().split())
s = input()
t = input()
L = lcm(n, m)
l = lcm(L // n, L // m)
for i in range(0, L, l):
    if s[i // (L // n)] != t[i // (L // m)]:
        print(-1)
        exit()
print(L)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(int(1e5+10))

def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] = g.get(a, []) + [(b, c)]
        g[b] = g.get(b, []) + [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

    for x, y in cood:
        print(dist[x]+dist[y])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(int(1e5+10))

def search_dist(g, dist, e):
    for b, c in g.get(e):
        if dist[b] is not None:
            continue
        dist[b] = dist[e] + c
        search_dist(g, dist, b)

def main():
    g = {}
    N = int(input())
    for i in range(N+1):
        g[i] = []
    for _ in range(N-1):
        a, b, c = list(map(int, input().split(' ')))
        g[a] += [(b, c)]
        g[b] += [(a, c)]
    Q, K = list(map(int, input().split(' ')))
    dist = [None]*(N+1)
    dist[K] = 0
    search_dist(g, dist, K)
    cood = []
    for _ in range(Q):
        cood.append(list(map(int, input().split(' '))))

    for x, y in cood:
        print(dist[x]+dist[y])

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

from sys import stdin

def gcd(a,b):
    if a<b:
        tmp=a
        a=b
        b=tmp
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=gcd(i,gcd(j,k))
print(str(ans)+"\n")

### FIXED CODE ###

from sys import stdin

def gcd(a,b):
    if a<b:
        tmp=a
        a=b
        b=tmp
    r=a%b
    while r!=0:
        a=b
        b=r
        r=a%b
    return b

k=int(input())
ans=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            ans+=gcd(i,gcd(j,k))
print(str(ans)+"\n")
### BUGGY CODE ###

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

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

### FIXED CODE ###

import sys

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

if 0 in A:
    print(0)
else:
    x = 1
    for i in range(N):
        x = x * A[i]
        if x>10**18:
            print(-1)
            sys.exit()
        
    print(x)
### BUGGY CODE ###

import itertools

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

a = tuple(itertools.combinations(lis,3))
b = 0

for i in a:
    if i[0] < i[1] + i[2] and i[1] < i[2] + i[0] and i[2] < i[0] + i[1]:
        b += 1
print(b)


### FIXED CODE ###

import bisect

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

a = sorted(lis, reverse=True)
c = sorted(lis)
d = 0

for i in range(n):
    for j in range(i + 1, n):
        e = c[:-j-1]
        b = bisect.bisect_right(e, int(a[i]-a[j]))
        d += max(0, len(e) - b)
print(d)
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

a=[0]*(n+1)
for i in range(2,n+1):
    if s[i-2]=='A' and s[i-1]=='C':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]

for i in range(Q):
    l,r=map(int,input().split())
    print(a[r]-a[l])
### BUGGY CODE ###

a = list(map(int, input().split()))
r = a[0]
g = a[1]
b = a[2]
n = a[3]
c = 0

for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            if n == r*i + g*j + b*k:
                c += 1
print(c)

### FIXED CODE ###

a = list(map(int, input().split()))
r = a[0]
g = a[1]
b = a[2]
n = a[3]
c = 0

for i in range(n+1):
    for j in range(n+1):
        k = (n - (r*i + g*j))//b
        if k >= 0:
            if n == r*i + g*j + b*k:
                c += 1
print(c)
### BUGGY CODE ###

import bisect


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N - bisect.bisect_right(A, y, lo=n + 1)
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += bisect.bisect_left(A, y, lo=n + 1) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)
### BUGGY CODE ###

N = int(input())
s = []
ans = [0]*N
for n in range(N):
  chars = sorted(list(input()))

  if chars in s:
    ans[s.index(chars)] += 1
  else:
    s.append(chars)

for idx,x in enumerate(ans):
  ans[idx] = x * (x+1) // 2
print(sum(ans))

### FIXED CODE ###

N = int(input())
s = {}
ans = 0
for n in range(N):
  chars = str(sorted(list(input())))

  if chars in s:
    s[chars] += 1
  else:
    s[chars] = 0
    
for value in s.values():
  ans += value * (value+1) // 2
  
print(ans)
### BUGGY CODE ###

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

flags = [True] * (A[-1] + 1)

for a in A:
    if A.count(a) > 1:
        flags[a] = False
    for mul in range(2, A[-1] // a + 1):
        flags[a * mul] = False
print(sum([flags[a] for a in A]))

### FIXED CODE ###

from collections import Counter

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

flags = [True] * (A[-1] + 1)

for a in A:
    for mul in range(2, A[-1] // a + 1):
        flags[a * mul] = False
print(sum([flags[a] and c[a] == 1 for a in A]))