Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
#print(N,M)
#print(A)
#print(BC)
#print("---")
A = sorted(A)
BC = sorted(BC, key = lambda x: -x[1])
D = []
for bc in BC :
    for i in range(bc[0]) :
        if len(D) < N :
            D.append(bc[1])
        else :
            break
    else :
        continue
    break
#print(A)
#print(D)
for i in range(N) :
    if A[i] < D[i] :
        A[i] = D[i]
    else :
        break
print(sum(A))

#times = [bc[0] for bc in BC]
#values = [bc[1] for bc in BC]
#values, times = zip(*sorted(zip(values, times),reverse=True))
#print(values)
#print(times)
#values.sort(reverse=True)


# for i, v in enumerate(values) :
#     tmp = [n for n,i in enumerate(A) if i > v]
#     if len(tmp) == N :
#         break
#     elif len(tmp) == 0 :
#         ind = N + 1
#     else :
#         ind = tmp[0]
#
#     if times[i] < ind :
#         A[0:times[i]] = [v] * times[i]
#     else :
#         A[0:ind] = [v] * ind
#     #print(A)
#     A = sorted(A)
# print(sum(A))

#for i, v in enumerate(values) :
#    for t in range(times[i]) :
#        min_A = min(A)
#        if v > min_A :
#            A[A.index(min(A))] = v
#            print(A)
#        else :
#            break
#    else:
#        continue
#    break
#print(sum(A))





### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]
#print(N,M)
#print(A)
#print(BC)
#print("---")
A = sorted(A)
BC = sorted(BC, key = lambda x: -x[1])
D = []
for bc in BC :
    for i in range(bc[0]) :
        if len(D) < N :
            D.append(bc[1])
        else :
            break
    else :
        continue
    break
if N > len(D) :
    S = len(D)
else :
    S = N
for i in range(S) :
    if A[i] < D[i] :
        A[i] = D[i]
    else :
        break
print(sum(A))

#times = [bc[0] for bc in BC]
#values = [bc[1] for bc in BC]
#values, times = zip(*sorted(zip(values, times),reverse=True))
#print(values)
#print(times)
#values.sort(reverse=True)


# for i, v in enumerate(values) :
#     tmp = [n for n,i in enumerate(A) if i > v]
#     if len(tmp) == N :
#         break
#     elif len(tmp) == 0 :
#         ind = N + 1
#     else :
#         ind = tmp[0]
#
#     if times[i] < ind :
#         A[0:times[i]] = [v] * times[i]
#     else :
#         A[0:ind] = [v] * ind
#     #print(A)
#     A = sorted(A)
# print(sum(A))

#for i, v in enumerate(values) :
#    for t in range(times[i]) :
#        min_A = min(A)
#        if v > min_A :
#            A[A.index(min(A))] = v
#            print(A)
#        else :
#            break
#    else:
#        continue
#    break
#print(sum(A))
a, b = list(map(int, input().split))
result = 0
for _ range(2):
  if a >= b:
    result += a
    a -= 1
  else:"
    result += b
    b -= 1
print(result)

### FIXED CODE ###

a, b = list(map(int, input().split()))
result = 0
for _ in range(2):
  if a >= b:
    result += a
    a -= 1
  else:
    result += b
    b -= 1
print(result)
import numpy in np

a, b = input().split()
a = a+b

if np.sqrt(int(a)).is_integer():
	print("Yes")
else:
	print("No")


### FIXED CODE ###

import numpy as np

a, b = input().split()
a = a+b

if np.sqrt(int(a)).is_integer():
	print("Yes")
else:
	print("No")
import math

N, X = map(int, input().split())
x = list(map(int, input().split()))

dx = [abs(X - v) for v in x]
ans = dx[0]
for b in dx[1:]:
    ans = math.gcd(ans, b)
print(ans)


### FIXED CODE ###

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

N, X = map(int, input().split())
x = list(map(int, input().split()))

dx = [abs(X - v) for v in x]
ans = dx[0]
for b in dx[1:]:
    ans = gcd(ans, b)
print(ans)
l = input()
print("Yes" if l[0]=l[2] else "No") 


