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

N, M = map(int, input().split())
base = [[int(l) for l in input().split()] for i in range(M)]
sorted_target = sorted(base) 
  
prefecture_index = sorted_target[0][0]

i=0
result = {}

for target in sorted_target:
  if prefecture_index == target[0]:
    i+=1
  else:
    prefecture_index = target[0]
    i = 1
  result[base.index(target)] = [prefecture_index, i]

for i in range(M):
  print("{:0=6}{:0=6}".format(result[i][0], result[i][1]))

### FIXED CODE ###

N, M = map(int, input().split())
base = []
for i in range(M):
  (a, b) = map(int, input().split())
  base.append((a, b, i))
sorted_target = sorted(base) 

prefecture_index = sorted_target[0][0]

i=0
result = {}

for target in sorted_target:
  if prefecture_index == target[0]:
    i+=1
  else:
    prefecture_index = target[0]
    i = 1
  result[target[2]] = [prefecture_index, i]

for i in range(M):
  print("{:0=6}{:0=6}".format(result[i][0], result[i][1]))
### BUGGY CODE ###

S = list(input())
Q = int(input())
a = 0
for i in range(Q):
  q = list(input().split())
  if q[0] == '1':
    a += 1
  else:
    if (q[1] == '1' and a % 2 == 0) or (q[1] == '2' and a % 2 == 1):
      S = [q[2]] + S
    else:
      S = S + [q[2]]
if a % 2 == 1:
  S = S[::-1]
S = ''.join(S)
print(S)

### FIXED CODE ###

S = list(input())
Q = int(input())
a = 0
A = []
B = []
for i in range(Q):
  q = list(input().split())
  q[0] = int(q[0])
  if q[0] == 1:
    if a == 0:
      a = 1
    else:
      a = 0
  else:
    q[1] = int(q[1])
    if (q[1] == 1 and a == 0) or (q[1] == 2 and a == 1):
      B.append(q[2])
    else:
      A.append(q[2])
B = B[::-1]
ans = B + S + A
if a == 1:
  ans = ans[::-1]
ans = ''.join(ans)
print(ans)
### BUGGY CODE ###

[N,K]=list(map(int, input().split()))
h=list(map(int, input().split()))
K=min(N,K)
 
dp=[[0 for i in range(K+1)] for j in range(N)]
 
for i in range (1,K):
    for j in range (0,i):
        dp[i][j]=dp[i-j-1][K]+abs(h[i-j-1]-h[i])
        dp[i][K]=min(dp[i][0:j+1])
 
for i in range (K,N):
    for j in range (0,K):
        dp[i][j]=dp[i-j-1][K]+abs(h[i-j-1]-h[i])
        dp[i][K]=min(dp[i][0:K])
 
print(dp[N-1][K])

### FIXED CODE ###

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

INF = 10e9
dp=[INF]*N
dp[0]=0

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

print(dp[N-1])
### BUGGY CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.N = N

    # xのrootを返す
    def root(self, x):
        return x if self.par[x] == x else self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if(rx != ry):
            for i in range(self.N):
                if self.par[i] == rx:
                    self.par[i] = ry

def output(uf):
    count = 0
    for i in range(uf.N):
        sub_par = uf.par[i+1:]
        count += len(sub_par) - sub_par.count(uf.par[i])

    return count



