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

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix
import collections
N,M,K = map(int,input().split())
G = [[0 for i in range(N)] for j in range(N)]
ans=[0 for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1][b-1]=1;G[b-1][a-1]=1
  ans[a-1]-=1;ans[b-1]-=1
  
a = np.array(G)
n, labels = connected_components(a)
c = collections.Counter(labels)

for i in range(N):
  ans[i]+=c[labels[i]]-1
  
for i in range(K):
  c,d=map(int,input().split())
  c-=1;d-=1
  if labels[c]==labels[d]:
    ans[c]-=1;ans[d]-=1
for i in range(N):
  print(ans[i],end=" ")

### FIXED CODE ###

N,M,K = map(int,input().split())
ans=[0 for i in range(N)]
  
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
uf = UnionFind(N)
for i in range(M):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
  ans[a-1]-=1;ans[b-1]-=1
    
for i in range(K):
  c,d=map(int,input().split())
  if uf.same(c-1,d-1):
    ans[c-1]-=1;ans[d-1]-=1
    
for i in range(N):
  ans[i]+=uf.size(i)-1
  print(ans[i],end=" ")
### BUGGY CODE ###

h,w,m = map(int,input().split())
hli = [0]*h
wli = [0]*w
li = []
for i in range(m):
    a,b = map(int,input().split())
    li.append([a,b])
    hli[a-1] += 1
    wli[b-1] += 1
a = max(hli)
b = max(wli)
hli2 = []
wli2 = []
for i in range(h):
    if hli[i] == a:
        hli2.append(i+1)
for i in range(w):
    if wli[i] == b:
        wli2.append(i+1)
for i in hli2:
    for j in wli2:
        if [i,j] not in li:
            print(a + b)
            exit()
print(a + b - 1)

### FIXED CODE ###

h,w,m = map(int,input().split())
hli = [0]*h
wli = [0]*w
li = []
liset = set()
for i in range(m):
    a,b = map(int,input().split())
    li.append([a,b])
    liset.add((a,b))
    hli[a-1] += 1
    wli[b-1] += 1
a = max(hli)
b = max(wli)
hli2 = []
wli2 = []
for i in range(h):
    if hli[i] == a:
        hli2.append(i+1)
for i in range(w):
    if wli[i] == b:
        wli2.append(i+1)
for i in hli2:
    for j in wli2:
        if (i,j) not in liset:
            print(a + b)
            exit()
print(a + b - 1)
### BUGGY CODE ###

N = int(input())
*a,= map(int, input().split())

count,res={},{}

for i in range(N):
  count[a[i]]=0
  res[a[i]]=0
  
for i in range(N):
  count[a[i]]+=1

def ncn(n):
  return n*(n-1)//2

def without(a,k):
  cc = 0
  for key in count.keys():
    kc = count[key]
    if key==a[k]:
       kc-=1
    if kc>1:
       cc+=ncn(kc)
  res[a[k]]=cc      
  return cc

def result(n):
  if res[n]>0:
    return res[n]
  return 0

for k in range(N):
  if result(a[k])>0:
    print(result(a[k]))
  else:
    print(without(a,k))

### FIXED CODE ###

N = int(input())
*a,= map(int, input().split())
count,result={},{}

for i in range(N):
  count[a[i]]=0
  result[a[i]]=0
  
def ncn(n):
  return n*(n-1)//2

for i in range(N):
  count[a[i]]+=1

total=0
for key in count.keys():
  kc = count[key]
  result[key]=ncn(kc)
  total += result[key]
  
def without(k):
  return total-count[a[k]] + 1

for k in range(N):
  print(without(k))
### BUGGY CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i in range(min(N,K)):
    dp[i] = abs(h[i]-h[0])

for i in range(K,N):
    dp[i] = dp[i-1] + abs(h[i]-h[i-1])
    for j in range(2,K+1):
        dp[i] = min(dp[i-j] + abs(h[i]-h[i-j]),dp[i])

answer = dp[-1]
print(answer)

### FIXED CODE ###

N,K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * N
for i in range(min(N,K)):
    dp[i] = abs(h[i]-h[0])