### FIXED CODE ###

l = input()
print("Yes" if l[0]==l[2] else "No")
m=input()
def s(x):
  if x=='1':
    return '9'
  else:
    return '1'
print(s(m[0])+s(m[1])+s(m[2])

### FIXED CODE ###

m=input()
def s(x):
  if x=='1':
    return '9'
  else:
    return '1'
print(s(m[0])+s(m[1])+s(m[2]))
s,t=input(),input() print((s[0]==t[0])+(s[1]==t[1])+(s[2]==t[2]))

### FIXED CODE ###

s,t=input(),input() 
print((s[0]==t[0])+(s[1]==t[1])+(s[2]==t[2]))
while True:
     (a, op, b) = input().split()
     a = int(a)
     b = int(b)

     if op = '?':
          break
     elif op = '+':
          print()
     elif op = '-':
          print()
     elif op = '*':
          print()
     elif op = '/':
          print()

### FIXED CODE ###

while True:
    (a, op, b) = input().split()
    a = int(a)
    b = int(b)

    if op == '?':
        break
    elif op == '+':
        print(a + b)
    elif op == '-':
        print(a - b)
    elif op == '*':
        print(a * b)
    elif op == '/':
        print(a // b)
str = input().split()
plus = str[0] + str[1]
minus = str[0] - str[1]
mul = str[0] * str[1]
if(plus > minus):
  if(plus > mul):
    max = plus
  else:
    max = mul
if(minus > plus):
  if(minus > mul):
    max = minus
  else:
    max = mul
if(plus > minus):
  if(plus > mul):
    max = plus
  else:
    max = mul

### FIXED CODE ###

num = input().split()
n1 = int(num[0])
n2 = int(num[1])
plus = n1 + n2
minus = n1 - n2
mul = n1 * n2
max = max(max(plus,minus), mul)
print(max)
import math
r = int(raw_input())
pai = 3.1415
print('%.5f %.5f' % (r*r*math.pi, 2*math.pi*r))

### FIXED CODE ###

import math
r = float(raw_input())
print('%.5f %.5f' % (r*r*math.pi, 2*math.pi*r))
a,b,c = map(int,input().split())
if b <= a:
  print(No)
elif c <= b:
  print(No)
else:
  print(Yes)

### FIXED CODE ###

a,b,c = map(int,input().split())
if b <= a:
  print('No')
elif c <= b:
  print('No')
else:
  print('Yes')
N = int(input())
A = list(map(int, input().split()))
LIST = [0]*(10001)
sum = sum(A)
for i in A:
    LIST[i]+=1
Q = int(input())
b =[0]*Q
c =[0]*Q
for i in range(Q):
    b[i], c[i] = map(int, input().split())
for i in range(Q):
    LIST[c[i]]+=LIST[b[i]]
    sum+=LIST[b[i]]*(c[i]-b[i])
    LIST[b[i]]= 0
    print(sum)


### FIXED CODE ###

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

for i in a:
    num[i] += 1

s = sum(a)

for i in range(q):
    s += (c[i]-b[i])*num[b[i]]
    num[c[i]] += num[b[i]]
    num[b[i]] = 0
    print(s)
def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(range(1,k+1))
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

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

### FIXED CODE ###

from collections import deque

def solve(n, a, b):
    E = {(i+1): [] for i in range(n)}
    G = {}
    for i in range(n-1):
        u, v = a[i], b[i]
        E[u].append(v)
        E[v].append(u)
        G[u, v] = 0
        G[v, u] = 0
    k = max(map(len, E.values()))
    V = {v: set() for v in E.keys()}
    que = deque(range(1,k+1))
    for u, vs in E.items():
        for v in vs:
            if G[u, v] != 0:
                continue
            while que:
                c = que.popleft()
                que.append(c)
                if (not c in V[u]) and (not c in V[v]):
                    V[u].add(c)
                    V[v].add(c)
                    G[u, v] = c
                    G[v, u] = c
                    break
    res = [k]
    for i in range(n-1):
        res.append(G[a[i], b[i]])
    return "\n".join(map(str, res))

n = int(input())
a = [0] * n
b = [0] * n
for i in range(n-1):
    a[i], b[i] = map(int, input().split())
print(solve(n, a, b))
N,L = list(map(int,input().split(" ")))

apple = list(range(L,L+N))

s = sum(apple)

m = 1000000000000000000
for x in apple:
  if abs(m) > abs(x):
    m = x

print(s-m)

### FIXED CODE ###

s = input()

flag = True
for i in range(len(s)-1):
  if s[i] == s[i+1]:
    print("Bad")
    flag = False
    break
if flag:
  print("Good")
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)


n,x=map(int,raw_input().split())
print 3*(n-gcd(n,x))

### FIXED CODE ###

n=int(raw_input())
N=map(int,raw_input().split())
N.sort()
count=0
for i in range(n):
    count+=N[2*i]
print count
n = int(input())
s, t = input().split()
 
res = ''
 
for i in range(n):
  res = res + str(s[i]) + str(t[i])
  
print(res)

### FIXED CODE ###

a = int(input())
b = int(input())
 
if (a != 1 and b != 1):
  print(1)
elif (a != 2 and b != 2):
  print(2)
else:
  print(3)
return (a+b)*h/2

### FIXED CODE ###

a = int(input())
b = int(input())
h = int(input())
print(int((a+b)*h/2))
S =input()
ans_list = []
for i in range(2**(len(S)-1)):
    comb = bin(i)[2:].zfill(len(S)-1)
    num_list = []
    num = S[0]
    for i in range(len(comb)):
        if comb[i] == "1":
            num_list.append(int(num))
            num = S[i+1]
        else:
            num += S[i+1]
    num_list.append(int(num))
    ans_list.append(sum(num_list))
print(sum(ans_list))

### FIXED CODE ###

S =input()
ans_list = []
if len(S) == 1:
    print(int(S))
else:
    for i in range(2**(len(S)-1)):
        comb = bin(i)[2:].zfill(len(S)-1)
        num_list = []
        num = S[0]
        for i in range(len(comb)):
            if comb[i] == "1":
                num_list.append(int(num))
                num = S[i+1]
            else:
                num += S[i+1]
        num_list.append(int(num))
        ans_list.append(sum(num_list))
    print(sum(ans_list))
d = input()
a = int(input())
p = []
k = len(d)
for i in range(k):
  for j in range(5):
    if i + j + 1 <= k-1:
      p.append(d[i:i+j+1])
    
x = list(set(p))
x.sort()
del x[0]
 
print(x[a-1])

### FIXED CODE ###

d = input()
a = int(input())
p = []
k = len(d)
for i in range(k):
  for j in range(min({6,k-i+1})):
    p.append(d[i:i+j])
    
x = list(set(p))
x.sort()
del x[0]
 
print(x[a-1])
print(round(mean([int(i) for i in input().split()] )))

### FIXED CODE ###

import math
print(math.ceil(sum([int(i) for i in input().split()] )/ 2))
def main():
    A = [list(map(int,input().split(" "))) for i in range(3)]
    N = int(input())
    b_list = [int(input()) for _ in range(N)]

    for i in range(3):
        for j in range(3):
            for b in b_list:
                if(A[i][j] == b):
                    A[i][j] = 0

    flag = False
    for i in range(3):
        for j in range(3):
                if(j+2 < 3 and A[i][j] == 0 and A[i][j+1] == 0 and A[i][j+2] == 0):
                    flag = True
                    break
                if(i+2 < 3 and A[i][j] == 0 and A[i+1][j] == 0 and A[i+2][j] == 0):
                    flag = True
                    break
                if(i+2 < 3 and j+2 < 3 and A[i][j] == 0 and A[i+1][j+1] == 0 and A[i+2][j+2] == 0):
                    flag = True
                    break
                if(i-2 >= 0 and j-2 >= 0 and A[i][j] == 0 and A[i-1][j-1] == 0 and A[i-2][j-2] == 0):
                    flag = True
                    break
                if(i-2 >= 0 and j+1 < 3 and A[i][j] == 0 and A[i-1][j+1] == 0 and A[i-2][j+2] == 0):
                    flag = True
                    break
                if(i+2 < 3 and j-2 >= 0 and A[i][j] == 0 and A[i+1][j-1] == 0 and A[i+2][j-2] == 0):
                    flag = True
                    break
        if(flag):
            break

    if(flag):
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    A = [list(map(int,input().split(" "))) for i in range(3)]
    N = int(input())
    b_list = [int(input()) for _ in range(N)]

    for i in range(3):
        for j in range(3):
            for b in b_list:
                if(A[i][j] == b):
                    A[i][j] = 0

    flag = False
    for i in range(3):
        for j in range(3):
                if(j+2 < 3 and A[i][j] == 0 and A[i][j+1] == 0 and A[i][j+2] == 0):
                    flag = True
                    break
                if(i+2 < 3 and A[i][j] == 0 and A[i+1][j] == 0 and A[i+2][j] == 0):
                    flag = True
                    break
                if(i+2 < 3 and j+2 < 3 and A[i][j] == 0 and A[i+1][j+1] == 0 and A[i+2][j+2] == 0):
                    flag = True
                    break
                if(i-2 >= 0 and j-2 >= 0 and A[i][j] == 0 and A[i-1][j-1] == 0 and A[i-2][j-2] == 0):
                    flag = True
                    break
                if(i-2 >= 0 and j+2 < 3 and A[i][j] == 0 and A[i-1][j+1] == 0 and A[i-2][j+2] == 0):
                    flag = True
                    break
                if(i+2 < 3 and j-2 >= 0 and A[i][j] == 0 and A[i+1][j-1] == 0 and A[i+2][j-2] == 0):
                    flag = True
                    break
        if(flag):
            break

    if(flag):
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()
n=int(input())
if n%2:
    print(0)
else:
    l=0
    x=n//2
    while x>0:
        l+=n//5
        x=n//5
print(l)

### FIXED CODE ###

n = int(input())
if n%2:
  print(0)
else:
  p=n//2
  l=0
  while p>0:
    l+=p//5
    p//=5
  print(l)
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

# weighted graph
for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

# while len(cache)>0:
#     if not dfs(G, (list(cache)[0], 0)):
#         print('No')
#         break
# else:
#     print('Yes')

if dfs(G, (0, 0)):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

from collections import deque

def main():
    N, M = map(int, input().split())
    link = [[] for _ in range(N+1)]
    value = [0 for _ in range(N+1)]

    for _ in range(M):
        l, r, d = map(int, input().split())
        link[l].append((r, d))
        link[r].append((l, -d))

    searched = set()
    q = deque()
    for u in range(N+1):
        if u in searched:
            continue
        q.append(u)
        searched.add(u)
        value[u] = 0

        # search
        while q:
            x = q.popleft()
            for y, d in link[x]:
                if y not in searched:
                    value[y] = value[x] + d
                    q.append(y)
                    searched.add(y)

    # verify
    for x in range(N+1):
        for y, d in link[x]:
            if value[y] != value[x] + d:
                print('No')
                return
    else:
        print('Yes')

if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

s=sum(A)
n=int(s**0.5)

#約数のリスト
cd=[]

for i in range(1,n+2):
	if s%i==0:
		cd.append(i)
		cd.append(s/i)

cd.sort(reverse=True)

def check(t):
	A_temp=[]
	for x in A:
		A_temp.append(x%t)

	A_temp.sort()

	#Aの配列をmod tした配列A_tempの累積和
	A_temp_sum=[]

	for i,x in enumerate(A_temp):
		if i==0: A_temp_sum.append(x)
		else: A_temp_sum.append(A_temp_sum[-1]+x)

	#配列の前半は、数字をマイナスしていく
	p1=bisect_left(A_temp_sum,K)
	if A_temp_sum[p1]<=K:
		k1=A_temp_sum[p1]
	else:
		p1-=1
		k1=A_temp_sum[p1]

	#配列の後半で、数字をどれだけプラスする必要があるか
	k2=t*(N-p1-1)-(A_temp_sum[-1]-A_temp_sum[p1])

	#プラスする量が、マイナスする量より少なければ成立
	if k2<=k1:
		return True
	else:
		return False

for x in cd:
	if check(x):
		print x
		quit()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())

