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

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
A += [-1e10]
B += [-1e10]
C += [-1e10]

memo = [A[i] + B[0] + C[0] for i in range(X + 1)]
L = [[0 for i in range(Y + 1)] for j in range(X + 1)]

for i in range(K):
  ma = 0
  for j in range(X):
    if memo[ma] < memo[j]:
      ma = j
  print(memo[ma])
  mb = 0
  mn = 0
  for j in range(Y):
    x = B[j] + C[L[ma][j]]
    if mb < x:
      mb = x
      mn = j
  L[ma][mn] += 1
  n = 0
  for j in range(Y):
    n = max(n, B[j] + C[L[ma][j]])
  memo[ma] = A[ma] + n


### FIXED CODE ###

X, Y, Z, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse = True)
B.sort(reverse = True)
C.sort(reverse = True)
A += [-1e10]
B += [-1e10]
C += [-1e10]

memo = [A[i] + B[0] + C[0] for i in range(X + 1)]
L = [[0 for i in range(Y + 1)] for j in range(X + 1)]

for i in range(K):
  ma = 0
  for j in range(X):
    if memo[ma] < memo[j]:
      ma = j
  print(memo[ma])
  mb = 0
  mn = 0
  for j in range(Y):
    x = B[j] + C[L[ma][j]]
    if mb < x:
      mb = x
      mn = j
  L[ma][mn] += 1
  n = 0
  for j in range(Y):
    n = max(n, B[j] + C[L[ma][j]])
  memo[ma] = A[ma] + n
### BUGGY CODE ###

from collections import deque
N, K, C = map(int, input().split())
S = input()

fastest = deque([])
latest = deque([])
ans = deque([])


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.appendleft(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[i]:
        ans.append(fastest[i])

print(*ans)    

### FIXED CODE ###

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

fastest = []
latest = []


date = 1

for work_days in range(K):
    while S[date - 1] == 'x':
        date += 1
    fastest.append(date)
    date += C + 1

date = 1

for work_days in range(K):
    while S[- date] == 'x':
        date += 1
    latest.append(N - (date - 1))
    date += C + 1
    
for i in range(K):
    if fastest[i] == latest[- (i + 1)]:
        print(fastest[i])
### BUGGY CODE ###

from heapq import heappop,heappush
n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[[]for i in range(n)]
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][1]-a[i][1]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    p,q,r=a[i][0],a[i+1][0],a[i+1][2]-a[i][2]
    s[p].append([r,p,q])
    s[q].append([r,q,p])
t=[1]*n
t[0],q,r=0,[],1
e=0
for i in s[0]:
    heappush(q,i)
while q and r!=n:
    b,c,d=heappop(q)
    if t[d]==1:
        t[d]=0
        for i in s[d]:
            if t[i[2]]==1:
                heappush(q,i)
        e+=b
        r+=1
print(e)

### FIXED CODE ###

n=int(input())
a=sorted([[i]+list(map(int,input().split()))for i in range(n)],key=lambda x:x[1])
s=[]
for i in range(n-1):
    s.append((a[i+1][1]-a[i][1],a[i][0],a[i+1][0]))
a=sorted(a,key=lambda x:x[2])
for i in range(n-1):
    s.append((a[i+1][2]-a[i][2],a[i][0],a[i+1][0]))
s.sort()
t=[i for i in range(n)]
def f(x):
    if x==t[x]:
        return x
    t[x]=f(t[x])
    return f(t[x])
c=0
for i,j,h in s:
    j,h=f(j),f(h)
    if h!=j:
        t[j]=h
        c+=i
print(c)
### BUGGY CODE ###

from collections import Counter
S = list(input())
T = list(input())

for w in S:
    if w in T:
        idxs = [i for i, x in enumerate(S) if x == w]
        idxt = [i for i, x in enumerate(T) if x == w]
        for num in idxs[::-1]:
            del S[num]
        for num in idxt[::-1]:
            del T[num]

s_count = Counter(S)
del_s = ''
t_count = Counter(T)
del_t = ''

for ks, vs in list(s_count.items()):
    for kt, vt in list(t_count.items()):
        if vs == vt:
            del_s += ks
            del_t += kt
            del s_count[ks]
            del t_count[kt]
            break