for i in range(K,N):
    dp[i] = dp[i-1] + abs(h[i]-h[i-1])
    for j in range(2,K+1):
        dp[i] = min(dp[i-j] + abs(h[i]-h[i-j]),dp[i])

answer = dp[-1]
print(answer)
### BUGGY CODE ###

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

import math
# 最初にpopcount用のリストを作成する，そもそも2**(10**5)だから圧倒的に範囲が足らなかった
L = [0 for i in range(int(math.log(N,2))+10)]
for i in range(int(math.log(N,2))+10):
    bi = list(str(bin(i)))
    bi = bi[1:]
    L[i] = bi.count('1')

# i番目のビットを反転させて,
dic={}
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    X[i] = str(b ^ 1)
    num = int(''.join(X),2) # できなきゃjoinで
    count = 0
    while num > 0:
        bi = list(str(bin(num)))
        bi = bi[2:]
        st = ''.join(bi)
        if st in dic:
            bic = dic[st]
        else:
            bic = bi.count('1')
            dic[st] = bic
        num = num % bic
        count += 1
    X[i] = str(b)
    print(count)


### FIXED CODE ###

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)
aa = x00 % (bn00+1)
if bn00-1==0:
    bb = 0
else:
    bb = x00 % (bn00-1)
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
        x0 = aa
    else:
        bn0 = bn00 - 1
        x0 = bb
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)
### BUGGY CODE ###

n = int(input())
a, b = [0]*n,[0]*n
count = 0
for i in range(n):
    a[i],b[i] = map(int,input().split())

while(n > 0):
    if(a[n-1]%b[n-1] == 0):
        n -= 1
        continue
    for j in range(0,n):
        a[j] += 1
    count += 1

print(count)

### FIXED CODE ###

n = int(input())
a, b = [0]*n,[0]*n
count = 0
for i in range(n):
    a[i],b[i] = map(int,input().split())

while(n > 0):
    n -= 1
    count += (b[n] if (a[n]+count)%b[n]!=0 else 0)-(a[n]+count)%b[n]

print(count)
### BUGGY CODE ###

import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    # 入力パターン．
    # 先に要素数Nが与えられて，その数読み込むパターン
    ### N
    ### x_1, y_1
    ### ...
    ### x_N, y_N
    N, M, Q = map(int, input().split())
    data = np.array([list(map(int, input().split())) for _ in range(Q)])
    #print(data)
    A = data[:, 0]
    B = data[:, 1]
    C = data[:, 2]
    D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = list(combinations_with_replacement(range(1, M+1), N))
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        for i in range(Q):
            t = a[B[i]-1]
            t = a[A[i]-1]
            t =C[i]
            if a[B[i]-1] - a[A[i]-1] == C[i]:
                s += D[i]
        if s > ans:
            ans = s
    print(ans)





### FIXED CODE ###

import numpy as np
import itertools
from itertools import combinations_with_replacement
if __name__ == "__main__":
    N, M, Q = map(int, input().split())
    #data = np.array([list(map(int, input().split())) for _ in range(Q)])
    data = [list(map(int, input().split())) for _ in range(Q)]
    #print(data)
    # A = data[:, 0]
    # B = data[:, 1]
    # C = data[:, 2]
    # D = data[:, 3]
    #print("B {}".format(len(B.shape)))

    # 1, 2, ..., M から重複を許してN個取り出す（ソート済み）
    arr = combinations_with_replacement(range(1, M+1), N)
    ans = 0
    for a in arr:
        #print(a)
        s = 0
        # for i in range(Q):
        #     if a[data[i, 1]-1] - a[data[i, 0]-1] == data[i, 2]:
        #         s += data[i, 3]
        for d in data:
            if a[d[1]-1] - a[d[0]-1] == d[2]:
                s += d[3] 

        if s > ans:
            ans = s
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
from collections import Counter
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    l = list(input().rstrip().split())

    c = Counter(l)
    for item in l:
        ans = 0
        for key in c:
            tmp = c[key]
            if key == item:
                tmp -= 1
            ans += tmp * (tmp - 1) // 2
        print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python
from collections import Counter
import sys

input = sys.stdin.readline