s=sum(A)
n=int(s**0.5)

#約数のリスト
cd=[]

for i in range(1,n+2):
	if s%i==0:
		cd.append(i)
		cd.append(s/i)

cd.sort(reverse=True)

def check(t):
	if t==1: return True
	A_temp=[]
	for x in A:
		A_temp.append(x%t)

	A_temp.sort()

	#Aの配列をmod tした配列A_tempの累積和
	A_temp_sum=[]

	for i,x in enumerate(A_temp):
		if i==0: A_temp_sum.append(x)
		else: A_temp_sum.append(A_temp_sum[-1]+x)

	#配列の前半は、数字をマイナスしていく
	p1=min(bisect_left(A_temp_sum,K),N-2)
	if A_temp_sum[p1]<=K:
		k1=A_temp_sum[p1]
	else:
		#配列の項数p1の値がKを超えている場合は、p1の1個手前の値をとる
		p1-=1
		k1=A_temp_sum[p1]


	#配列の後半で、数字をどれだけプラスする必要があるか
	k2=t*(N-p1-1)-(A_temp_sum[-1]-A_temp_sum[p1])

	#プラスする量が、マイナスする量より少なければ成立
	if k2<=k1:
		return True
	else:
		return False

for x in cd:
	if check(x):
		print x
		quit()
