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

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    c = list(map(int, input().split()))
    c.sort()
    res = 0
    b = int(pow(2, n, mod))
    for i in range(n):
        l = int(pow(2, i, mod))
        r = int(pow(2, n-i-1, mod) + (n-i-1)*pow(2, n-i-2))
        res += b*c[i]*l*r % mod
    print(res%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    n = int(input())
    c = list(map(int, input().split()))
    c.sort()
    res = 0
    b = pow(2, n, mod)
    for i in range(n):
        l = pow(2, i, mod)
        if n-i-2 >= 0:
            r = pow(2, n-i-1, mod) + (n-i-1)*pow(2, n-i-2, mod)
        else:
            r = pow(2, n-i-1, mod)
        res += b*c[i]*l*r % mod
        res %= mod
    print(res)

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

n, q = map(int, input().split())
s = input()
cum_sum = [0] * (n+1)

for i in range(n+1):
    cum_sum[i] = s[:i].count('AC')

for _ in range(q):
    l, r = map(int, input().split())
    print(cum_sum[r]-cum_sum[l])


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
cum_sum = [0] * (n+1)

for i in range(n):
    if s[:i+1][-2:] == 'AC':
        cum_sum[i+1] += 1
    cum_sum[i+1] += cum_sum[i]

for _ in range(q):
    l, r = map(int, input().split())
    print(cum_sum[r]-cum_sum[l])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    from collections import deque

    # input
    n=int(input())
    V=[(i,j) for i,j in product(range(n),repeat=2) if i<j]
    E={v:[] for v in V}
    indeg={v:0 for v in V}
    for i in range(n):
        a=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            p0,q0=min(i,a[j-1]),max(i,a[j-1])
            p1,q1=min(i,a[j]),max(i,a[j])
            E[(p0,q0)].append((p1,q1))
            indeg[(p1,q1)]+=1

    # topological sort
    Q=deque(k for k,v in indeg.items() if v==0)
    res=[]
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in E[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    # judge whether DAG or not
    if len(res)<n*(n-1)//2:
        print(-1)
        return

    # calculate diameter
    LP={v:1 for v in V}
    for v0 in res:
        for v1 in E[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = np.array(list(map(int,input().split())))

cost = np.full(N, 0)
for i in range(1, N):
    gaps = np.abs(h[max(0, i-K):i] - h[i]) + cost[max(0, i-K):i]
    cost[i] = np.min(gaps)
    
print(int(cost[N-1]))

### FIXED CODE ###

import numpy as np
N, K = map(int, input().split())
hights = np.array(list(map(int,input().split())))
steps=np.array([0]*N)
steps[0]=0

for i in range(1, N):
    gaps = hights[max(0, i-K):i] - hights[i]
    gaps = np.abs(gaps)
    gaps += steps[max(0, i-K):i]
    steps[i] = np.min(gaps)
    
print(int(steps[N-1]))
### BUGGY CODE ###

s = input()
n = int(input())
li = [input().split() for i in range(n)]
 
for x in li:
    if x[0] == "1":
        s = s[::-1]
    else:
        if x[1] == "1":
            s = x[2] + s
        else:
            s = s + x[2]
 
print(s)

### FIXED CODE ###

ans = input()
q = int(input())
top = 0
first = str()
last = str()

for i in range(q):
    li =input().split()
    if li[0] =="1":
        top = (top+1)%2
    else:
        if li[1] == "1":
            if top ==0:
                first += li[2]
            else:
                last += li[2]
        else:
            if top ==1:
                first += li[2]
            else:
                last += li[2]

if top == 0:
    ans = first[::-1] + ans + last
else:
    ans = last[::-1] + ans[::-1] + first

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

import numpy as np
import sys


def calc(a, H, W):
    # 横方向
    for j in range(H):
        prev = 0
        start = 0
        for i in range(W + 1):
            if a[j, i] > 0:
                if prev == 0:
                    start = i
                    prev = 1
            else:
                if prev == 1:
                    num = i - start
                    a[j, start:i] = num
                    prev = 0
    # 縦方向
    for i in range(W):
        prev = 0
        start = 0
        for j in range(H + 1):
            if a[j, i] > 0:
                if prev == 0:
                    start = j
                    prev = 1
            else:
                if prev == 1:
                    num = j - start - 1
                    a[start:j, i] += num
                    prev = 0


def get_data(stream):
    buf = b''
    b = stream.buffer.read(1)
    while b != b'\n':
        buf += b
        b = stream.buffer.read(1)
    H, W = map(int, buf.split())
    c = stream.buffer.read(H * (W + 1))
    arr = np.array(c.split())
    arr = np.frombuffer(arr, dtype='S1').reshape((H, W))
    return H, W, arr


def main():
    H, W, arr = get_data(sys.stdin)
    a = np.zeros((H + 1, W + 1), dtype='i8')
    a[:-1, :-1] = arr == b'.'

    calc(a, H, W)
    print(a.max())


if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
import sys


def get_data(stream):
    buf = b''
    b = stream.buffer.read(1)
    while b != b'\n':
        buf += b
        b = stream.buffer.read(1)
    H, W = map(int, buf.split())
    c = stream.buffer.read(H * (W + 1))
    arr = np.array(c.split())
    arr = np.frombuffer(arr, dtype='S1').reshape((H, W))
    return H, W, arr


def main():
    H, W, arr = get_data(sys.stdin)
    a = arr == b'.'
    L = np.empty((H, W), dtype='i8')
    R = np.empty((H, W), dtype='i8')
    T = np.empty((H, W), dtype='i8')
    B = np.empty((H, W), dtype='i8')
    T[0] = a[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * a[i]
    B[-1] = a[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * a[i]
    L[:, 0] = a[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * a[:, i]
    R[:, -1] = a[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * a[:, i]

    print((T + B + L + R - 3).max())


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

import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    for n in range(1,N+1):
        ans = 0
        for x in range(1,int((n//3)**0.5)+1):
            for y in range(1,int((n//3)**0.5)+1):
                pre = x**2 + y**2 + x*y
                uu = n-pre
                if uu<0:
                    break
                for z in range(1,int(uu**0.5)+1):
                    if z*(z+x+y)==uu:
                        if len(set([x,y,z])) == 1:
                            ans = 1
                            break
                        elif len(set([x,y,z])) == 2:
                            ans = 3
                            break
                        else:
                            ans = 6
                            break
            else:
                continue
            break
        print(ans)



if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zer
    ans = [0]*N
    for x in range(1,int(N**0.5)+1):
        for y in range(1,int(N**0.5)+1):
            for z in range(1,int(N**0.5)+1):
                a = x**2 + y**2 + z**2 +x*y + y*z + z*x
                if a > N:
                    break
                ans[a-1] += 1

    for i in range(N):
        print(ans[i])



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

def modpow(x, n, m):
    res = 1
    while n > 0:
        if n % 2 == 1:
            res = (res * x) % m
        x = (x * x) % m
        n >>= 1
    return res

def combination(n, r, m):
    res = 1
    r = min(r, n - r)

    for i in range(1, r + 1):
        res = res * (n - r + i) % m
        res = res * modpow(i, m - 2, m) % m
    return res

mod = 10**9 + 7
n, a, b = map(int, input().split())
total = modpow(2, n, mod) - 1

total = (total - combination(n, a, mod) - combination(n, b, mod)) % mod

print(total)

### FIXED CODE ###

def combination(n, r, m):
    res = 1
    r = min(r, n - r)

    for i in range(r):
        res = res * (n - i) % m
        res = res * pow(i + 1, m - 2, m) % m
    return res

mod = 10**9 + 7
n, a, b = map(int, input().split())
total = pow(2, n, mod) - 1

total -= (combination(n, a, mod) + combination(n, b, mod)) % mod

print(total % mod)
### BUGGY CODE ###

from itertools import combinations
n = int(input())
s = input()
num_id = [x for x in range(len(s))]
A = list(combinations(num_id, 3))
B = [s[x[0]] + s[x[1]] + s[x[2]] for x in A]
print(len(set(B)))

### FIXED CODE ###

n = int(input())
s = input()
lst = [0] * 1000
for i in range(1000):
    if len(str(i)) == 1:
        tmp = '00' + str(i)
        lst[i] = tmp
    elif len(str(i)) == 2:
        tmp = '0' + str(i)
        lst[i] = tmp
    else:
        lst[i] = str(i)

cnt = 0
for v in lst:
    id_1 = s.find(v[0])
    if id_1 == -1:
        continue
    id_2 = s.find(v[1], id_1 + 1)
    if id_2 == -1:
        continue
    id_3 = s.find(v[2], id_2 + 1)
    if id_3 == -1:
        continue
    cnt += 1

print(cnt)
### BUGGY CODE ###

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

for a in range(1, n+1):
  if n % a == 0:
    if len(str(a)) <= len(str(int(n/a))):
      lis.append(max(a, int(n/a)))
    else:
      break

print(len(str(min(lis))))

### FIXED CODE ###

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

for a in range(1, int(n**0.5)+1):
  if n % a == 0:
    lis.append(max(a, int(n/a)))

print(len(str(min(lis))))
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    ans = 1
    for i in a:
        if i == 0:
            ans = 0
            
        ans *= i
        if ans > 10**18:
            ans = -1
            

    return ans

if __name__ == '__main__':
    print(main())


### FIXED CODE ###

n = int(input())
a = [int(_) for _ in input().split()]
a.sort()
ans = 1
for i in a:
    if i == 0:
        ans = 0
        break
    ans *= i
    if ans > 10**18:
        ans = -1
        break

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

def main():
    n, p = map(int, input().split())
    s = input()

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    u = [int(s[i:]) for i in range(n)]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()


### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    # u = [int(s[i:]) for i in range(n)]
    remainders = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += pow(10, i, p) * int(char)
        remainders.append(t % p)
    remainders = remainders[::-1]
    remainders.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()
### BUGGY CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    maxi = 0
    for i in range(2 ** N):
        binary = list(map(int, format(i, 'b').zfill(N)))
        ans = 0
        for j, k in enumerate(binary):
            if k == 1:
                ans += V[j] - C[j]
        if ans > maxi:
            maxi = ans

    print(maxi)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    K = [V[i] - C[i] for i in range(N)]
    ans = 0
    for k in K:
        if k > 0:
            ans += k
    print(ans)


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

N, M = map(int, input().split())
X, Y = [],[]
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        X.append(B)
    elif B == N:
        Y.append(A)

for i in X:
    for j in Y:
        if i == j:
            print("POSSIBLE")
            exit(0)
print("IMPOSSIBLE")

### FIXED CODE ###

N, M = map(int, input().split())
cnt = [0]*N
for i in range(M):
    A, B = map(int, input().split())
    if A == 1:
        cnt[B] += 1
    elif B == N:
        cnt[A] += 1

if 2 in cnt:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)

def f(a,c,b,d):
    if a >= A and b >=B :
        return a,b
    return f(a+c,c,b+d,d)

n = int(input())
a = [list(map(int,input().split()))for _ in range(n)]
A,B = a[0][0],a[0][1]
for i in range(1,n):
    A,B = f(a[i][0],a[i][0],a[i][1],a[i][1])
print(A+B)

### FIXED CODE ###

n = int(input())
a = [list(map(int,input().split()))for _ in range(n)]
A,B = a[0][0],a[0][1]
for i in range(1,n):
    C = max([1,-(-A//a[i][0]),-(-B//a[i][1])])
    A = a[i][0]*C
    B = a[i][1]*C
print(A+B)
### BUGGY CODE ###

# bin/env/pypy3
import sys
import collections
import heapq
import math
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(max(n - r,0)) * math.factorial(r))
for e in a:
    c[e] -= 1
    b = [combinations_count(v,2) for v in c.values() if v > 1]
    print(sum(b))
    c[e] += 1

### FIXED CODE ###

# bin/env/pypy3
import sys
import collections
n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
c = collections.Counter(a)
#print(n,a,c)
memo_e = {}
s = sum(v*(v-1)//2 for v in c.values() if v > 1)
for e in a:
    if not e in memo_e:
        #c[e] -= 1
        if 1 < c[e]:
            memo_e[e] = s - (c[e]*(c[e]-1)//2 - (c[e]-1)*(c[e]-2)//2)
        else:
            memo_e[e] = s
    print(memo_e[e])
### BUGGY CODE ###

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

def ev(n):
    return n * (n + 1) / (2 * n)

ans = 0
for i in range(n - k + 1):
    tmp = 0
    for j in range(i, i + k):
        tmp += ev(p[j])
    if ans <= tmp:
        ans = tmp
    #print(ans, i)
print(ans)


### FIXED CODE ###

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

def ev(n):
    return n * (n + 1) / (2 * n)

q = [0]
for i in range(n):
    q.append(ev(p[i]))
    q[i + 1] = q[i] + ev(p[i])
#print(q)

tmp = 0
for j in range(n - k + 1):
    if tmp <= q[j + k] - q[j]:
        tmp = q[j + k] - q[j]
print(tmp)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
Is = []
p = 0
while True:
  i = S.find("AC", p)
  if i < 0:
    break
  Is.append(i)
  p = i+2
#print(Is)
for i in range(Q):
  l, r = map(int, input().split())
  l, r = l-1, r-1
  c = 0
  for i in Is:
    if i >= l and i+1 <= r:
      c += 1
  print(c)


### FIXED CODE ###

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

import queue


def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = queue.Queue()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.put_nowait(s)
    
    n_days = 0
    n_states_left = max_state
    while today_states.qsize() > 0:
        n_days += 1
        n_today_states = today_states.qsize()
        if n_today_states == 0:
            break
        for _ in range(n_today_states):
            s = today_states.get_nowait()
            n_states_left -= 1
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    today_states.put_nowait(ns)
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


if __name__ == "__main__":
    main()


### FIXED CODE ###

def make_state(N):
    state = [[-1 for j in range(N+1)] for i in range(N+1)]
    min_state = 0
    s = min_state
    for i in range(1, N+1):
        for j in range(1, i):
            state[i][j] = s
            state[j][i] = s
            s += 1
    return state


def solve(N, A):
    state = make_state(N)
    max_state = N * (N-1) // 2
    n_prev_states = [0 for i in range(max_state)]
    next_states = [set() for i in range(max_state)]
    for i in range(1, N+1):
        for k in range(N-2):
            ps = state[i][A[i][k]]
            ns = state[i][A[i][k+1]]
            n_prev_states[ns] += 1
            next_states[ps].add(ns)
    
    today_states = set()
    for s in range(max_state):
        if n_prev_states[s] == 0:
            today_states.add(s)
    
    n_days = 0
    n_states_left = max_state
    while len(today_states) > 0:
        n_days += 1
        if len(today_states) == 0:
            break
        n_states_left -= len(today_states)
        nextday_states = set()
        for s in today_states:
            for ns in next_states[s]:
                n_prev_states[ns] -= 1
                if n_prev_states[ns] == 0:
                    nextday_states.add(ns)
        today_states = nextday_states
    return n_days if n_states_left == 0 else -1


def main():
    N = int(input())
    A = list()
    A.append([])
    for i in range(N):
        a = list(map(int, input().strip().split()))
        A.append(a)
    print(solve(N, A))


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

h, w, n = [int(item) for item in input().split()]
ab = [[int(item) for item in input().split()] for _ in range(n)]
poe = []
 
for a, b in ab:
    for i in range(3):
        for j in range(3):
            ah = a+i-1
            bw = b+j-1
            if ah > 1 and ah <= h-1 and bw > 1 and bw <= w-1:
                poe.append([ah, bw])
poe.sort()
 
ans = [0] * 10 
if len(poe) > 0:
    count = 1
    for i in range(1,len(poe)):
        if poe[i] == poe[i-1]:
            count += 1
        else:
            ans[count] += 1
            count = 1
    ans[count] += 1

print((w-2)*(h-2) - sum(ans))
for item in ans[1:]:
    print(item)

### FIXED CODE ###

#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

h, w, n = [int(item) for item in input().split()]
blk_cnt = defaultdict(int) 

for i in range(n):
    a, b = [int(item) - 1 for item in input().split()]
    for j in range(-1, 2):
        for k in range(-1, 2):
            blk_cnt[(a + j, b + k)] += 1
ans = [0] * 10 
for key in blk_cnt.keys():
    if key[0] < 1 or key[1] < 1 or key[0] >= h-1 or key[1] >= w-1:
        continue
    ans[blk_cnt[key]] += 1
total = (w - 2) * (h - 2)
ans[0] = total - sum(ans)
for item in ans:
    print(item)