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

# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    par[x]=y
    size[y]+=size[x]

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[x]<size[y]: x,y=y,x  #xの要素数が大きいように
    size[x]+=size[y]
    par[y]=x


def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1


TAKAHASHI = [0] * N

def dfs_takahashi(cur: int, past: int, G, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, G, d + 1)

def dfs_aoki(cur: int, past: int, G, d: int):

    if elens[cur] == 1 and G[cur][0] == past:
        return d - 1, cur == u

    ret = 0
    ret_te = cur == u

    for nx in G[cur]:
        if nx == past:
            continue

        depth, takahashi_exists = dfs_aoki(nx, cur, G, d + 1)
        if takahashi_exists and d <= TAKAHASHI[cur]:
            return depth, True

        ret = max(ret, depth)
        ret_te |= takahashi_exists

    return ret, ret_te

dfs_takahashi(u, -1, G, 0)
d, _ = dfs_aoki(v, -1, G, 0)
print(d)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
N, u, v = map(int, input().split())
u -= 1
v -= 1

G = [[] for _ in range(N)]
elens = [0] * N

for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
    elens[a] += 1
    elens[b] += 1
depths = [0] * N
dists = [0] * N


TAKAHASHI = [0] * N
AOKI = [0] * N

def dfs_aoki(cur: int, past: int, d: int):
    AOKI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_aoki(nx, cur, d + 1)

def dfs_takahashi(cur: int, past: int, d: int):
    TAKAHASHI[cur] = d

    for nx in G[cur]:
        if nx == past:
            continue
        dfs_takahashi(nx, cur, d + 1)

dfs_takahashi(u, -1, 0)
dfs_aoki(v, -1, 0)

ans = 0

for i in range(N):
    if TAKAHASHI[i] < AOKI[i]:
        ans = max(ans, AOKI[i] - 1)

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

k = int(input())

sum = 0

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


for a in range(1, k + 1):
    for b in range(1, k + 1):
        ab_gcd = gcd(a, b)
        for c in range(1, k + 1):
            abc_gcd = gcd(c, ab_gcd)
            sum += abc_gcd
        
print(sum)

### FIXED CODE ###

k = int(input())

sum = 0

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


for a in range(1, k + 1):
    for b in range(1, k + 1):
        ab_gcd = gcd(a, b)
        for c in range(1, k + 1):
            abc_gcd = gcd(c, ab_gcd)
            sum += abc_gcd
        
print(sum)
### BUGGY CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_word = [i[0] for i in word_buf.items() if i[1] == max(word_buf.values())]
max_word.sort()

for i in max_word:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

# from pprint import pprint
# import math
# import collections

# n = int(input())
R, G, B, N = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

max_r, max_g, max_b = N // R, N // G, N // B
ans = []

r, g, b = 0, 0, 0
for r in range(max_r + 1):
    for g in range(max_g + 1):
        if R * r + G * g > N:
            break
        x = (N - (R * r + G * g))
        if x % B == 0 and x >= 0:
            b = x // B
            a = (r, g, b)

            ans.append(a)

print(len(ans))


### FIXED CODE ###

# from pprint import pprint
# import math
# import collections

# n = int(input())
R, G, B, N = map(int, input().split(' '))
# a = list(map(int, input().split(' ')))

# max_r, max_g, max_b = N // R, N // G, N // B
ans = []

r, g, b = 0, 0, 0
cnt = 0

max_r = N // R
for r in range(max_r + 1):
    if R * r > N:
        break

    max_g = (N - R * r) // G

    for g in range(max_g + 1):
        if R * r + G * g > N:
            break
        x = (N - (R * r + G * g))
        if x % B == 0 and x >= 0:
            # b = x // B
            # a = (r, g, b)
            cnt += 1
            # ans.append(a)

# print(len(ans))
print(cnt)
### BUGGY CODE ###

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

su=[]
for i in s:
    shu=sorted(list(i))
    su.append("".join(shu))


count=0
while len(su)>1:
  j=su[0]
  del su[0]
  c=su.count(j)+1
  count+=c*(c-1)/2
  su=[i for i in su if i!=j]
  
print(int(count))

### FIXED CODE ###

import collections
N=int(input())
su=["".join(sorted(list(input()))) for _ in range(N)]

C=list(collections.Counter(su).values())

ans=0
for i in C:
  if i>1:
    ans+=i*(i-1)//2

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

import sys
import math

input= sys.stdin.readline
N, M = map(int,input().split())

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

