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

import sys
readline = sys.stdin.readline
V, E = map(int, readline().split())
g = [[] for i in xrange(V)]
cost = {}
to = [0]*V
for i in xrange(E):
    s, t, d = map(int, readline().split())
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = -1
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        res = get((v, start), INF)
        dp[key] = res
        return res
    if state & to[v] != to[v]:
        res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t)))
    else:
        res = INF
    dp[key] = res
    return res
def solve(v):
    global dp, start
    dp = {}
    start = v
    return dfs(1<<v, v)
res = min(solve(v) for v in xrange(V))
print res if res<INF else -1

### FIXED CODE ###

import sys
readline = sys.stdin.readline
V, E = map(int, readline().split())
g = [[] for i in xrange(V)]
cost = {}
to = [0]*V
for i in xrange(E):
    s, t, d = map(int, readline().split())
    g[s].append((t, d))
    cost[s,t] = d
    to[s] |= 1 << t
get = cost.get
INF = 10**9
ALL = 2**V-1
dp = {}
start = 0
def dfs(state, v):
    key = (state, v)
    if key in dp: return dp[key]
    if state == ALL:
        dp[key] = res = get((v, start), INF)
        return res
    dp[key] = res = min((dfs(state | (1 << t), t) + d for t, d in g[v] if not state & (1 << t))) if state & to[v] != to[v] else INF
    return res
res = dfs(1, 0)
print res if res<INF else -1
### BUGGY CODE ###

import numpy as np

s = input()[::-1]

dp = np.zeros((len(s),13), dtype="uint64")

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

L1 = range(1, len(s))

for i in L1:
    if s[i] == "?":
        mod = pow(10, i, 13)
        mod_list = ((mod*i)%13 for i in range(10))
        for j in mod_list:
            dp[i, :] += np.roll(dp[i - 1, :], j)
        dp[i, :] %= (10**9+7)
    else:
        mod = (pow(10, i, 13)*int(s[i]))%13
        dp[i, :] += np.roll(dp[i - 1, :], mod)

print(int(dp[-1][5])%(10**9+7))


### FIXED CODE ###

s=input()
l=len(s)

mod=10**9+7

dp=[[0 for j in range(13)] for i in range(l)]

if s[0] =="?":
    dp[0] = [1]*10+[0]*3
else:
    dp[0][int(s[0])] =1

for i in range(1, l):
 if s[i]=='?':
   for j in range(10):
     for k in range(13):
       dp[i][(k*10+j)%13]+=dp[i-1][k]%mod
 else:
   for k in range(13):
     dp[i][(k*10+int(s[i]))%13]+=dp[i-1][k]%mod
print(dp[-1][5]%mod)
### BUGGY CODE ###

def nibu(list,item):

    high=len(list)-1

    low=0
    while low <= high:
        mid=(low+high)//2
        guess=list[mid]
        if guess==item:
            return mid+1
            break
        elif guess < item:
            low = mid +1
        elif guess > item:
            high = mid - 1
    if guess != item:
        return high+1



n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
Bs=[]
s=0
for i in range(n):
    Bs.append(n-nibu(C,B[i]))
for i in range(n):
    Bss=Bs[:]
    Bss=Bs[nibu(B,A[i]):]
    s+=sum(Bss)
print(s)


### FIXED CODE ###

N=map(int,input().split())
A=sorted(list(map(int,input().split())))
B=list(map(int,input().split()))
C=sorted(list(map(int,input().split())))
 
def countA(target,L):
  ok=-1
  ng=len(L)
  while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if L[mid]<target:
      ok=mid
    else:
      ng=mid
  return (ok+1)
 
def countC(target,L):
  ok=len(L)
  ng=-1
  while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if L[mid]>target:
      ok=mid
    else:
      ng=mid
  return len(L)-ok
 
ans=0
for i in range(len(B)):
  data=B[i]
  ans+=(countA(data,A)*countC(data,C))
  
print(ans)
### BUGGY CODE ###

n=int(input())
aa=list(map(int,input().split()))
accumulation=[]
total=0

for i in range(n):
    aacut=aa[:(i+1)]
    accumulation.append(sum(aacut))

for i in range(n):
    total+=aa[i]*(accumulation[n-1]-accumulation[i])