N = int(input())
ab = [list(map(int, input().split())) for _ in range(max(1, N-1))]
c = list(map(int, input().split()))
c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
if N == 1:
    print(c[0])
    exit()

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N-1)]
c = list(map(int, input().split()))

if N == 1:
    print(0)
    print(c[0])
    exit()

c.sort(reverse = True)
edge = [[] for _ in range(N)]
for a, b in ab:
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v, p):
    global ans
    global count
    if p != -1:
        anse[v] = c[count+1]
        ans += min(anse[v], anse[p])
        count += 1
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(nv, v)

#search = [i for i, e in enumerate(edge) if len(e) == 1]
search = [0]
res = 0
rese = [None for _ in range(N)]
for i in search:
    count = 0
    ans = 0
    anse = [None for _ in range(N)]
    anse[i] = c[0]
    dfs(i, -1)
    if res < ans:
        res = ans
        rese = anse
print(res)
print(" ".join(map(str, rese)))
def main():
    N = int(input())
    l = list(map(int, input().split()))
    ans = []
    X = sum(l)
    for i in range(N-1):
      	X = abs(X-2*l[i])
        ans.append(X)
    print(min(ans))
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int, input().split()))
    ans = []
    sunuke = 0
    arai = sum(l)
    for i in range(N-1):
        sunuke += l[i]
        arai   -= l[i]
        ans.append(abs(sunuke-arai))
    print(min(ans))