A.sort(reverse=True)
cnt = 1
A[0]=A[0]//2

if N==1:
    while A[0]>0 and cnt<M:
        cnt+=1
        A[0]=A[0]//2
else:
    while cnt<M:
        c=min(M-cnt,int(math.log2(A[0]/A[1])+1))
        cnt+=c
        A[0]=A[0]//(2**c)
        
        b=A[0]
        A[0]=A[1]
        for i in range(2,N):
            if A[i]>b:A[i-1]=A[i]
            else:
                A[i-1]=b
                break

print(sum(A))
    
        

### FIXED CODE ###

import heapq

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

a = [-int(x) for x in input().split()]

heapq.heapify(a)

num = 0
hq = 1

while num < M and hq != 0:
    hq = -heapq.heappop(a)
    hq2 = hq // 2
    heapq.heappush(a, -hq2)
    num += 1

print(-sum(a))
### BUGGY CODE ###

def lcs_len(x, y):
    ly = len(y)
    tcsl = [0] * (ly + 1)
    for x_i in x:
        pre_tcsl = list(tcsl)
        for j in range(ly):
            if x_i == y[j]:
                tcsl[j] = pre_tcsl[j - 1] + 1
            else:
                tcsl[j] = max(pre_tcsl[j], tcsl[j - 1])
    print(tcsl[j])


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)

### FIXED CODE ###

def lcs_len(x, y):
    indices = [0]
    for y_i in y:
        t_index = 0
        for i, index in enumerate(indices, 1):
            c_index = x.find(y_i, t_index) + 1
            if c_index:
                if i < len(indices):
                    t_index = indices[i]
                    indices[i] = min(c_index, t_index)
                else:
                    indices.append(c_index)
                    break
    print(len(indices) - 1)


q = int(input())

for i in range(q):
    ax = input()
    ay = input()
    lcs_len(ax, ay)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [int(s) for s in A]

	BC = []
	for i in range(M):
		b, c = map(int, input().split(" "))
		BC.append((c, b))

	BC.sort(reverse=True)

	for i in BC:
		A.sort()
		c, b = i

		if A[0] >= c:
			continue

		tmp = bisect_left(A, c)
		if tmp <= b:
			A[:tmp] = [c] * tmp
		elif tmp > b:
			A[:b] = [c] * b


	ans = 0
	for i in A:
		ans += i
	print(ans)


if __name__ == "__main__":
	main()

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)

# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

def main():
	N, M = map(int, input().split(" "))
	#N = int(input())
	#S = input()

	A = input().split(" ")
	A = list(A)
	#A = A[:-1]
	A = [(int(s) * (-1), 1) for s in A]
	heapq.heapify(A)

	for i in range(M):
		b, c = map(int, input().split(" "))
		heapq.heappush(A, (c * (-1), b))
	
	ans = []
	for i in range(N):
		t, con = heapq.heappop(A)
		for _ in range(con):
			if len(ans) == N:
				print(sum(ans))
				sys.exit()
			ans.append(t * (-1))
	print(sum(ans))


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

N, Q = map(int, input().split())
S = input()
l=[]; r=[]
for _ in range(Q):
    l1, r1 = map(int, input().split())
    l.append(l1); r.append(r1)
import re
regex = re.compile(r"AC")
for i in range(Q):
    mo = regex.findall(S[l[i]-1:r[i]])
    print(len(mo))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
L = [0]*(N+1)
for i in range(N):
    if S[i:i+2] == "AC":
        L[i+1] = L[i] +1
    else:
        L[i+1] = L[i]
for i in range(Q):
    l,r = map(int, input().split())
    print(L[r-1]-L[l-1])
### BUGGY CODE ###

from numpy import*
from numba import*
@njit('void(i8,i8,i8[:],i8[:,:])',cache=True)
def main(n,q,c,z):
  a=zeros(q,int64)
  t=zeros(9**6,int64)
  b=zeros(9**6,int64)
  j=0
  for i in argsort(z[:,1]):
    l,r=z[i,0],z[i,1]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:
        t[x]+=1
        x+=x&-x
      while y<=n:
        t[y]-=1
        y+=y&-y
    while l:
      a[i]+=t[l]
      l-=l&-l
  for i in a:print(i)
(n,q),c,*z=[int_(t.split())for t in open(0)]
main(n,q,c,int_(z))

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()
### BUGGY CODE ###