def main():
    n = int(input().rstrip())
    l = list(input().rstrip().split())

    c = Counter(l)
    total = 0
    for key in c:
        total += c[key] * (c[key] -1) // 2
    for item in l:
        print(total - (c[item] -1))
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M=map(int,input().split())
flag = False
v=[]
x=[]
y=[]
for i in range(M):
    a,b=map(int,input().split())
    v.append((a,b))
    if a==1:
        x.append(b)
    if b==N:
        y.append(a)
for i in x:
    for j in y:
        if i==j:
            flag=True
            break
    if flag:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M=map(int,input().split())
x=[0]*(N+1)
y=[0]*(N+1)
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        x[b]=1
    if b==N:
        y[a]=1
for i in range(N+1):
    if x[i]==1 and y[i]==1:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

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

N = int(input())
A = list(map(int, input().split()))
# print(N)
# print(A)
A.sort(reverse=True)
ans = 0
N = N - 2
ans += A[0]
A.pop(0)
while N > 0:
    if N > 1:
        ans += 2 * A[0]
        N -= 2
        A.pop(0)
        continue
    if N == 1:
        ans += A[0]
        break
print(ans)


### FIXED CODE ###

import heapq

N = int(input())
A = list(map(int, input().split()))
A = list(map(lambda x: x * (-1), A))

heapq.heapify(A)

ans = 0
N -= 2
ans += heapq.heappop(A) * (-1)

if N == 0:
    print(ans)
    exit()
elif N == 1:
    ans += A[0]
    print(ans)
    exit()
elif N >= 2:
    q = N // 2
    r = N % 2
    for i in range(1, q + 1):
        ans += 2 * heapq.heappop(A) * (-1)
    if r == 1:
        ans += heapq.heappop(A) * (-1)
    print(ans)
### BUGGY CODE ###