x=10**9+7
ans=total%x
print(ans)

### FIXED CODE ###

n=int(input())
aa=list(map(int,input().split()))
su=sum(aa)
new=[n**2 for n in aa]
sa=sum(new)
x=10**9+7
print((su**2-sa)//2%x)
sa
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    n = int(input())
    aa = list(map(int, input().split()))
    dp = [[0] * n for _ in range(n)]
    for i, a in enumerate(aa):
        dp[i][i] = a
    # p2D(dp)
    for d in range(1, n):
        for l in range(n - 1):
            r = l + d
            if r >= n: break
            dp[l][r] = max(aa[l] - dp[l + 1][r], aa[r] - dp[l][r - 1])
    # p2D(dp)
    print(dp[0][-1])

main()


### FIXED CODE ###

def kukan(n, a):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = a[i]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            L = a[i] - dp[i + 1][j]
            R = a[j] - dp[i][j - 1]
            dp[i][j] = L if L > R else R
    return dp[0][n - 1]


n = int(input())
a = list(map(int, input().split()))
print(kukan(n, a))
### BUGGY CODE ###

from operator import mul
from functools import reduce

N,K = map(int,input().split())
A = list(map(int,input().split()))  
tempA = reduce(mul, A[0:K])

for i in range(N - K):
  mulA = reduce(mul, A[i+1:K+i+1])
  if tempA < mulA:
    print('Yes')
  else:
    print('No')
  tempA = mulA


### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))  
for i in range(N - K):
  if A[i] < A[K+i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]or d[t]<p:break
   q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()

for i in range(len(S)//2+1):
    S_ = S.replace('ST', '', 1)
    if S_ == S:
        break
    S = S_

print(len(S))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

S = input()
'''
f_cnt = b_cnt = 0
for m in S:
    if m != 'T':
        break
    f_cnt += 1

for m in S[::-1]:
    if m != 'S':
        break
    b_cnt += 1
print(max(f_cnt, b_cnt) * 2)
'''
s_cnt = 0
for m in S:
    if m == 'S':
        s_cnt += 1
    elif m == 'T' and s_cnt > 0:
        s_cnt -= 1

print(2*s_cnt)
### BUGGY CODE ###

k,s=map(int, input().split())
t=0
for i in range(k+1):
    for j in range(k+1):
        if 0<=i<=k and 0<=j<=k and 0<=s-i-j<=k:
            t+=1
print(t)


### FIXED CODE ###

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

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
A = [0] + [int(input()) for _ in range(N)]

cur = 1
ans = 0
pushed = [False] * (N + 1)
pushed[1] = True
ok = True
while True:
    ans += 1
    cur = A[cur]
    if cur == 2:
        break
    if pushed[cur]:
        ok = False
        break

if ok:
    print(ans)
else:
    print(-1)

        



### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
A = [0] + [int(input()) for _ in range(N)]

cur = 1
ans = 0
pushed = [False] * (N + 1)
pushed[1] = True
ok = True
while True:
    pushed[cur] = True
    ans += 1
    cur = A[cur]
    if cur == 2:
        break
    if pushed[cur]:
        ok = False
        break

if ok:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

# input
n = int(input())

c = []
dp = [0] * (n + 1)
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in c and c[-1] is not stone:
            plc = len(c) - 1 - c[::-1].index(stone)
            dp[i + 1] = dp[i] + dp[plc + 1]
        else:
            dp[i + 1] = dp[i]
    c.append(stone)

print(dp[-1])


### FIXED CODE ###

# input
n = int(input())

mod = pow(10, 9) + 7
c = []
dp = [0] * (n + 1)
stone_history = dict()
for i in range(n):
    stone = int(input())
    if len(c) == 0:
        dp[i + 1] = 1
    else:
        if stone in stone_history and c[-1] != stone:
            dp[i + 1] = dp[i] + stone_history[stone]
        else:
            dp[i + 1] = dp[i]

    stone_history[stone] = dp[i + 1]
    c.append(stone)

print(dp[-1] % mod)
### BUGGY CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    for y in range(min(s-x+1, k+1)):
        z = s - x - y
        if min(x, y, z) < 0 or z > k:
            continue
        ans += 1
print(ans)

### FIXED CODE ###

k, s = map(int, input().split())

ans = 0
for x in range(k+1):
    if 0 <= s - x <= k:
        ans += s-x+1
    elif 0 <= s-x-k <= k:
        ans += k - s + x + k + 1
    # print(x, ans)
print(ans)
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = list(readline().decode().rstrip())[::-1]
l = len(S)

cnt = 0
for _ in range(l - 1):
    for i in range(l - 1):
        if S[i:i + 2] == ['W', 'B']:
            S[i:i + 2] = ['B', 'W']
            cnt += 1

print(cnt)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

S = readline().decode().rstrip()

res = 0
b_cnt = 0

for c in S:
    if c == 'B':
        b_cnt += 1
    elif c == 'W':
        res += b_cnt

print(res)
### BUGGY CODE ###

import heapq as hp

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
pul=[0]*n
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)


for i in range(q):
  p,x=map(int,input().split())
  pul[p-1]+=x


ans=[0]*n
def dfs():
  val=0
  que=[[0,val]]
  done=[0]*n  

  while(que):
    now,val=que.pop(0)
    if done[now]==1:
      continue
    val+=pul[now]
    ans[now]=val
    done[now]=1

    for i in l[now]:
      if done[i]==0:
        que.append([i,val])

dfs()
print(*ans)


### FIXED CODE ###

n,q=[int(x) for x in input().rstrip().split()]
l=[[] for i in range(n)]
ans=[0]*n

for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x

def dfs():
  que=[0]
  done=[0]*n  
  done[0]=1
  while(que):
    now=que.pop()

    for i in l[now]:
      if done[i]==0:
        done[i]=1
        que.append(i)
        ans[i]+=ans[now]

dfs()
print(*ans)
### BUGGY CODE ###

n = int(input())
s = input()
r, g, b = [], [], []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
lr, lg, lb = len(r), len(g), len(b)
ans = lr * lg * lb
for i in r:
    for j in g:
        a = 2 * j - i
        c = 2 * i - j
        if 0 <= a and a <= n-1 and a in b:
            ans -= 1
        if 0 <= c and c <= n-1 and c in b:
            ans -= 1
        if (i + j) % 2 == 0 and (i + j) / 2 in b:
            ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r, g, b = [], [], []
for i in range(n):
    if s[i] == 'R':
        r.append(i)
    elif s[i] == 'G':
        g.append(i)
    else:
        b.append(i)
lr, lg, lb = len(r), len(g), len(b)
ans = lr * lg * lb

for i in r:
    for j in g:
        a = 2 * j - i
        c = 2 * i - j
        if 0 <= a and a <= n-1 and s[a] == 'B':
            ans -= 1
        if 0 <= c and c <= n-1 and s[c] == 'B':
            ans -= 1
        if (i + j) % 2 == 0 and s[int((i + j) / 2)] == 'B':
            ans -= 1
print(ans)
### BUGGY CODE ###

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

result = 0
route = []
for x in set(S):
    co = S.count(x)
    if co > 0:
        route.append(co)

for i in range(1,len(route)+1):
    xxx = result
    for cb in itertools.combinations(route, i):
        num = 1
        for x in cb:
            num = num * x
        result += num
    if xxx == result:
        break
print(result%(10**9+7))


### FIXED CODE ###

import collections
N = int(input())
S = input()

result = 1
route = [x+1 for _,x in collections.Counter(S).items()]
for x in route:
    result = result*x
print((result-1)%(10**9+7))
### BUGGY CODE ###

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

B=[]
C=[]
for i in range(q):
    b1,c1=map(int, input().split())
    B.append(b1)
    C.append(c1)

# print(A)
for i in range(q):
    A=[ C[i] if B[i]==a else a for a in A ]
    print(sum(A))


### FIXED CODE ###

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

asum = sum(A)
S={}
for i in range(len(A)):
    if A[i] in S:
        S[A[i]]+=1
    else:
        S[A[i]]=1

D=[]
q=int(input())
for i in range(q):
    diff=0
    b,c =map(int,input().split())
    if not c in S:
        S[c]=0
    if b in S:
        diff = (S[b]*c-S[b]*b)
        S[c]+=S[b]
        S[b]=0

    asum+=diff
    D.append(asum)

for d in D:
    print(d)
### BUGGY CODE ###

R,G,B,N = map(int,input().split(' '))
num = 0
for i in range(int(N//R)+1):
  for j in range(int(N//G)+1):
    A = N-R*i-G*j
    if A >= 0  and A % B == 0:
      num += 1
print(num)

### FIXED CODE ###

R,G,B,N = map(int,input().split(' '))
A,B,C = sorted([R,G,B])
if A==1 and B==1 and C ==1:
  print(int((N+2)*(N+1)/2))
  exit()
num = 0
E = int(N//C+1)
F = int(N//B+1)
for i in range(E):
  for j in range(F):
    X = N-C*i-B*j
    if X >= 0  and X % A == 0:
      num += 1
print(num)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
count = 0
for i in range(len(l)-2):
  for j in range(i+1, len(l)-1):
    for k in range(j+1, len(l)):
      if l[i]+l[j]>l[k] and l[j]+l[k] > l[i] and l[k] + l[i] > l[j]:
        count += 1
print(count)



### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
count = 0
l.sort(reverse = False)
for i in range(len(l)-1, 1, -1):
  for j in range(i-1, 0, -1):
    pt = bisect.bisect_right(l, l[i] - l[j])
    count += max(j - pt, 0)
print(count)
### BUGGY CODE ###

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

ans = S.count('R')*S.count('G')*S.count('B')

for i in range(N):
  for j in range(i+1, N):
    k = j + j - i
    if k < N :
      if (S[i] != S[j]) & (S[j] != S[k]) & (S[k] != S[i]) :
        ans -= 1

print(ans)

### FIXED CODE ###

from collections import Counter

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

cnt = Counter(S)

ans = cnt['R'] * cnt['G'] * cnt['B']

for i in range(N):
  for j in range(i+1, N):
    k = j + j - i
    if k < N :
      if (S[i] == S[j]) or (S[j] == S[k]) or (S[k] == S[i]) :
        continue
      ans -= 1

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

N, M = list(map(int, input("").split(" ")))
permit = [list(map(int, input("").split(" "))) for i in range(M)]
able = [0 for i in range(N)]
for i,j in permit:
  for k in range(i,j+1):
    able[k-1] += 1
print(able.count(M))


### FIXED CODE ###

N, M = list(map(int, input("").split(" ")))
permit = [list(map(int, input("").split(" "))) for i in range(M)]
l,r = 1, N
for i,j in permit:
  l = max(l, i)
  r = min(r, j)
print(max(r-l+1,0))
### BUGGY CODE ###

def shortest_path(s, n, es):
    d = [float('inf')] * n

    d[s] = 0
    while True:
        update = False
        for p, q in es:
            if d[p] != float('inf') and d[q] > d[p] + 1:
                d[q] = d[p] + 1
                update = True
        if not update:
            break
    return d

n, x, y = map(int, input().split())
es = [(x - 1, y - 1), (y - 1, x - 1)]
for i in range(n - 1):
    es.append((i, i + 1))
    es.append((i + 1, i))
length = [0] * (n - 1)
for i in range(n - 1):
    a = shortest_path(i, n, es)
    for l in range(i + 1, n):
        if a[l] != float('inf') and l != 0:
            length[a[l] - 1] += 1
for l in length:
    print(l)

### FIXED CODE ###

n, x, y = map(int, input().split())
x = min(x - 1, y - 1)
y = max(x - 1, y - 1)
length = [0] * (n - 1)
for i in range(n - 1):
    for j in range(i, n):
        l = min(abs(i - j), abs(i - x) + 1 + abs(j - y), abs(i - y) + 1 + abs(j - x))
        if l != 0:
            length[l - 1] += 1
for l in length:
    print(l)
### BUGGY CODE ###

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

msq = int(math.sqrt(M))
if N == 1:
    ans = M
else:
    for i in range(M, 0, -1):
        if M%i == 0:
            tmp = M - i*(N-1)
            if tmp > 0 and tmp%i == 0:
                ans = i
                break

print(ans)


### FIXED CODE ###

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

MAX_SQRT = int(math.sqrt(M))
prime_flag = [True] * (MAX_SQRT+1)
prime_dic = {}

prime_flag[0] = False
prime_flag[1] = False

for i in range(2, MAX_SQRT+1):
    mul = 2
    while True:
        p = i * mul
        if p > MAX_SQRT:
            break
        prime_flag[p] = False
        mul += 1

TMPM = M
for i in range(2, MAX_SQRT+1):
    if prime_flag[i]:
        while TMPM%i == 0:
            if i in prime_dic:
                prime_dic[i] += 1
            else:
                prime_dic[i] = 1
            TMPM = int(TMPM/i)

if TMPM > 1 or len(prime_dic) == 0:
    prime_dic[TMPM] = 1

max_mul = 1
def Rec(mul, p):
    global max_mul
    if M//mul < N:
        return

    if p >= len(prime_dic):
        if mul > max_mul:
            max_mul = mul
        return

    k = list(prime_dic.keys())[p]
    v = list(prime_dic.values())[p]
    for i in range(v+1):
        Rec(mul*(k**i), p+1)

Rec(1, 0)
print(max_mul)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
total=sum(a)
ans=[]
for i in range(n-1):
    x=sum(a[:i+1:])
    ans.append(abs(2*x-total))
print(min(ans))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
v=sum(a)
x=sum(a)
ans=[]
for i in range(n-1):
    x=x-a[i]
    ans.append(abs(v-2*x))
print(min(ans))
### BUGGY CODE ###

I=lambda:list(map(int,input().split()));x,y,z,k=I();s=lambda a,b:sorted(i+j for i in a for j in b)[:-k-1:-1];S=sorted;print(*s(s(S(I()),S(I())),I()))

### FIXED CODE ###

I=lambda:list(map(int,input().split()));x,y,z,k=I();s=lambda a,b:sorted(i+j for i in a for j in b)[:-k-1:-1];print(*s(s(I(),I()),I()))
### BUGGY CODE ###

N = int(input())
S = [0] + list(input())
Q = int(input())

Query = [list(input().split()) for i in range(Q)]

for i in range(Q):
    if Query[i][0] == '1':
        S[int(Query[i][1])] = Query[i][2]
    else:
        s = {S[j] for j in range(int(Query[i][1]),int(Query[i][2])+1)}
        print(len(s))

### FIXED CODE ###

import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

N = I()
S = [set([a]) for a in LS2()]


def seg_func(x,y):
    return x | y

unit = set([])

class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = N
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)
    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)


seg = SegTree(N,seg_func,unit)
seg.build(S)

Q = I()
for i in range(Q):
    a,b,c = LS()
    if a == '1':
        b = int(b)-1
        seg.set_val(b,set([c]))
    else:
        b,c = int(b)-1,int(c)-1
        print(len(seg.fold(b,c+1)))
### BUGGY CODE ###

import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    for j in itertools.combinations(x, i):
        if sum(j) > 0:
            continue
        if sum(j) == 0:
            cnt += c + 1
print(int(cnt))

### FIXED CODE ###

import sys
import numpy as np
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, a = imap()
x = np.array(iarr()) - a
MAX = 50*50+1

dp = np.zeros((n+1, 2*MAX+1)).astype(int)
dp[0][MAX] = 1
for i in range(n):
    for j in range(2*MAX):
        if j-x[i] < 0 or j-x[i] > 2*MAX:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x[i]]
print(dp[n][MAX]-1)
### BUGGY CODE ###

import numpy as np
import itertools as it
n=int(input())
x=[]
for i in range(n):
	X=list(map(int,input().split()))
	x.append(X)
x=np.array(x)
ans=0
roots=list(it.permutations(range(n)))
for root in roots:
	for i in range(1,n):
		d=np.linalg.norm(x[root[i-1]]-x[root[i]])
		ans+=d
print('{:.8f}'.format(ans/len(roots)))

### FIXED CODE ###

import numpy as np
n=int(input())
x=[]
for i in range(n):
	X=list(map(int,input().split()))
	x.append(X)
x=np.array(x)
ans=0
for i in range(n):
	for j in range(i+1,n):
		d=np.linalg.norm(x[i]-x[j]) #ベクトルの距離を計算
		ans+=d
#nc2=n*(n-1)/2
print('{:.8f}'.format(ans*2/n)) #桁数設定