N,M = map(int,input().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,input().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
for i in start:
    if i in goal:
        ans = 'POSSIBLE'
        break
print(ans)

### FIXED CODE ###

import sys
N,M = map(int,sys.stdin.readline().split())
start = []
goal = []
for i in range(M):
    a,b = map(int,sys.stdin.readline().split())
    if a == 1:
        start.append(b)
    if b == N:
        goal.append(a)
ans = 'IMPOSSIBLE'
seta = set(start)
setg = set(goal)
for i in seta:
    if i in setg:
        ans = 'POSSIBLE'
        break
print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
N,M,K = map(int,input().split())
follow = [[False for i in range(N)] for j in range(N)]
block = [[False for i in range(N)] for j in range(N)]
edges = [0 for i in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A][B] = True
    follow[B][A] = True
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

n,labels = connected_components(np.array(follow))

groupV = [0]*n
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    block[C][D] = True
    block[D][C] = True
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))


### FIXED CODE ###

N,M,K = map(int,input().split())
#follow = [[False for i in range(N)] for j in range(N)]
follow = [[] for _ in range(N)]
labels = [-1 for _ in range(N)]
edges = [0 for _ in range(N)]

for i in range(M):
    A,B = map(int,input().split())
    A = A-1
    B = B-1
    follow[A].append(B)
    follow[B].append(A)
    edges[A] = edges[A] + 1
    edges[B] = edges[B] + 1

c = 0
for i in range(N):
    if (labels[i] == -1):
        s = []
        s.append(i)
        labels[i] = c
        while(len(s) != 0):
            u = s.pop()
            for i in range(len(follow[u])):
                if (labels[follow[u][i]] == -1):
                    labels[follow[u][i]] = c
                    s.append(follow[u][i])
        c += 1

groupV = [0]*(c+1)
for i in range(N):
    groupV[labels[i]] = groupV[labels[i]] + 1

for i in range(K):
    C,D = map(int,input().split())
    C = C-1
    D = D-1
    if (labels[C] != labels[D]) : continue
    edges[C] = edges[C] + 1
    edges[D] = edges[D] + 1

ans = ["0"]*N

for i in range(N):
    ans[i] = str(groupV[labels[i]] - 1 - edges[i])

print(" ".join(ans))
### BUGGY CODE ###

import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

def wantp(n):

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q:
                p[i] = nown

            return nown


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

AB = []
for i in range(M):

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

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = []
c = []
rank = [1] * N
up2 = set([])

for i in range(N):

    p.append(i)
    c.append(set([i]))

for i in range(M):

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)

    if ap != bp:

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] = c[ap] | c[bp]

            up2 = up2 - set([bp])
            up2 = up2 | set([ap])

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] = c[ap] | c[bp]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

        else:

            p[ap] = bp
            c[bp] = c[ap] | c[bp]

            up2 = up2 - set([ap])
            up2 = up2 | set([bp])

            rank[bp] += 1

    now = 0

    for j in up2:

        now += nCr(len(c[j]),2)

    ans.append(nCr(N,2) - now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


### FIXED CODE ###

import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


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

AB = []
for i in range(M):

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

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])
### BUGGY CODE ###

def ccc(n):
    #c(n,2)
    result = (n * (n-1))//2
    return result

def calculate(arr):
    if len(arr) == 0:
        return 0

    if len(arr) == 1:
        return 0

    criteron = arr[0]
    res = [0]

    nextarr = []

    for i in range(1,len(arr)):
        if tellIsTheSame(criteron,arr[i]):
            res.append(i)
        else:
            nextarr.append(arr[i])

    return ccc(len(res)) + calculate(nextarr)

def tellIsTheSame(s1,s2):
    s1 = list(s1)
    s2 = list(s2)

    s1.sort()
    s2.sort()

    length = len(s1)

    for i in range(length):
        if s1[i] != s2[i]:
            return False

    return True


arr = []

N = int(input())
for i in range(N):
    arr.append(input())


result = calculate(arr)
print(result)

### FIXED CODE ###

def ccc(n):
    #c(n,2)
    result = (n * (n-1))//2
    return result



def sortString(a):
    a = list(a)
    a.sort()
    return "".join(a)


def calculate(arr):
    if len(arr) == 0:
        return 0

    dict = {}
    for i in range(len(arr)):
        s = sortString(arr[i])
        if dict.get(s) == None:
            dict.setdefault(s,1)
        else:
            dict.__setitem__(s,dict.get(s) + 1)


    sum = 0
    for v in dict.values():
        sum += ccc(v)

    return sum



arr = []

N = int(input())
for i in range(N):
    arr.append(input())


