Harryxun/stf_run huggingface dataset:
n = int(raw_input())
pts = [map(int, raw_input().split()) for i in xrange(n)]

for i in xrange(105):
    for j in xrange(105):
        H = -7
        ok = True
        for k in pts:
            if max(H - abs(k[0] - i) - abs(k[1] - j), 0) == k[2]:
                continue
            elif H < 1:
                H = k[2] + abs(k[0] - i) + abs(k[1] - j)
            else:
                ok = False
        if ok:
            print i, j, max(H, 1)
            exit(0)

### FIXED CODE ###

n = int(raw_input())
if n == 1:
    print "Hello World"
else:
    print int(raw_input()) + int(raw_input())
def gcd(a, b):
 if a < b:
    a, b = b, a
 if b == 0:
    return a
 c = a % b
 return gcd(b, c)
def lcm(a,b):
  return int(a*b/gcd(a,b))

N = int(input())
ans = 1
for i in range(N):
    t = int(input())
    ans = lcm(t,ans)

print(ans)

### FIXED CODE ###

N = int(input())
T = [int(input()) for i in range(N)]

from functools import reduce
from fractions import gcd

def lcm(a,b):
  return a*b //gcd(a,b)

print(reduce(lcm,T))
a,b=map(int,input())
if a<10:
  print(b+(100*(10-a))
else:
  print(b)
        

### FIXED CODE ###

a,b=map(int,input().split())
if a<10:
  print(b+(100*(10-a)))
else:
  print(b)
import math
n=int(input())
mod=1000000007
ans=0
sum=0
s=[int(n) for n in input().split()]
ans=1
for i in s:
    ans*=i//math.gcd(ans,i)
for i in range(0, n):
    sum=(sum+ans//(s[i]))%mod
print(sum)


### FIXED CODE ###

n=int(input())
a=[int(j) for j in input().split()]
t=1
mod=10**9+7
from fractions import*
for i in a:
    t*=i//gcd(t,i)
print(sum(t//i for i in a)%mod)
r,c = (int(x) for x in input().split())

table = []
i = 0

while i < r
  table[0] = list(int(x) for x in input().split())
  i += 1

# output R
i,j = 0,0
while i < r
  sum = 0
  while j < c
    if j != 0:
      print(' ')
    print(' ' + teble[i][j], end='')
    sum += table[i][j]
    j += 1
    if j == c:
      print(' ' + sum)

i,j = 0
while j < c:
  while i < r:
  i += 1


### FIXED CODE ###

r,c = (int(x) for x in input().split())

table = []
i = 0

while i < r:
  table.append(list(int(x) for x in input().split()))
  i += 1

i,j = 0,0
for i in table:
  sum = 0
  for idx,j in enumerate(i):
    if idx != 0:
      print(' ', end='')
    print(j, end='')   
    sum += j
  print(' ' + str(sum))

j,ttl = 0,0
while j < c:
  i = 0
  sum = 0
  while i < r:
    sum += table[i][j]
    i += 1
  print (sum, end=' ')
  ttl += sum
  j += 1
print(ttl)
N = int(stdin.readline().rstrip())
P = map(int, input().rstrip().split())
Q = map(int, input().rstrip().split())

import itertools
l = list(itertools.permutations(list(range(1, N+1))))
a = l.index(tuple(P))
b = l.index(tuple(Q))
print(abs(a-b))



### FIXED CODE ###

N = int(input().rstrip())
P = map(int, input().rstrip().split())
Q = map(int, input().rstrip().split())

import itertools
l = list(itertools.permutations(list(range(1, N+1))))
a = l.index(tuple(P))
b = l.index(tuple(Q))
print(abs(a-b))
N,K = map(int,input().split())
list[N] = input().split()
MIN = int(list[0])
SUM = 0
for j in range(0,K):
  for i in list:
    if MIN > int(i):
      MIN = int(i)
  list.remove(str(MIN))
  SUM += MIN
  MIN = int(list[0])
print(SUM)


### FIXED CODE ###

N,K = map(int,input().split())
import sys
if N==1:
    print(input())
    sys.exit()
list = input().split()
MIN = 1001
SUM = 0
for j in range(0,K):
  for i in list:
    if MIN > int(i):
      MIN = int(i)
  list.remove(str(MIN))
  SUM += MIN
  MIN = 1001
print(SUM)
N = raw_input().split()
print(N)

### FIXED CODE ###

arg = input().split()

num = int(arg[0]) * int(arg[1])

if (num % 2) == 0:
  print('No')
else:
  print('Yes')
#!/usr/bin/env python3
import sys

def solve(H: int, W: int, s: "List[str]"):
    dp = [[0]*W for _ in range(H)]

    if s[0][0] == "#":
        dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            if i == 0:
                if j == 0:
                    continue

                if s[i][j] == "#" and s[i][j-1] == ".":
                    dp[i][j] = dp[i][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1] 
            else:
                if j == 0:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    dp[i][j] = up
                    continue
                else:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    
                    if s[i][j-1] == "." and s[i][j] == "#":
                        left = dp[i][j-1]+1
                    else:
                        left = dp[i][j-1]
                    
                    dp[i][j] = min(left,up)

    print(dp[H-1][W-1])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    s = [next(tokens) for _ in range(W)]  # type: "List[str]"
    solve(H, W, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
# input = sys.stdin.r/eadline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    H,W = MAP()
    s = [input() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]

    if s[0][0] == "#":
        dp[0][0] = 1

    for i in range(H):
        for j in range(W):
            if i == 0:
                if j == 0:
                    continue

                if s[i][j] == "#" and s[i][j-1] == ".":
                    dp[i][j] = dp[i][j-1]+1
                else:
                    dp[i][j] = dp[i][j-1] 
            else:
                if j == 0:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    dp[i][j] = up
                    continue
                else:
                    if s[i-1][j] == "." and s[i][j] == "#":
                        up = dp[i-1][j]+1
                    else:
                        up = dp[i-1][j]
                    
                    if s[i][j-1] == "." and s[i][j] == "#":
                        left = dp[i][j-1]+1
                    else:
                        left = dp[i][j-1]
                    
                    dp[i][j] = min(left,up)

    print(dp[H-1][W-1])

if __name__ == '__main__':
    main()
import re
print sum(map(int,re.sub("\w+"," ",raw_input()).strip().split()))

### FIXED CODE ###

import re, sys
print sum(map(int,re.sub(r"[^\d]+",r" "," ".join(sys.stdin.readlines())).strip().split()))
import math
s1 = input()
s2 = input()
s1 += s2
a = int(s1)
if math.sqrt(a) * math.sqrt(a) == a:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import math
s1, s2 = input().split()
s1 += s2
a = int(s1)
if math.floor(math.sqrt(a)) * math.floor(math.sqrt(a)) == a:
  print("Yes")
else:
  print("No")
N = input()

l = len(N)
j = "9"*(l-1)

if n[i::] == j:
    print(int(n[0])+9*(n-1))
else:
    print(int(n[0])-1+9*(k-1))

### FIXED CODE ###

N = input()
l = len(N)

if N[1::] == '9'*(l-1):
    print(int(N[0])+9*(l-1))
else:
    print(int(N[0])-1+9*(l-1))
import math


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // math.gcd(c, d)
    b_c = b // c
    b_d = b // d
    b_cd = b // lcm
    a_c = (a - 1) // c
    a_d = (a - 1) // d
    a_cd = (a - 1) // lcm
    return b - b_c - b_d + b_cd - (a - 1 - a_c - a_d + a_cd)


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

import fractions


def solve():
    a, b, c, d = map(int, input().split())
    lcm = c * d // fractions.gcd(c, d)
    div_c = b // c - (a - 1) // c
    div_d = b // d - (a - 1) // d
    div_cd = b // lcm - (a - 1) // lcm
    return (b - a + 1) - div_c - div_d + div_cd


if __name__ == "__main__":
    print(solve())
# -*- coding: utf-8 -*-

instr = input()
target = int(input())

# 部分文字列の一覧リストを作成
str_list = []
for i in range(len(instr)):

	for j in range(len(instr)+1):
		
		# 開始位置iの方が大きいものはやる必要がないのでjを増やす
		if i >= j:
			j = i + 1
		
		# targetよりも大きい文字数のものは処理しない
		if j-i > target:
			break

		# 候補となる部分文字列の格納
		str_list.append(instr[i:j])
		j += 1
	i += 1

# 重複削除
str_list = list(set(str_list))
# 昇順ソート
str_list.sort()

print(str_list[target-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

# 入力を各変数に格納
a, b, c, d = map(int, input().split())

# 直接可能
if abs(a - c) <= d:
	print("Yes")
# 間接可能
elif abs(a - b) <= d and abs(b - c) <= d:
	print("Yes")
else:
	print("No")
H,W = input().split()
H,W=int(H),int(W)
sw=[[0]*W]*H

for i in range(W):
    sw[i] = input()

count=0
if sw[0][0]=='#':
    sw[0]='.'+sw[0][1:]
    count+=1
if sw[H-1][W-1]=='#':
    sw[H-1]=sw[H-1][:W-1]+'.'
    count+=1

def search(h,v):
    global H,W
    global sw
    if h>=H-1 and v>=W-1:
        return -2,-2
    elif v>=H-1:
        if sw[h+1][W-1]=='.':
            return h+1,v
        else:
            return -1,-1
    elif h>=W-1:
        if sw[H-1][v+1]=='.':
            return h,v+1
        else:
            return -1,-1
    else:
        if sw[h+1][v]=='.':
            return h+1,v
        elif sw[h][v+1]=='.':
            return h,v+1
        else:
            return -1,-1

h=0
v=0
i=0
while(1):
    flag=True
    for j in range(i+1):
        result = search(h+i-j,v+j)
        if result == (-2,-2):
            print(count)
            exit()
        if result!=(-1,-1):
            i=0
            flag = False
            h,v=result
            break
    if flag:
        count+=1
        i+=1

### FIXED CODE ###

import numpy as np

H,W = input().split()
H,W=int(H),int(W)
P=[0]*H
for i in range(H):
    P[i] = input()

dp=np.zeros((H,W),dtype='u8')
if P[0][0]=='#':
    dp[0][0]=1
else:
    dp[0][0]=0

def DP(y,x):
    global dp
    if 0<=x<=W-1 and 0<=y<=H-1:
        return dp[y][x]
    else:
        return 9999999

for l in range(1,H+W):
    for i in range(l+1):
        if i<H and l-i<W:
            if P[i][l-i]=='#':
                a=DP(i-1,l-i)
                b=DP(i,l-i-1)
                if a < 9999999:
                    if P[i-1][l-i]=='.':
                        a+=1
                if b <  9999999:
                    if P[i][l-i-1]=='.':
                        b+=1
                dp[i][l-i]=min(a,b)
            else:
                #print(i,l-i,DP(i-1,l-i),DP(i,l-i-1))
                dp[i][l-i]=min(DP(i-1,l-i),DP(i,l-i-1))
print(dp[H-1][W-1])
import numpy as np

H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(input())
  
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      print('#', end='')
    count = 0
    for k in range(min(0, i-1), max(i+1, H-1)+1):
      for l in range(min(0, j-1), max(j+1, W-1)+1):
        if A[k][l] == '#':
          count += 1
    print(count, end='')
  print()

### FIXED CODE ###

H, W = map(int, input().split())
A = []
for i in range(H):
  A.append(input())
  
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      print('#', end='')
    else:
      count = 0
      for k in range(max(0, i-1), min(i+1, H-1)+1):
        for l in range(max(0, j-1), min(j+1, W-1)+1):
          if A[k][l] == '#':
            count += 1
      print(count, end='')
  print()
def toggle_nth_bit(num: int, n: int):
    return num ^ (1 << n)

N = int(input())
X = input()
f = 0
count = 1
c = []
fi = 0
for i in range(N-1, -1, -1):
    # print(i)
    fi = toggle_nth_bit(int(X, 2), i)
    f = str(bin(toggle_nth_bit(int(X, 2), i)))
    while fi % f.count("1") != 0:
        fi = fi % f.count("1")
        f = str(bin(fi))
        # print(f)
        # print(fi)
        count += 1
        # print(count)
    c.append(count)
    count = 1

# ans = str(bin(toggle_nth_bit(int(X,2), 0)))
for i in c:
    print(i)

### FIXED CODE ###

def pc(x):
    return format(x, 'b').count('1')


N = int(input())
X = input()
Xo = int(X, 2)

count = 0
ans = 0
ori = pc(Xo)
X = list(X)

Xp = Xo%(ori + 1)
if ori == 1:
    Xm = 0
else:
    Xm = Xo % (ori - 1)

# for i in range(N-1, -1, -1):
for i in range(N):
    if ori == 1 and X[i] == '1':
        print(0)
        continue
    else:
        if X[i] == '1':
            # ans = Xm - pow(2, i, ori - 1)
            ans = Xm - pow(2, N-1-i, ori - 1)
            ans %= ori - 1
        else:
            # ans = Xp - pow(2, i, ori + 1)
            ans = Xp + pow(2, N-1-i, ori + 1)
            ans %= ori + 1
    count = 1
    while ans > 0:
        # count += 1
        # if ans == 1:
        #     break
        ans %= pc(ans)
        count += 1

   
    print(count)
    count = 1
n,m,q = input().split()
list = []
for i in range(int(m)):
    l,r = input().split()
    list.append([int(l),int(r)])
for i in range(int(q)):
    p,q = input().split()
    count = 0
    for j in range(len(list)):
        if int(p) <= list[j][0] and int(q) >= list[j][1]:
            count += 1
    print(count)

### FIXED CODE ###

a,b = input().split()
c = (int(a)-1) * (int(b)-1)
print(c)
import sys

def main(a,b,h)
    reuturn (a+b)*h//2

a =int(sys.stdin.readlin().strip())
b =int(sys.stdin.readlin().strip())
h =int(sys.stdin.readlin().strip())

print(main(a,b,h))


### FIXED CODE ###

import sys

def main(a,b,h):
    return (a+b)*h//2

a =int(sys.stdin.readline().strip())
b =int(sys.stdin.readline().strip())
h =int(sys.stdin.readline().strip())

print(main(a,b,h))
n=int(input())
a=list(map(int,input().split()))
d=[0]*n
for i in range(0,n):
  d[a[i]]=i

print(*d)  

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
d=[0]*n
for i in range(0,n):
  d[a[i]-1]=i+1
print(*d)
import math
from math import gcd as bltin_gcd
def coprime2(a, b):
    return bltin_gcd(a, b) == 1

A, B, C, D = map(int, input().split())
N = B - A + 1  #整数列の長さ

if C == D:
    tmp = 0   #最後にNから引く
    mod = A % C
    tmp += math.ceil((N-mod)/C)
    print(N-tmp)
elif coprime2(C, D):
    tmp = 0   #最後にNから引く
    mod = A % C
    tmp += math.ceil((N-mod)/C)
    mod = A % D
    tmp += math.ceil((N-mod)/D)
    mod = A % (D*C)
    tmp -= math.ceil((N-mod)/(D*C))
    print(N-tmp)
else:
    tmp = 0   #最後にNから引く
    mod = A % min(C, D)
    tmp += math.ceil((N-mod)/min(C, D))
    print(N-tmp)

### FIXED CODE ###

import math
import fractions
A, B, C, D = map(int, input().split())
g = int(C*D/fractions.gcd(C,D))
N = B - A + 1
E = B - B//C  - B//D + B//g
F = A-1 - (A-1)//C - (A-1)//D + (A-1)//g
print(int(E-F))
#ABC_131_C
import math

A,B,C,D=list(map(int,input().split()))


def f(A,B,X):
    if A%X==0 or B%X==0:
        X_num=1+(B-A)//X
    else:
        X_num=(B-A)//X
    return X_num


C_num=f(A,B,C)
D_num=f(A,B,D)

CD_m=C*D//math.gcd(C,D)

CD_num=f(A,B,CD_m)

ans=(B-A+1)-C_num-D_num+CD_num
print(ans)

### FIXED CODE ###

#ABC_131_C
import fractions
A,B,C,D=list(map(int,input().split()))
#B以下の答え
CD_lcm=C*D//fractions.gcd(C,D)

underB=B-B//C-B//D+B//CD_lcm
underA_1=A-1-(A-1)//C-(A-1)//D+(A-1)//CD_lcm

print(underB-underA_1)
M = int(input())
if M <= 399:
    pass
elif 400 <= M and M <= 599:
    print("8")
elif M <= 799:
    print("7")
elif M <= 999:
    print("6")
elif M <= 1199:
    print("5")
elif M <= 1399:
    print("4")1
elif M <= 1599:
    print("3")
elif M <= 1799:
    print("2")
elif M <= 1999:
    print("1")

### FIXED CODE ###

M = int(input())
if M <= 399:
    pass
elif 400 <= M and M <= 599:
    print("8")
elif M <= 799:
    print("7")
elif M <= 999:
    print("6")
elif M <= 1199:
    print("5")
elif M <= 1399:
    print("4")
elif M <= 1599:
    print("3")
elif M <= 1799:
    print("2")
elif M <= 1999:
    print("1")
h,w=map(int,input().split())
n=int(input())
a=list(map(int,input().split()))
colors=[]
for i in range(n):
    for _ in range(a[i]):
        colors.append(i+1)
ans=[[0 for _ in range(w)] for _ in range(h)]
temp=0
for i in range(h):
    for j in range(w):
        if i%2!=0:
            j = w-j-1
        ans[i][j]=colors[temp]
        temp+=1

for i in range(h):
    for j in range(w):
        print(ans[i][j], end="")
    print()

### FIXED CODE ###

n = int(input())
a=list(map(int,input().split()))
cnt,cnt2,cnt4=0,0,0
for val in a:
    if val%4==0:
        cnt4+=1
    elif val%2==0:
        cnt2+=1
    else:
        cnt+=1
if cnt2==n: print("Yes")
elif cnt2==0:
    if cnt4>=cnt-1: print("Yes")
    else: print("No")
else:
    if cnt4>=cnt: print("Yes")
    else: print("No")
d, t, s = map(int, inport().split())

if t*s <= d:
  print("yes")
else:
  print("No")

### FIXED CODE ###

d, t, s = map(int, input().split())

if d/s <= t:
  print("Yes")
else:
  print("No")
S = input()
T = input()
# S = "cd"
# T = "abc"
sS = "".join(sorted(S))
sT = "".join(sorted(T, reverse = True))
if (sS < sT):
  print("Yes")
  else:
    print("No")


### FIXED CODE ###

S = input()
T = input()
# S = "cd"
# T = "abc"
sS = "".join(sorted(S))
sT = "".join(sorted(T, reverse = True))
if (sS < sT):
	print("Yes")
else:
	print("No")
x,n=map(int,input().split())
S=map(int, input().split())
K=(list(range(1,101)))
for i in S:
    K.remove(i)
L=[]
for i in K:
    L.append(abs(x-i))
m=min(L)
ind_m=L.index(m)
print(K[ind_m])

### FIXED CODE ###

x,n=map(int,input().split())
S=map(int, input().split())
K=(list(range(0,102)))
for i in S:
    K.remove(i)
L=[]
for i in K:
    L.append(abs(x-i))
m=min(L)
ind_m=L.index(m)
print(K[ind_m])
monster, skill = map(int,input().split())

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

sorted_monster_hp = monster_hp.sort()

attack_count = 0

while(skill>0):
    skill -= 1
    sorted_monster_hp.pop(-1)

for hp in sorted_monster_hp:
    attack_count += hp

print(hp)

### FIXED CODE ###

monster, skill = map(int,input().split())

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

monster_hp.sort()

attack_count = 0

while(skill>0):
    skill -= 1
    if len(monster_hp) > 0:    
        monster_hp.pop(-1)
    

for hp in monster_hp:
    attack_count += hp

print(attack_count)
s = input()
t = input()
s1 = []
t1 = []
for i in range(0 , n):
  s1.append(s[i])
for i in range(0 , n):
  t1.append(t[i])
a = set(s1 + t1)
print(len(a))

### FIXED CODE ###

n = int(input())
s = input()
t = input()
answer = n
for i in range (n + 1) :
  newstring = s[0:i] + t[:n]
  if newstring[0:n] == s:
    answer += i
    break
print (answer)
import math


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

minimum = x[0]
for i in range(len(x)):
    x[i] = x[i] - X
    minimum = min(x[i], minimum)
# print(x, minimum)

gcd_value = math.gcd(x[0], x[0])
for i in range(len(x)):
    gcd_value = math.gcd(gcd_value, x[i])
    # print(gcd)
print(gcd_value)


### FIXED CODE ###

import fractions

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

minimum = x[0]
for i in range(len(x)):
    x[i] = x[i] - X
    minimum = min(x[i], minimum)
# print(x, minimum)

gcd_value = fractions.gcd(x[0], x[0])
for i in range(len(x)):
    gcd_value = abs(fractions.gcd(gcd_value, x[i]))
    # print(gcd)
print(gcd_value)
A,B= map(int, input().split(" "))
S=input()
if S[3]=="-" and len(S)==A+B+1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

# Your code here!
A,B= map(int, input().split(" "))
S=input()
n=S.count("-")
if S[A]=="-" and len(S)==A+B+1 and n==1:
    print("Yes")
else:
    print("No")
n=int(input)
tako=list(map(int,input().split()))
ans=0
for i in range(n):
    for j in range(1,n+1):
        ans+=tako[i]*tako[j]
print(ans)


### FIXED CODE ###

n=int(input())
tako=list(map(int,input().split()))
ans=0
for i in range(n-1):
    for j in range(1,n):
        if not j<=i:
            
          
            ans+=tako[i]*tako[j]
print(ans)
import sys
from collections import deque, OrderedDict
inputs = sys.stdin.readlines()

n = int(inputs[0])
edges = [tuple(map(int, x.split())) for x in inputs[1:]]

tree, colors = [[] for _ in range(n)], OrderedDict()
for x, y in edges:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)
    colors[(x-1, y-1)] = 0
use_color = max(len(x) for x in tree)

queue, passed = deque([0]), set()
while queue:
    x = queue.popleft()
    passed.add(x)
    pallet = [i for i in range(use_color)][::-1]
    for y in tree[x]:
        if y in passed:
            if (x, y) in colors:
                pallet.remove(colors[(x, y)])
            elif (y, x) in colors:
                pallet.remove(colors[(y, x)])
            continue
        if (x, y) in colors:
            colors[(x, y)] = pallet.pop()
        elif (y, x) in colors:
            colors[(y, x)] = pallet.pop()
        queue.append(y)

print(use_color)
for c in colors.values():
    print(c+1)

### FIXED CODE ###

from collections import deque
 
N, *AB = map(int, open(0).read().split())
B = AB[1::2]
 
E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
#def pscl(num,l=[1]):
#    for i in range(num):
#        l = map(lambda x,y:x+y,[0]+l,l+[0])
#    return l

# "!/usr/bin/env pypy3
# pscl 要修正
#n=int(input())

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(n):
    l[i*n].add(s[i]])
for i in range(m):
    l[i*m].add(t[i]])
for i in range(l):
    if len(l[i])==2: f=-1
print(f)


### FIXED CODE ###

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d={}
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n and o not in d:
        d[o]=s[i]
    elif i<n and o in d and d[o]!=s[i]:
        f=-1
    if i<m and p not in d:
        d[p]=t[i]
    elif i<m and p in d and d[p]!=t[i]:
        f=-1
print(f)
n = int(input())
s1 = input()
s2 = input()

mod = 10**9 + 7

# dp[i][j] : i番目まで見たときに、i番目の要素が j = 0 だと縦に、
# j = 1 だと横にブロックが並んでいた時の色の塗りかた (mod 10**9+7)
dp = [[0 for j in range(2)] for i in range(n+1)]

if s1[0] == s2[0]:
    dp[1][0] = 3
    i = 1
else:
    dp[2][1] = 3 * 2
    i = 2
while i < n:
    if s1[i] == s2[i]:
        if s1[i+1] == s2[i+1]:
            dp[i+1][0] = dp[i][0] * 2
            i += 1
        else:
            dp[i+2][1] = dp[i][0] * 2
            i += 2
    else:
        if s1[i+2] == s2[i+2]:
            dp[i+2][0] = dp[i][1]
            i += 2
        else:
            dp[i+3][1] = dp[i][1] * 2
            i += 3

print(dp[n][0] + dp[n][1])

### FIXED CODE ###

n = int(input())
s1 = input()
s2 = input()

mod = 10**9 + 7

# dp[i][j] : i番目まで見たときに、i番目の要素が j = 0 だと縦に、
# j = 1 だと横にブロックが並んでいた時の色の塗りかた (mod 10**9+7)
dp = [[0 for j in range(2)] for i in range(n+1)]

if s1[0] == s2[0]:
    dp[0][0] = 3
    i = 0
else:
    dp[1][1] = 3 * 2
    i = 1
while i < n - 1:
    if s1[i] == s2[i]:
        if s1[i+1] == s2[i+1]:
            dp[i+1][0] = dp[i][0] * 2 % mod
            i += 1
        else:
            dp[i+2][1] = dp[i][0] * 2 % mod
            i += 2
    else:
        if s1[i+1] == s2[i+1]:
            dp[i+1][0] = dp[i][1] % mod
            i += 1
        else:
            dp[i+2][1] = dp[i][1] * 3 % mod
            i += 2

print((dp[n-1][0] % mod + dp[n-1][1] % mod) % mod)