if len(set(S)) == len(del_s) and len(set(T)) == len(del_t):
    print('Yes')
else:
    print('No')


### FIXED CODE ###

from collections import defaultdict
S = list(input())
T = list(input())
l = len(S)
ds = defaultdict(str)
dt = defaultdict(str)
for i in range(l):
    if ds[S[i]] == "":
        ds[S[i]] = T[i]
    elif ds[S[i]] == T[i]:
        pass
    else:
        print('No')
        exit()
    if dt[T[i]] == "":
        dt[T[i]] = S[i]
    elif dt[T[i]] == S[i]:
        pass
    else:
        print('No')
        exit()

print('Yes')
### BUGGY CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
  h1=h[i:i+k]
  a1=max(h1)-min(h1)
  a=min(a,a1)
print(a)

### FIXED CODE ###

n,k=map(int,input().split())
h=sorted([int(input()) for _ in range(n)])
a=10**9
for i in range(n-k+1):
    a1=h[i+k-1]-h[i]
    a=min(a,a1)
print(a)
### BUGGY CODE ###

import collections
h, w = [int(_) for _ in input().split()]
S = [list(input()) for _ in range(h)]
B = [[-1] * w for _ in range(h)]
B[0][0] = 0 if S[0][0] == '.' else 1
cand = collections.deque([(0, 1), (1, 0)])
while cand:
    x, y = cand.popleft()
    s = 999
    if y:
        s = B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1])
    if x:
        s = min(s, B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
    B[x][y] = s
    if x + 1 < h:
        cand += [(x + 1, y)]
    if y + 1 < w:
        cand += [(x, y + 1)]
print(B[-1][-1])


### FIXED CODE ###

import collections
h, w = [int(_) for _ in input().split()]
S = [list('.' * (w + 1))] + [['.'] + list(input()) for _ in range(h)]
B = [[99999] * (w + 1) for _ in range(h + 1)]
B[1][1] = 0 if S[1][1] == '.' else 1
cand = collections.deque([(1, 2), (2, 1)])
while cand:
    x, y = cand.popleft()
    if B[x][y] == 99999:
        B[x][y] = min(B[x][y - 1] + (S[x][y] == '#' != S[x][y - 1]),
                      B[x - 1][y] + (S[x][y] == '#' != S[x - 1][y]))
        if x < h:
            cand += [(x + 1, y)]
        if y < w:
            cand += [(x, y + 1)]
print(B[-1][-1])
### BUGGY CODE ###

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


def f():
    B = [['.'] * W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                B[i][j] = '#'
                if i > 0:
                    B[i - 1][j] = '#'
                if j > 0:
                    B[i][j - 1] = '#'
                if i < H - 1:
                    B[i + 1][j] = '#'
                if j < W - 1:
                    B[i][j + 1] = '#'
    return B


def c():
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.': return False
    return True


ans = 0
while 1:
    if c():
        break
    ans += 1
    A = f()
print(ans)


### FIXED CODE ###

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

from collections import deque

lst = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            lst.append((i, j, 0))


def chg(i, j):
    if i < 0 or j < 0 or H <= i or W <= j: return False
    if A[i][j] == '.':
        A[i][j] = '#'
        return True
    return False


ans = 0
while lst:
    h, w, v = lst.popleft()
    ans = max(v, ans)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0: continue

            if chg(h + i, w + j):
                lst.append((h + i, w + j, v + 1))
print(ans)
### BUGGY CODE ###

import numpy as np

H, W = map(int, input().split())

maze_x = [input() for _ in range(H)]
maze01 = np.array([[int(x=='.') for x in maze_x[i]] for i in range(H)])

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst1 = [i for i in maze[hh].split('#') if i != '']
        lst2 = [i for i in maze[hh].split('.') if i != '']
        ww = 0
        k1 = 0
        k2 = 0
        if maze[hh][0]=='#':
            ww += len(lst2[0])
            k2 += 1
          
        while len(lst1)>k1:
            if maze[hh][ww] == '.':
                ln = len(lst1[k1])
                cnt[hh][ww:ww+ln] = [ln]*ln
                k1 += 1
                ww += ln
            else:
                ln = len(lst2[k2])
                cnt[hh][ww:ww+ln] = [0]*ln
                k2 += 1
                ww += ln

    return cnt
u = np.zeros((H, W), dtype=np.int32)
l = np.zeros((H, W), dtype=np.int32)

u[0] = maze01[0]
l[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] = [x * y for x, y in zip(u[hh], maze01[hh])]
    l[H - hh - 1, :] = l[H - hh] + maze01[H - hh - 1]
    l[H - hh - 1] = [x * y for x, y in zip(l[H - hh -1], maze01[H - hh - 1])]

cnt = np.array(count_light(maze_x, W, H)) + u + l - 2

print(max([max(cnt[i]) for i in range(H)]))


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))
### BUGGY CODE ###