result = calculate(arr)
print(result)
### BUGGY CODE ###

def main():
    mod = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    
    for i in range(0, n-1):
        for j in range(i+1, n):
            ans = (ans + (a[i] * a[j])) % mod
    print(ans)
        
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 10**9 + 7
    n = int(input())
    a = list(map(int, input().split()))
    a_sum = sum(a)
    ans = 0
    
    for i in range(n):
        ans += a[i] * (a_sum - a[i])
    print(ans // 2 % MOD)
        
        
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

from collections import defaultdict, Counter
t =defaultdict(int)

L = {}
for i in range(N):
    a,b = map(int,input().split())
    #t[a-1][b-1] = 1
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p-1 not in L:
                L[a+p-1] = []
            L[a+p-1].append(b+q-1)

ans = [0]*10
for k in L.keys():
    ll = set(L[k])
    for v in ll:
        a,b = k,v
        if a < 1 or b < 1 or a >H-2 or b >W-2:
            continue

        c = 0
        for p in [-1,0,1]:
            for q in [-1,0,1]:
                c +=t[(a+p,b+q)]

        ans[c] += 1

ans[0] = (H-2)*(W-2) - sum(ans)
for i in range(10):
    print(ans[i])



### FIXED CODE ###

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

from collections import defaultdict
t =defaultdict(int)
L = defaultdict(int)

for i in range(N):
    a,b = map(int,input().split())
    t[(a-1,b-1)] = 1
    for p in [-1,0,1]:
        for q in [-1,0,1]:
            if a+p < 2 or b+q < 2 or a+p >H-1 or b+q >W-1:
                continue
            L[(a+p-1,b+q-1)] += 1
ans = [0]*10
for v in L.values():
    ans[v] += 1

ans[0] = (H-2)*(W-2) - sum(ans)
for i in range(10):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
    if max(a) > a[i]:
        print(max(a))
    else:
        print(sorted(a)[-2])

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
Amax = max(a)
Amax2 = sorted(a)[-2]
for i in range(n):
    if Amax > a[i]:
        print(Amax)
    else:
        print(Amax2)
### BUGGY CODE ###

from operator import itemgetter

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

d = [0] * (m+1)

ab.sort(key=itemgetter(1), reverse=True)

for a, b in ab:
    x = m - a
    while x >= 0:
        if d[x] == 0:
            d[x] = b
            break
        x -= 1

print(sum(d))

### FIXED CODE ###

from heapq import heappop, heappush

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

h = []

ans = 0

ab.sort()
i = 0
for d in range(1, m+1):
    while i < n:
        if ab[i][0] <= d:
            heappush(h, - ab[i][1])
            i += 1
        else:
            break
    if len(h) > 0:
        ans -= heappop(h)

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

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  dp.update(((i,pk),s) for i,s in enumerate(map(sum, zip(x_sum,y_sum))))

  for i in range(pk):
    x_sum[i] += dp[i,pk]
  x_sum.append(0)
  y_sum.append((2*s))
  s *= 3

  removes = [(i,j) for i,j in dp.keys()
            if any(x != (l<=i)+(l<=j)+1 for l,x in Q[k])]

  for i,j in removes:
    c = dp[i,j]
    del dp[i,j]
    x_sum[i] -= c
    y_sum[j] -= c
    s -= c

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)

### FIXED CODE ###

from collections import defaultdict

MOD = 1000000007
iist = lambda: map(int,input().split())

N,M = iist()
Q = defaultdict(list)
for i in range(M):
  l,r,x = iist()
  Q[r].append((l,x))

if any(x != 1 for l,x in Q[1]):
  print(0)
  exit(0)

dp = defaultdict(int)
dp[0,0] = 3

x_sum = [3]
y_sum = [3]
s = 3

for pk in range(1,N):
  k = pk+1

  for i,(a,b) in enumerate(zip(x_sum,y_sum)):
    c = (a+b)%MOD
    dp[i,pk] = c
    x_sum[i] += c

  x_sum.append(0)
  y_sum.append((2*s)%MOD)
  s *= 3
  subQ = Q[k]

  for i,j in list(dp.keys()):
    for l,x in subQ:
      if x != (l<=i)+(l<=j)+1:
        c = dp[i,j]
        x_sum[i] -= c
        y_sum[j] -= c
        s -= c
        del dp[i,j]
        break

  for i in range(pk):
    x_sum[i] %= MOD
    y_sum[i] %= MOD
  s %= MOD

print(s)