if __name__ == '__main__':
    main()
N, K = map(int, input().split())
S = str(input())
S_list = []
cum_list = [0]
tmp = 1
count = 0
if "0" not in S:
    print(len(S))
else:
    for i in range(N):
        if i == 0:
            if int(S[i]) == tmp:
                count += 1
            else:
                S_list.append(count)
                count = 1
        else:
            if S[i] == S[i - 1]:
                count += 1
                if i == N - 1:
                    S_list.append(count)
            else:
                S_list.append(count)
                count = 1


    if S[-1] == "0":
        S_list.append(0)




    now = 0
    for i in range(len(S_list)):
        now += S_list[i]
        cum_list.append(now)
    def check(x,K):
        answer_list = []
        i = 0
        if i + 2 * K + 1 < len(x):
            while i + 2 * K + 1 < len(x):
                answer_list.append(x[i + 2 * K + 1] - x[i])
                i += 2
            return answer_list
        elif K > 0:
            check(x,K-1)
    answer_list = check(cum_list,K)

    answer = max(answer_list)
    print(answer)

### FIXED CODE ###

A, B = map(int, input().split())
if max(A,B) - min(A,B) >= 1:
    answer = max(A,B) * 2 - 1
else:
    answer = 2 * max(A,B)
print(answer)
H,W,K=map(int,input().split())
ls=[]
for i in range(H):
    ls.append(input())