N = int(input())
a = [int(i) for i in input().split()] 
num = 0
for j in range(N):
    c = 0
    k = j 
    while k < N:
        c = c + a[k]
        if c == 0:
            num = num+1
        k = k+1
print(num)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()] 
b =[0]*(N+1)
for i in range(N):
    b[i+1]= b[i] + a[i]
b.sort()
j = 0
num = 0
v = 0
while j < N:
    if b[j+1] == b[j]:
        v = v+1
    else:
        num = num + (v*(v+1))//2
        v = 0
    j = j +1
num = num + (v*(v+1))//2
print(num)
### BUGGY CODE ###

N = int(input())
L = [int(input()) for i in range(N)]
P = list(set(L))
ans = 0
for i in range(len(P)) :
    p = L.count(P[i])
    if p % 2 != 0 :
        ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
D = {}
for i in range(N) :
    index = int(input())
    if index not in D :
        D[index] = 1
    else :
        D[index] += 1
ans = 0
for i in D :
    if D[i] % 2 != 0 :
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '#':
                q.append((i, j))
                a[i*w+j] = 0
    dd = ((0, -1), (0, 1), (1, 0), (-1, 0))
    while q:
        x, y = q.popleft()
        z = a[x*w+y] + 1
        for dx, dy in dd:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and a[nx*w+ny] > z:
                a[nx*w+ny] = z
                q.append((nx, ny))
    print max(a)
main()


### FIXED CODE ###

from collections import deque
def main():
    h, w = map(int, raw_input().split())
    s = [raw_input().strip() for _ in xrange(h)]
    q = deque()
    po = q.popleft
    pu = q.append
    a = [100000] * (h * w)
    for i, r in enumerate(s):
        for j, c in enumerate(r):
            if c == '#':
                pu((i, j))
                a[i*w+j] = 0
    dd = ((0, -1), (0, 1), (1, 0), (-1, 0))
    while q:
        x, y = po()
        z = a[x*w+y] + 1
        for dx, dy in dd:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and a[nx*w+ny] > z:
                a[nx*w+ny] = z
                pu((nx, ny))
    print z - 1
main()
### BUGGY CODE ###

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    ss = set(s)
    res = 0
    for i in ss:
        cnt = s.count(i) - 1
        res += (cnt+1)*cnt//2
    print(res)
    
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = ["".join(sorted(input())) for i in range(n)]
    
    from collections import Counter
    c = Counter(s)
    res = 0
    for i in c.values():
        if i < 2:
            continue
        else:
            res += i * (i-1) // 2
    print(res)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import fractions
from functools import reduce
N=int(input())
A=list(map(int,input().split()))
ans=0
def gcd(n):
  return reduce(fractions.gcd, n)

for i in range(N):
  li=A[:i]+A[i+1:]
  x=gcd(li)
  if x>ans:
    ans=x
print(ans)

### FIXED CODE ###

import fractions
N=int(input())
A=list(map(int,input().split()))
ans=0  #更新用
#端っこの処理用
l=[0]*(N+1)
r=[0]*(N+1)
for i in range(N):
  l[i+1]=(fractions.gcd(l[i],A[i]))
  r[N-i-1]=(fractions.gcd(r[N-i],A[N-1-i]))
for j in range(N):
  ans=max(ans,fractions.gcd(l[j],r[j+1]))