n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [output(uf)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    uf.unite(a,b)
    result.append(output(uf))
    #print(output(uf))
    #print("{},{}:{}:{}".format(a, b, uf.par, output(uf) ))

for i in result[::-1][1:]:
    print(i)

#print(uf.par)


### FIXED CODE ###

# UnionTreeクラス：グループ分けを木構造で管理する
class UnionFind():
    def __init__(self, N):
        self.par = [i for i in range(N)]
        self.size = [1] * N
        self.N = N

    # xのrootを返す
    def root(self, x):
        if self.par[x] == x:
            return x
        else: 
            self.par[x] = self.root(self.par[x])
            return self.root(self.par[x])

    # x, yが同じrootの場合true
    def same(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        return rx == ry

    # x,yのrootが違った場合、併合
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if self.size[rx] < self.size[ry]:
            self.par[rx] = ry
            self.size[ry] += self.size[rx]
        else:
            self.par[ry] = rx
            self.size[rx] += self.size[ry]

n, m = (int(i) for i in input().split())
input_arr = [[int(i) for i in input().split()] for i in range(m)] 

uf = UnionFind(n)
#input_arr = [[1,2],[3,4],[1,3],[2,3],[1,4]]

#print(output(uf))
result = [int(n*(n-1)/2)]
for i in input_arr[::-1]:
    a = i[0]-1
    b = i[1]-1
    if not uf.same(a,b):
        x = uf.size[uf.root(a)] * uf.size[uf.root(b)]
        uf.unite(a,b)
        result.append(int(result[-1]-x))
    else:
        result.append(result[-1])

for i in result[::-1][1:]:
    print(i)

#print(uf.par)
### BUGGY CODE ###

# TPBC201C - Stones
n = int(input())
s = input()
if len(set(s)) == 1:
    print(0)
else:
    ans = n
    for i in range(len(s)):
        ans = min(ans, s[:i].count("#") + s[i:].count("."))
    print(ans)

### FIXED CODE ###

# TPBC201C - Stones
n = int(input())
s = input()
ans = 0
blk = 0
for i in s:
    if i == "#":
        blk += 1
    else:
        if blk > 0:
            ans += 1
            blk -= 1
print(ans)
### BUGGY CODE ###

(k, s) = list(map(int, input().split()))
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        for z in range(k + 1):
            if s == x + y + z:
                count += 1
print(count)

### FIXED CODE ###

(k, s) = list(map(int, input().split()))
count = 0
for x in range(k + 1):
    for y in range(k + 1):
        z = s - x - y
        if z >= 0 and z <= k:
            count += 1
print(count)
### BUGGY CODE ###

import itertools
n, w = (int(x) for x in input().split())
dp = [[0 for i in range(w+1)] for j in range(n+1)] 
for i in range(n):
    a, b = (int(x) for x in input().split())
    for j in range(w+1):
        if j < a:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max([dp[i][j], dp[i][j-a]+b])
print(max(list(itertools.chain.from_iterable(dp))))

### FIXED CODE ###

N,W = map(int,input().split())
wv = []
base_w = float('inf')
for _ in range(N):
    w, v = (int(x) for x in input().split())
    wv.append([w, v])
    base_w = min(base_w, w)

dp = [[-10000000000 for i in range(100*3+1)] for j in range(N+1)]

dp[0][0] = 0

#横軸はお重さの合計、縦軸は何個選ぶか
for ws ,vs in wv:
    ws -= base_w
    for h in range(N+1, 0, -1):
        for w in range(100*3, -1, -1):
            if 0 <= w-ws:
                if dp[h-1][w-ws] != -10000000000:
                    dp[h][w] = max(dp[h][w], dp[h-1][w-ws]+vs)

ans = 0
for i in range(0,N+1):
    tmp_W = W-i*base_w
    #print(tmp_W, i)
    if 0 <= tmp_W:
        #print(dp[i][:tmp_W+1])
        tmp_max_V = max(dp[i][:tmp_W+1])
        ans = max(ans, tmp_max_V)
print(ans)
### BUGGY CODE ###

#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

#input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


h , w = map(int , input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1
cw-=1
dh-=1
dw-=1
arr = [list(input()) for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.append((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])



### FIXED CODE ###

#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
def valid(a,b):
	#print(a,b)
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


h , w = map(int , input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch-=1
cw-=1
dh-=1
dw-=1
arr = [input() for i in range(h)]
#print(arr)
can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0
#print(dh,dw,ch,cw)
while q:
	#print(q.popleft())
	#print(q)
	curx , cury = q.popleft()
	#can_vis.append((curx,cury))
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.appendleft((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury] + 1:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


if dist[dh][dw] == 10**10:
	print(-1)
else:
	print(dist[dh][dw])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
S = [list(map(int, input().split())) for l in range(Q)]

numList = {}

for n in range(N):
  if A[n] not in numList:
    numList[A[n]] = 0
  numList[A[n]] += 1

for q in range(Q):
  if S[q][0] in numList:
    if S[q][1] not in numList:
      numList[S[q][1]] = 0
    numList[S[q][1]] += numList[S[q][0]]
    numList[S[q][0]] = 0
  sum = 0
  for key, value in numList.items():
    sum += key * value
  print(sum)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
S = [list(map(int, input().split())) for l in range(Q)]
 
numList = {}
sum = 0

for n in range(N):
  if A[n] not in numList:
    numList[A[n]] = 0
  numList[A[n]] += 1
  sum += A[n]

for q in range(Q):
  if S[q][0] in numList:
    if S[q][1] not in numList:
      numList[S[q][1]] = 0
    sum += (S[q][1] - S[q][0]) * numList[S[q][0]]
    numList[S[q][1]] += numList[S[q][0]]
    numList[S[q][0]] = 0
  print(sum)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
for i in l:
  p*=i
if p>1000000000000000000:
  print('-1')
else:
  print(p)


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
p=1
flag=1
zero=0 
for i in l:
    if i==0 :
        zero=1 
        break 
if zero==0:
    for i in l:
        p*=i
        if p>1000000000000000000:
            flag=0
            break
    if flag==0:
        print('-1')
    else:
        print(p)
else : 
    print("0")
### BUGGY CODE ###

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

if not ((2 <= K and K <= 2500) or (0 <= S and S <= 3*K)):
    exit()

count = 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:
                count+=1

print(count)


### FIXED CODE ###

import itertools

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

if not ((2 <= K and K <= 2500) or (0 <= S and S <= 3*K)):
    exit()

count = 0
for X in range(0, K + 1):
    for Y in range(0, K + 1):
        if 0 <= (S - X - Y) and (S - X - Y) <= K:
            count += 1

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

M = 15140366

def getkey(text):
    dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
    sum = 0
    p = 1
    for c in text:
        sum += p*dic[c]
        p *= 5
    return sum

def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

dict = {}
def find(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict.get(h) == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):
    global dict
    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict.get(j) == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
for i in range(n):
    op, text = input().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')



### FIXED CODE ###

import sys

M = 1046527
def h1(key):
    return key % M

def h2(key):
    return 1 + (key %(M-1))

def h3(key, i):
    return (h1(key) + i*h2(key)) % M

word_dic = {'A': 1, 'T': 2, 'G': 3, 'C': 4}
def getkey(text):
    sum = 0
    p = 1
    for c in text:
        sum += p*word_dic[c]
        p *= 5
    return sum

dict = [None for i in range(M)]
def find(text):
    key = getkey(text)
    i = 0
    while i < M:
        h = h3(key, i)
        if dict[h] == None:
            break
        elif dict[h] == text:
            return True
        i += 1
    return False

def insert(text):

    key = getkey(text)
    i = 0
    while i < M:
        j = h3(key, i)
        if dict[j] == None:
            dict[j] = text
            break
        else:
            i += 1

n = int(input())
operations = sys.stdin.readlines()
for ope in operations:
    op, text = ope.rstrip().split(' ')
    if op == 'insert':
        insert(text)
    elif op == 'find':
        rst = find(text)
        if rst:
            print('yes')
        else:
            print('no')
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

    def calc_idx(x, y):
        if x > y:
            x, y = y, x
        return x + y*(y-1)//2

    # create graphs & calc indegree
    n_game = n * (n-1) // 2
    edge = [[] for i in range(n_game)]
    indegree = [0] * n_game
    for i in range(n):
        for j in range(1, n-1):
            g1 = calc_idx(i, a[i][j-1])
            g2 = calc_idx(i, a[i][j])
            edge[g1].append(g2)
            indegree[g2] += 1


    ans = 0
    cand = deque([(i, 1) for i in range(n_game) if indegree[i] == 0])
    n_ts = 0
    while len(cand) > 0:
        u, day = cand.popleft()
        ans = max(ans, day)
        n_ts += 1
        for v in edge[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand.append((v, day+1))

    if n_ts != n_game:
        ans = -1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

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

n, m = map(int, input().split())
broken_list = [int(input()) for _ in range(m)]
a = [0] * (n+1)
a[0] = 1
a[1] = 0 if 1 in broken_list else 1

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in range(2, n+1):
  if i in broken_list:
    a[i] = 0
  else:
    a[i] = a[i-1] + a[i-2]

print(a[n]%1000000007)

### FIXED CODE ###

n, m = map(int, input().split())

a = 1
b = 1

i = 2

for j in range(m):
  ind = int(input())
  if ind == 1:
    b = 0
    continue
  while i < ind:
    a, b = b, a+b
    i += 1
  else:
    a, b = b, 0
    i += 1
    
while i < n+1:
  a, b = b, a+b
  i += 1
  
  
print(b%1000000007)
### BUGGY CODE ###

#094
n=int(input())
x=list(map(int,input().split()))
x.insert(0,0) #x[0]に0を挿入
sorted_x = sorted(x[:])

for i in range(1,n+1):
    idx = sorted_x.index(x[i])
    print(sorted_x[n//2+1] if idx<=n//2 else sorted_x[n//2])

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
x.insert(0,0) #x[0]に0を挿入
sorted_x = sorted(x[:])

l,r=sorted_x[n//2],sorted_x[n//2+1]

for i in range(1,n+1):
    print(r if x[i]<=l else l)
### BUGGY CODE ###

import sys

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

l,r = map(int,input().split())
mod = 2019
a = range(l, r + 1)
for i in range(mod):
    m = l * (l + 1)
    M = (r - 1) * r
    for j in range(m // mod, M // mod + 1):
        b = j * mod + i
        c = make_divisors(b)
        #print(b, c)
        for k in c:
            d = b // k
            #print(k, d)
            if k != d and l <= k and k <= r and l <= d and d <= r:
                #print('i: ',end='')
                print(i)
                sys.exit()


### FIXED CODE ###

l,r = map(int,input().split())
ans = 2018
for i in range(l, min(r, l + 2019)):
    for j in range(i + 1, min(r + 1, i + 2020)):
        ans = min(ans, (i * j) % 2019)
print(ans)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [list(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [[INF for _ in range(n+1)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	dp[i+1][0] = 0
	for j in range(1, i+2):
		dp[i+1][j] = min(dp[i+1][j], dp[i][j])
		if dp[i][j-1] <= men[i][0]:
			dp[i+1][j] = min(dp[i+1][j], dp[i][j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[n][i] < INF:
		ans = i
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
men = [tuple(map(int, input().split())) for _ in range(n)]
men.sort(key=lambda x: (x[0]+x[1], -x[0]))
allowed = [-1 for _ in range(n)]
allowed[n-1] = men[-1][0]
for i in range(n-2, -1, -1):
	allowed[i] = max(allowed[i+1], men[i][0])

INF = 10**10
dp = [INF for _ in range(n+1)]
dp[0] = 0
for i in range(n):
	for j in range(i+1, 0, -1):
		if dp[j-1] <= men[i][0]:
			dp[j] = min(dp[j], dp[j-1] + men[i][1])

#print(dp)
for i in range(n+1):
	if dp[i] < INF:
		ans = i
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
li_a = list(map(int, input().split()))
li_w = li_a
for i in range(m):
    li_w = sorted(li_w, reverse=True)
    li_w[0] = li_w[0] // 2

print(sum(li_w))


### FIXED CODE ###

import heapq
import math

n, m = map(int, input().split())
li_a = list(map(lambda x: x * -1, (map(int, input().split()))))
heapq.heapify(li_a)


for i in range(m):
    w = heapq.heappop(li_a)
    heapq.heappush(li_a, math.ceil(w / 2))

print(sum(li_a) * -1)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
q = int(input())
ans = []

for _ in range(q):
    b, c = input().split()
    atmp = " ".join(a)
    atmp = atmp.replace(b, c)
    a = atmp.split(" ")
    anew = [int(x) for x in a]
    ans.append(sum(anew))
    
print(*ans, sep='\n')

### FIXED CODE ###

import collections

n = int(input())
arr = list(map(int, input().split()))
cnt = collections.defaultdict(int)

for val in arr:
    cnt[val] += 1

sums = sum(arr)
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    diff = (c-b)*(cnt[b])
    sums += diff
    print(sums)
    cnt[c] += cnt[b]
    cnt[b] = 0
### BUGGY CODE ###

S = input()
N = len(S)

for i in range(N):
    fn = len(S)
    S = S.replace('01', '').replace('10', '')
    if fn == len(S):
        break

print(N - len(S))

### FIXED CODE ###

S = input()
N = len(S)
A = 0

for i in range(N):
    if S[i] == '1':
        A = A + 1

print(min(N - A, A)*2)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
	a.append(int(input()))

mod = 1000000007

memo = [0]*(n+1)
memo[0] = 1


for i in range(1, n+1):
    memo[i] = memo[i-1] + memo[i-2]
    if i in a:
        memo[i] = 0

print(memo[-1]%mod)

### FIXED CODE ###

n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))

mod = 1000000007

memo = [-1]*(n+1)
memo[0] = 0

for k in range(m):
    memo[a[k]] = 0

for i in range(1, n+1):
    if memo[i] != -1:
        pass 
    elif i <= 2:
        memo[i] = memo[i-1] + 1
    else:
        memo[i] = memo[i-1] + memo[i-2]
print(memo[-1]%mod)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

l= []
r = []
lr = []
p = []
q = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)
    l.append(lri[0])
    r.append(lri[1])

lr.sort(key=lambda x:(x[0],x[1]))
l.sort()

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp2 = [z[1] for z in lr[idxl:]]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)
### BUGGY CODE ###

#!/usr/bin/env python

from copy import deepcopy

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa, skip):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        if i == skip:
            continue
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

for i in range(len(a)):
    print(price(a, i))


### FIXED CODE ###

#!/usr/bin/env python

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, = read_line(int)
a = read_line(*([int] * n))

def price(aa):
    sum = 0

    prev = 0
    for i in range(len(aa)):
        sum += abs(prev - aa[i])
        prev = aa[i]

    sum += abs(prev)
    return sum

aa = [0] + a + [0]
price_all = 0

for i in range(len(aa) - 1):
    price_all += abs(aa[i] - aa[i + 1])

for i in range(1, len(aa) - 1):
    p = price_all
    p -= abs(aa[i - 1] - aa[i])
    p -= abs(aa[i] - aa[i + 1])
    p += abs(aa[i - 1] - aa[i + 1])
    print(p)
### BUGGY CODE ###

n = int(input())
for x in range(1,(n+1)):
         ans = 0
         for i in range(1,int((n ** (1/2)))):
                  for j in range(1,int((n ** (1/2)))):
                           for k in range(1,int((n ** (1/2)))):
                                    if (i*i) + (j*j) + (k*k) + (i*j) + (j*k) + (k*i) == x:
                                             ans += 1
         print(ans)


### FIXED CODE ###

n = int(input())
ans = [0 for _ in range(10050)]
for i in range(1,105):
         for j in range(1,105):
                  for k in range(1,105):
                           v = i*i+j*j+k*k+i*j+j*k+k*i;
                           if v<10050:
                                    ans[v]+=1
for i in range(n):
         print(ans[i+1])