ld=[]
f=0
#n=1
ns=0
for i in range(H):
    nstmp=0
    ld.append([])
    for j in range(W):
        if ls[i][j]=="#":
            nstmp+=1
            ns+=1
            if nstmp==2:
                #ld[i].append(j)
                #n+=1
                #ld[i].append((j,ns))
                ld[i].append((j,ns-1))#jより小さいところはns-1区画
                nstmp=1
                #n+=1
    if nstmp==1:
        ld[i].append((j+1,ns))
    if not ld[i]:
        if i==0:
            f=1
        else:
            ld[i]=ld[i-1]
    #n+=1
if f==1:
    ld[0]=ld[1]
#print(ld)
for i in range(H):
    k=0
    for j in range(W):
        if j>=ld[i][k][0]:
            k+=1
        print(ld[i][k][1],end=" ")
    print("")


### FIXED CODE ###

H,W,K=map(int,input().split())
ls=[]
for i in range(H):
    ls.append(input())
ld=[]
#f=0
f=-1
#n=1
ns=0
for i in range(H):
    nstmp=0
    ld.append([])
    for j in range(W):
        if ls[i][j]=="#":
            nstmp+=1
            ns+=1
            if nstmp==2:
                #ld[i].append(j)
                #n+=1
                #ld[i].append((j,ns))
                ld[i].append((j,ns-1))#jより小さいところはns-1区画
                nstmp=1
                #n+=1
    #print("j",j)
    if nstmp==1:
        ld[i].append((j+1,ns))
    if not ld[i]:
        if i==0:
            f=0
        elif not ld[i-1]:
            f+=1
        else:
            ld[i]=ld[i-1]
    #n+=1
#if f==1:
    #ld[0]=ld[1]
if f>-1:
    for i in range(f,-1,-1):
        ld[i]=ld[i+1]
#print(ld)
for i in range(H):
    k=0
    for j in range(W):
        if j<ld[i][k][0]:
            print(ld[i][k][1],end=" ")
        else:
            k+=1
            print(ld[i][k][1],end=" ")
    print("")
import sys
INFTY=sys.maxsize

def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(1,n):
        u,v,w=map(int,input().split())
        nList[u].append((v,w))
        nList[v].append((u,w))

    return n,nList

WHITE=0
GRAY=1
BLACK=2
status=[]
color=[]

def dfs(s,nList):
    for u,w in nList[s]:
        if status[u]==WHITE:
            if w%2==0:
                color[u]=color[s]
            else:
                color[u]=(color[s]+1)%2
            status[u]=GRAY
            dfs(u,nList)
    status[u]=BLACK

def main(n,nList):
    global status
    global color

    status=[WHITE]*(n+1)
    color=[WHITE]*(n+1)
    dfs(1,nList)

    for i in range(1,n+1):
        print(color[i])
    

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)
    #print(ans)


### FIXED CODE ###

import sys
INFTY=sys.maxsize
sys.setrecursionlimit(100000)

def readinput():
    n=int(input())
    nList=[]
    for _ in range(n+1):
        nList.append([])
    for _ in range(1,n):
        u,v,w=map(int,input().split())
        nList[u].append((v,w))
        nList[v].append((u,w))

    return n,nList

WHITE=0
GRAY=1
BLACK=2
status=[]
color=[]

def dfs(s,nList):
    for u,w in nList[s]:
        if status[u]==WHITE:
            if w%2==0:
                color[u]=color[s]
            else:
                color[u]=(color[s]+1)%2
            status[u]=GRAY
            dfs(u,nList)
    status[s]=BLACK

def main(n,nList):
    global status
    global color

    status=[WHITE]*(n+1)
    color=[WHITE]*(n+1)
    dfs(1,nList)

    for i in range(1,n+1):
        print(color[i])
    

if __name__=='__main__':
    n,nList=readinput()
    main(n,nList)
    #print(ans)