print(ans)
### BUGGY CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
for i in range(h):
    if g[i]==max(g):
        G.append(i+1)
for i in range(w):
    if r[i]==max(r):
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)


### FIXED CODE ###

h,w,m=map(int,input().split())
a=[[] for i in range(m)]
g=[0 for i in range(h)]
r=[0 for i in range(w)]

for i in range(m):
    x,y=map(int,input().split())
    a[i].append(x)
    a[i].append(y)
    g[x-1]+=1
    r[y-1]+=1
G=[]
R=[]
d=max(g)
e=max(r)
for i in range(h):
    if g[i]==d:
        G.append(i+1)
for i in range(w):
    if r[i]==e:
        R.append(i+1)
f=0
for i in range(m):
    q=0
    p=0
    x=a[i][0]
    y=a[i][1]
    k=len(G)-1
    l=0
    j=(k+l)//2
    while k-l>1:
        j=(k+l)//2
        if G[j]>=x:
            k=j
        else:
            l=j
    if G[l]==x or G[k]==x:
        p=1

    k = len(R) - 1
    l = 0
    j = (k + l) // 2
    while k - l > 1:
        j = (k + l) // 2
        if R[j] >=y:
            k = j
        else:
            l = j
    if R[l] == y or R[k] == y:
        q = 1

    if p==q==1:
        f+=1
v=1
if f!=len(G)*len(R):
    v=0