n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import Counter
from math import sqrt, ceil
def factors(x):
    c = Counter()
    while x % 2 == 0:
        c[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            c[i] += 1
            x //= i
    if x > 1:
        c[x] += 1
    return c

factors_of_aa = list(map(factors, aa))

lcm = Counter()
for factors_of_a in factors_of_aa:
    lcm |= factors_of_a

ans = 0
for factors_of_a in factors_of_aa:
    factors_to_add = lcm - factors_of_a
    to_add = 1
    for factor, cnt in factors_to_add.items():
        to_add *= pow(factor, cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

print(ans)

### FIXED CODE ###

n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import defaultdict
from math import sqrt, ceil
def factors(x):
    d = defaultdict(int)
    while x % 2 == 0:
        d[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            d[i] += 1
            x //= i
    if x > 1:
        d[x] += 1
    return d

factors_of_aa = list(map(factors, aa))

factors_of_lcm = defaultdict(int)
for factors_of_a in factors_of_aa:
    for k in factors_of_a:
        factors_of_lcm[k] = max(factors_of_lcm[k], factors_of_a[k])
lcm = 1
for factor, cnt in factors_of_lcm.items():
    lcm *= pow(factor, cnt, MOD)

ans = 0
for factors_of_a in factors_of_aa:
    to_add = lcm
    for factor, cnt in factors_of_a.items():
        to_add *= pow(factor, -cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

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

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

ans = 0
for i in range(0, N-2):
    a = L[i]
    for j in range(i+1, N-1):
        b = L[j]
        for k in range(j+1, N):
            c = L[k]
            if (a < b + c) and (b < c + a) and (c < a + b):
                ans += 1
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()

'''
リストをソートし、a, b <= cとなるようにa, bを取り出せば、
a < b + c, b < c + a という条件は満たすので、
a, bを取り出したとき、c < a + b を満たすcを二分探索で探す
'''

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l, l[i]+l[j]) - j - 1
print(ans)
### BUGGY CODE ###

class DFS:
    def __init__(self, N):
        self.N = N
        self.visited = []
        self.depth = [0 for i in range(N)]
        self.edge = [[] for i in range(N)]
        self.graph = [[False for i in range(N)] for j in range(N)]

    def dfs2(self, v, p, d):
        self.depth[v] = d
        for e in self.edge[v]:
            if (e[0] == p):
                continue
            self.dfs2(e[0], v, d+e[1])

N = int(input())
dfs = DFS(N)
for i in range(N-1):
    a,b,c = map(int, input().split())
    dfs.edge[a-1].append((b-1,c))
    dfs.edge[b-1].append((a-1,c))

Q,K = map(int,input().split())
dfs.dfs2(K-1,-1,0)
for _ in range(Q):
    x,y = map(int, input().split())
    print(dfs.depth[x-1]+dfs.depth[y-1])


### FIXED CODE ###

n = int(input())
 
graph = [[] for x in range(n)]
 
for i in range(n - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, c))
    graph[b].append((a, c))
 
q, k = map(int, input().split())
k -= 1
 
costs = [0 for x in range(n)]
que = []
que.append((k, 0))
while que:
    now, cost = que.pop()
    costs[now] = cost
    for node in graph[now]:
        if graph[node[0]] is not None:
            que.append((node[0], cost + node[1]))
    graph[now] = None
 
result = ""
for i in range(q):
    x, y = map(int, input().split())
    result += str(costs[x - 1] + costs[y - 1])
    result += "\n"
print(result)
### BUGGY CODE ###

#解説参照
n,m=map(int, input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi);e[bi].append(ai)

from collections import deque

pth=deque([1,e[1][0]])
used=[0]*(n+1)
used[1]=1;used[e[1][0]]=1

for _ in range((n+m)*2):
    r=pth[-1]
    for v in e[r]:
        if not used[v]:
            pth.append(v)
            used[v]=1
            break
    l=pth[0]
    for v in e[l]:
        if not used[v]:
            pth.appendleft(v)
            used[v]=1
            break
print(len(pth))
print(*pth)



### FIXED CODE ###

n,m=map(int, input().split())
e=[[] for _ in range(n+1)]
for _ in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi);e[bi].append(ai)

from collections import deque

pth=deque([1,e[1][0]])
used=[0]*(n+1)
used[1]=1;used[e[1][0]]=1

for _ in range(n*2):
    r=pth[-1]
    for v in e[r]:
        if not used[v]:
            pth.append(v)
            used[v]=1
            break
    l=pth[0]
    for v in e[l]:
        if not used[v]:
            pth.appendleft(v)
            used[v]=1
            break
print(len(pth))
print(*pth)
### BUGGY CODE ###

N = int(input())
lst_a = list(map(int, input().split()))
ans = float("INF")


for i in range(N - 1):
    x = sum(lst_a[:i+1])
    y = sum(lst_a[i+1:])
    ans = min(ans, abs(x - y))


print(ans)

### FIXED CODE ###

N = int(input())
lst_a = list(map(int, input().split()))
total = sum(lst_a)
x = 0
ans = float("INF")


for i in range(N - 1):
    x += lst_a[i]
    y = total - x
    ans = min(ans, abs(x - y))


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

N=input()
A=map(int, raw_input().split())
B=range(1,N+1)

C=[]
for x,y in zip(A,B):
	C.append(x-y)

K=set(C)


ans=float("inf")
for x in K:
	t=0
	for y in C:
		t+=abs(-1*x+y)
	ans=min(ans, abs(t))

print ans

### FIXED CODE ###

N=input()
A=map(int, raw_input().split())
B=range(1,N+1)
 
C=[]
for x,y in zip(A,B):
	C.append(x-y)

C.sort()

m=0
if len(C)%2==1:
	m=C[len(C)/2]
else:
	m=(C[len(C)/2-1]+C[len(C)/2])/2

	
t=0
for x in C:
	t+=abs(-1*m+x)
print t
### BUGGY CODE ###

import copy
from collections import deque

def dfs(i, k, v, x):
    if i >= k:
        return sum(x)
    x.sort()
    y = [0, 0, 0, 0]
    if len(v) > 0:
        p = v.popleft()
        xi = copy.copy(x)
        xi.append(p)
        y[0] = dfs(i + 1, k, v, xi)
        v.appendleft(p)
    if len(v) > 1:
        p = v.pop()
        xi = copy.copy(x)
        xi.append(p)
        y[1] = dfs(i + 1, k, v, xi)
        v.append(p)
    if len(x) > 0:
        p = x[0]
        xi = [x[i] for i in range(1, len(x))]
        v.appendleft(p)
        y[2] = dfs(i + 1, k, v, xi)
        _ = v.popleft()
        v.append(p)
        y[3] = dfs(i + 1, k, v, xi)
        _ = v.pop()
    return max(y)

n, k = map(int, input().split())
v = deque(list(map(int, input().split())))
x = []
ans = dfs(0, k, v, [])
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
v = list(map(int, input().split()))

ans = 0
if n == 1:
    ans = max(0, v[0])
else:
    ans = 0 if k < n else sum(v)
    for i in range(min(k + 1, n)):
        for j in range(i + 1):
            t = v[:j]
            if j != i:
                t += v[j - i:]
            t.sort()
            for p in range(k - i):
                if len(t) > 0 and t[0] < 0:
                    t.pop(0)
                else:
                    break
            if len(t) == 0:
                t = [0]
            ans = max(ans, sum(t))
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=list(input())
li=[0]*n

for i in range(n):
  if i==0:
    continue
  if s[i-1]=="A" and s[i]=="C":
    li[i]=1
    
for i in range(q):
  l,r=map(int,input().split())
  tmp=li[l:r]
  print(sum(tmp))


### FIXED CODE ###

n,q=map(int,input().split())
s=list(input())
li=[0]*n
cnt=0
ans=0

for i in range(n):
  if i==0:
    continue
  if s[i-1]=="A" and s[i]=="C":
    cnt+=1  
  li[i]=cnt
    
for i in range(q):
  l,r=map(int,input().split())
  ans=li[r-1]-li[l-1]
  print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a,b=set(map(int,input().split())),set(map(int,input().split()))
c=1;N=M=0
for k in range(m*n,0,-1):
  if k in a and k in b:
    N+=1;M+=1
  elif k in a:
    c*=M;N+=1
  elif k in b:
    c*=N;M+=1
  else:
    c*=M*N-m*n+k
print(c%(10**9+7))

### FIXED CODE ###

import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
x=10**9+7
if len(set(a))!=len(a) or len(set(b))!=len(b):
  print(0)
else:
  a.sort()
  b.sort()
  L=[]
  for i in range(n):
    l=[]
    for j in range(m):
      l.append(0)
    L.append(l)
  if m*n in a and m*n in b:
    L[a.index(m*n)][b.index(m*n)]=m*n
    ct=1
    ctn=1
    ctm=1
    A=set(a)
    B=set(b)
    for k in range(m*n-1,0,-1):
      if k in A and k in B:
        L[bisect.bisect_left(a,k)][bisect.bisect_left(b,k)]=k
        ct*=1
        ctn+=1
        ctm+=1
      elif k in A:
          ct*=ctm
          ctn+=1
      elif k in B:
          ct*=ctn
          ctm+=1
      else:
        ct*=(ctm*ctn-m*n+k)
      if ct==0:
        break
      ct=ct%x
    print(ct)
  else:
    print(0)
### BUGGY CODE ###

import numpy as np

H, W, A, B = map(int, input().split())
ans = np.zeros([H, W], dtype=int)
ans[:B, :A] = ans[B:, A:] = 1

for a in ans:
  print(*a, sep='')

### FIXED CODE ###

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

ans = [['1' if (h<B and w<A) or (B<=h and A<=w) else '0' for w in range(W)] for h in range(H)]

for a in ans:
  print(''.join(a))
### BUGGY CODE ###

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [float("inf") for _ in range(hmaxa)]
dp[0] = 0

for i in range(hmaxa):
    ab_child = [dp[i]]
    for j in ab:
        if j[0] <= i:
            ab_child.append(dp[i-j[0]] + j[1])
        dp[i] = min(min(ab_child), dp[i])

print(min(dp[h:]))

### FIXED CODE ###

h,n = list(map(int, input().split()))
ab = []
a = []
b = []
for _ in range(n):
    t_ab = list(map(int, input().split()))
    ab.append(t_ab)
    a.append(t_ab[0])
    b.append(t_ab[1])

maxa = max(a)
hmaxa = h+maxa
dp = [0 for _ in range(hmaxa)]

for i in range(1, hmaxa):
    ab_child = [dp[i-a]+b for a,b in ab]
    dp[i] = min(ab_child)

print(min(dp[h:]))