ans=max(g)+max(r)
print(ans if v==0 else ans-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
  l, r = map(int, input().split())
  strin = S[l - 1:r]
  print(strin.count("AC")) 

### FIXED CODE ###

import bisect
N, Q = map(int, input().split())
S = input()
lis = []
for i in range(len(S) - 1):
  if S[i] == "A" and S[i + 1] == "C":
    lis.append(i + 1)
for _ in range(Q):
  l, r = map(int, input().split())
  ko = bisect.bisect_left(lis, l)
  kk = bisect.bisect_left(lis, r)
  print(kk - ko)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
I = np.arange(1, N+1)
C = A - I
mincost = -1
for b in range(C.min(), C.max()+1):
    cost = np.abs(C - b).sum()
    mincost = cost if mincost < 0 else min(mincost, cost)
print(mincost)

### FIXED CODE ###

import numpy as np
def _unique1d(ar, return_index=False, return_inverse=False,
              return_counts=False):
    """
    Find the unique elements of an array, ignoring shape.
    """
    ar = np.asanyarray(ar).flatten()

    optional_indices = return_index or return_inverse
    optional_returns = optional_indices or return_counts

    if ar.size == 0:
        if not optional_returns:
            ret = ar
        else:
            ret = (ar,)
            if return_index:
                ret += (np.empty(0, np.intp),)
            if return_inverse:
                ret += (np.empty(0, np.intp),)
            if return_counts:
                ret += (np.empty(0, np.intp),)
        return ret

    if optional_indices:
        perm = ar.argsort(kind='mergesort' if return_index else 'quicksort')
        aux = ar[perm]
    else:
        ar.sort()
        aux = ar
    flag = np.concatenate(([True], aux[1:] != aux[:-1]))

    if not optional_returns:
        ret = aux[flag]
    else:
        ret = (aux[flag],)
        if return_index:
            ret += (perm[flag],)
        if return_inverse:
            iflag = np.cumsum(flag) - 1
            inv_idx = np.empty(ar.shape, dtype=np.intp)
            inv_idx[perm] = iflag
            ret += (inv_idx,)
        if return_counts:
            idx = np.concatenate(np.nonzero(flag) + ([ar.size],))
            ret += (np.diff(idx),)
    return ret
N = int(input())
A = np.array(list(map(int, input().split())), dtype= int)
I = np.arange(1, N+1)
C = A - I
mincost = -1
P, M = _unique1d(C, return_counts=True)
n = -N
for p , m in zip(P, M):
    n1 = n + 2*m
    if n*n1<=0:
        b = p
        break
    n = n1
cost = np.abs(C - b).sum()
print(cost)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
memo = [float('inf')]*n
memo[0] = 0
for i in range(0, n):
    for j in range(1, min(k + 1, n - i)):
        memo[i + j] = min(memo[i + j], memo[i] + abs(h[i + j] - h[i]))
print(memo[-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]
memo = [0]*n
for i in range(1, n):
    min_k = float('inf') 
    min_k=min([memo[j] +abs(h[i]-h[j]) for j in range(max(0, i-k), i)])
    memo[i] = min_k

print(memo[-1])
### 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):
  n=len(pt)
  d=[-1]*n
  if visited[v]==True:
    return -1,visited
  check_visited = [False]*n
  check_visited[v] = True
  S = [v]
  d[v] = 0
  while S:
    v1 = S.pop()
    for i in pt[v1]:
      if check_visited[i] == False:
        check_visited[i] = True
        visited[i] = True
        d[i] = d[v1] + 1
        S.append(i)
      else:
        print(-1)
        exit()
  return max(d),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 ###

n = int(input())
a = [int(i) for i in input().split()]
b = {}
c = set()
for i in a:
    if i not in b:
        b[i] = 1
    else:
        b[i] += 1
        c.add(i)
for i in range(n):
    b[a[i]] -= 1
    x = 0
    for j in c:
        x += (b[j] * (b[j] - 1)) // 2
    print(x)
    b[a[i]] += 1

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = {}
    c = set()
    for i in a:
        if i not in b:
            b[i] = 1
        else:
            b[i] += 1
            c.add(i)
    d = 0
    for i in c:
        d += (b[i] * (b[i] - 1)) // 2
    for i in range(n):
        e = d - ((b[a[i]] * (b[a[i]] - 1)) // 2) + (((b[a[i]] - 1) * (b[a[i]] - 2)) // 2)
        print(e)

main()
### BUGGY CODE ###

# coding = SJIS

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

for x in range(0, k + 1):
    for y in range(0, k + 1):
        for z in range(0, k + 1):
            if x + y + z == s:
                ans += 1

print(ans)

### FIXED CODE ###

# coding = SJIS

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

if s < k:
    ans = (s + 1) * (s + 2) / 2
elif s <= 2 * k:
    t = 2 * k - s
    a = (k + 1) * (k + 2) / 2
    b = t * (t + 1) / 2
    c = t * (2 * k - (t - 1)) / 2
    ans = a - b + c
elif s <= 3 * k:
    t = 3 * k - s + 1
    ans = t * (t + 1) / 2
print(int(ans))
### BUGGY CODE ###

L,R = map(int,input().split())
result = 1e9
R = min(R,L+4038)
for i in range(L,R):
    for j in range(L+1,R+1):
        result = min(result,i*j%2019)
print(result)

### FIXED CODE ###

L,R = map(int,input().split())
result = 2018
if R - L >= 2019:
    result = 0
else:
    for i in range(L,R):
        for j in range(L+1,R+1):
            result = min(result,i*j%2019)
print(result)
### BUGGY CODE ###

n,m = map(int, input().split())
dp = [float("inf")]*(2**n)
dp[0] = 0
for M in range(m):
    a,b = map(int, input().split())
    C = list(map(int, input().split()))

    state = 0
    for c in C:
        state += 2**(c-1)

    for i in range(2**n):
        if dp[i|state] != float("inf"):
            dp[i|state] = min(dp[i]+a,dp[i|state])
        else:
            dp[i|state] = dp[i]+a

if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline
    N,M = map(int,input().split())
    full = 2**N
    dp = [float("inf")]*full
    dp[0] = 0


    for m in range(M):
        a,b = map(int, input().split())
        C = list(map(int, input().split()))
        #鍵mで開く宝箱を二進法で表記
        state = 0
        for c in C:
            state += 2**(c-1)

        #状態iに対して鍵mを使い、状態i|stateにいく場合と、元から入っている場合の大小を比較
        #状態i|state即ち状態iに対して鍵mを使った後の状態
        for i in range(full):
            if dp[i] != float("inf"):
                dp[i|state] = min(dp[i]+a,dp[i|state])

    if dp[-1]==float("inf"):
    #dp[-1]はdp[full-1]でも同じ
        return -1

    return dp[-1]

print(main())