Harryxun/stf_run huggingface dataset:
def dfs(i, d):
    # print(i, d)
    for j, w in node_array[i]:
        if color_array[j] == -1:
            color_array[j] = (d + w) % 2
            dfs(j, d + w)


N = int(input())
node_array = [[] for i in range(N)]
color_array = [-1] * N

for _ in range(N - 1):
    i, j, w = map(int, input().split())
    node_array[i - 1].append((j - 1, w))
    node_array[j - 1].append((i - 1, w))

color_array[0] = 0
dfs(0, 0)

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


### FIXED CODE ###

N = int(input())
node_array = [list(map(int, input().split())) for i in range(N - 1)]
# print(node_array)
tree_num_array = [-1] * N
# print(tree_num_array)

tree_num_max = -1
tree = {}
last_tree_num = -1
for node in node_array:
    # print(tree)
    i, j, w = node
    i = i - 1
    j = j - 1
    if tree_num_array[i] == -1 and tree_num_array[j] == -1:
        # print(i, j, "added")
        tree_num_max += 1
        tree[tree_num_max] = {i: 0, j: w}
        tree_num_array[i] = tree_num_max
        tree_num_array[j] = tree_num_max
        last_tree_num = tree_num_max
        continue
    elif tree_num_array[i] == -1:
        # print(i, "added")
        tree_num_added = tree_num_array[j]
        tree[tree_num_added][i] = tree[tree_num_added][j] + w
        tree_num_array[i] = tree_num_added
        last_tree_num = tree_num_added
    elif tree_num_array[j] == -1:
        # print(j, "added")
        tree_num_added = tree_num_array[i]
        tree[tree_num_added][j] = tree[tree_num_added][i] + w
        tree_num_array[j] = tree_num_added
        last_tree_num = tree_num_added
    else:
        tree_num_i = tree_num_array[i]
        tree_num_j = tree_num_array[j]
        # print(tree_num_i, tree_num_j, "unite")
        if len(tree[tree_num_i]) > len(tree[tree_num_j]):
            tree_main_num = tree_num_i
            tree_main_value = tree[tree_main_num][i]
            tree_sub_num = tree_num_j
            tree_sub_value = tree[tree_sub_num][j]
        else:
            tree_main_num = tree_num_j
            tree_main_value = tree[tree_main_num][j]
            tree_sub_num = tree_num_i
            tree_sub_value = tree[tree_sub_num][i]

        for key, value in tree[tree_sub_num].items():
            tree[tree_main_num][
                key] = tree_main_value + w + abs(value - tree_sub_value)
            tree_num_array[int(key)] = tree_main_num
        last_tree_num = tree_main_num
# print(tree)
ans_dict = sorted(tree[last_tree_num].items(), key=lambda x: int(x[0]))
# print(ans_dict)
for distance in ans_dict:
    print(distance[1] % 2)
N, K = [int(i) for i in input().split()]
P = [int(i) for i in input().split()]

# 期待値
def func_d(n):
    if n == 1:
        return 1
    else:
        return n + func_d(n-1)

AA = []
for i in P:
    AA.append(func_d(i)/i)

# 累積和
A = [0]
for i in range(0, N):
    A.append(AA[i]+A[i])

ans = []
for i in range(K, N+1):
    ans.append(A[i] - A[i-K])
    
print(max(ans))

### FIXED CODE ###

def func(x):
    return (x+1)/2
N, K = [int(i) for i in input().split()]
P = [func(int(i)) for i in input().split()]

# 累積和
A = [0]
for i in P:
    A.append(A[-1]+i)

ans = []
for i in range(K, N+1):
    ans.append(A[i] - A[i-K])
    
print(max(ans))
N = int(input())
ABCDE = [int(input()) for i in range(5)]
ans = N//mi+5
print(ans)

### FIXED CODE ###

N = int(input())
ABCDE = [int(input()) for i in range(5)]
mi = min(ABCDE)
if N%mi!=0:
    ans = N//mi+5
else:
    ans = N//mi+4
print(ans)
nums = input()
print(sum(nums) - sum(set(nums)))

### FIXED CODE ###

nums = map(int, input().split())
d = {}
for n in nums:
  d.setdefault(n, 0)
  d[n] += 1
print(list(d.keys())[list(d.values()).index(1)])
a, b, c = map(int, input().split())
m = c - a - b

if m <= 0:
 　print('No')

else:
  X = ((c - a - b)^2) - (4 * a * b)
  if X > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

a, b, c = map(int, input().split())
m = c - a - b

if m <= 0:
  print('No')

else:
  X = (m * m) - (4 * a * b)
  if X > 0:
    print('Yes')
  else:
    print('No')
L,R= map(int,input().split())
#境界条件
bool = True
l = L % 2019
r = R % 2019
# if L == R:
#     ans = L * R %2019
# if l >= r:
#     r += 2019

for i in range(l,r):
    for j in range(i+1,r+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
print(ans)

### FIXED CODE ###

L,R= map(int,input().split())
#境界条件
bool = True
flag = False
for i in range(L,R):
    for j in range(i+1,R+1):
        temp = (i * j) % 2019
        if bool:
            min = temp
            ans = min
            bool = False
        elif min > temp:
            min = temp
            ans = min
        if min == 0:
            flag = True
            break
    if flag:
        break
print(ans)
n,m = map(int,input().split( ))
ls_a = []
ls_b = [[] for i in range(n)]
for i in range(M):
    p,y = map(int,input().split( ))
    ls_a.append([p,y])
    ls_b[p-1].append(y)
for i in range(n):
    ls_b[i].sort()
for i in range(m):
    print(str(ls_a[i][0]).zfill(6) + str(ls_b[ls_a[i][0]-1].index(ls_a[i][1])+1).zfill(6))

### FIXED CODE ###

N,M=map(int,input().split())
PY=[list(map(int,input().split()))+[i] for i in range(M)] #定義終了
 
PY.sort(key= lambda x:x[1])
num=[0]*N
w=[""]*M
 
for p,y,i in PY:
	num[p-1]+=1
	w[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for i in range(M):
  	print(w[i])
N, K = map(int, input().split())
S = input()
L = [0]
prev = S[0]
num = 1
for s in S[1:]:
    if s == prev:
        num += 1
    else:
        L.append(num)
        num = 1
        prev = s
L.append(num)
# print(L)
for i in range(1, len(L)):
    L[i] += L[i - 1]
# print(L)
left = 0
if S[0] == "1":
    right = min(2 * K + 1, len(L) - 1)
else:
    right = min(2 * K, len(L) - 1)
num = 0
while right < len(L):
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
    if left == 0 and S[0] == "0":
        left += 1
    else:
        left += 2
    right += 2
if S[-1] == "0":
    right -= 1
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
print(num)


### FIXED CODE ###

N, K = map(int, input().split())
S = input()
if S == "0":
    print(1)
    exit()
if S.count("0") == N:
    print(N)
    exit()
L = [0]
prev = S[0]
num = 1
for s in S[1:]:
    if s == prev:
        num += 1
    else:
        L.append(num)
        num = 1
        prev = s
L.append(num)
# print(L)
for i in range(1, len(L)):
    L[i] += L[i - 1]
# print(L)
left = 0
if S[0] == "1":
    right = min(2 * K + 1, len(L) - 1)
else:
    right = min(2 * K, len(L) - 1)
num = 0
while right < len(L):
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
    if left == 0 and S[0] == "0":
        left += 1
    else:
        left += 2
    right += 2
if S[-1] == "0":
    right -= 1
    # print("L[" + str(right) + "] - L[" + str(left) + "] = " + str(L[right] - L[left]))
    num = max(num, L[right] - L[left])
print(num)
A,B,K = map(int,input().split())

a = []

if K == 1:
    print(K)
    exit()

for i in range(1,100):
    if A%i == 0 and B%i == 0:
        a.append(i)
if 
print(a[-K])

### FIXED CODE ###

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

a = []

for i in range(1,100000):
    if A%i == 0 and B%i == 0:
        a.append(i)

print(a[-K])
from collections import Counter

N = int(input())
edges = [[] for _ in range(N)]

for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

C = Counter(map(int, input().split()))

def dfs(now, pr, prev):
    ret = 0
    for to in edges:
        if to == pr:
            continue
        for c, n in C.items():
            if n == 0:
                continue
            C[c] -= 1
            ret = max(ret, dfs(to, now, c) + min(prev, c))
            C[c] += 1
    return ret

print(dfs(0, -1, 0))


### FIXED CODE ###

from collections import deque

N = int(input())

edges = [[] for _ in range(N)]
edgeList = []
for _ in range(N - 1):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)
    edgeList.append((fr, to))

C = list(map(int, input().split()))
C.sort()

M = sum(C) - C[-1]

values = [-1] * N
que = deque([0])

while que:
    now = que.popleft()
    values[now] = C.pop()
    for to in edges[now]:
        if values[to] == -1:
            que.append(to)

print(M)
print(*values)
N, A, B, C, D = map(int, input().split())
S = input()

AtoC = True
BtoD = True
replace = False

for n in list(range(A-1,C)):
    if S[n] =='#' and S[n+1] =='#':
        AtoC = False
        
for n in list(range(B-1,D)):
    if S[n] =='#' and S[n+1] == '#':
        BtoD = False
        
for n in list(range(B-2,D-1)):
    if S[n] =='.' and S[n+1] == '.' and S[n+2] == '.':
        replace = True
if C<D:
    if AtoC == True and BtoD == True:
        print('Yes')
    else:
        print('No')
else:
    if AtoC == True and BtoD == True and replace == True:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

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

AtoC = True
BtoD = True
replace = False

for n in list(range(A-1,C)):
    if S[n] =='#' and S[n+1] =='#':
        AtoC = False
        
for n in list(range(B-1,D)):
    if S[n] =='#' and S[n+1] == '#':
        BtoD = False
        
if C<D:
    if AtoC == True and BtoD == True:
        print('Yes')
    else:
        print('No')
else:
    for n in list(range(B-2,D-1)):
        if S[n] =='.' and S[n+1] == '.' and S[n+2] == '.':
            replace = True
    if AtoC == True and BtoD == True and replace == True:
        print('Yes')
    else:
        print('No')
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
a = 0
b = 0
k = 0

for i in itertools.permutations(range(1,n+1)):
    k += 1
    if i == p:
        a = k
    if i == q:
        b = k
ans = abs(a-b)
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
a = 0
b = 0
k = 0

for i in itertools.permutations(range(1,n+1)):
    k += 1
    if i == p:
        a = k
    if i == q:
        b = k
ans = abs(a-b)
print(ans)
N, M = map(int, input())
if N == M:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N, M = map(int, input().split())
if N == M:
    print('Yes')
else:
    print('No')
def fragOptimalJump(h,n):
    dp=[0]*(n+1)
    dp[2]=abs(h[1]-h[2])
    for i in range(3,n+1):
        min=10000
        p=1
        j=1
        while j<i:
            d=dp[j]+abs(h[i]-h[j])
            if d<min:
                min=d
            p=p*2
            j=p
            
        dp[i]=min
    return dp[n]

N=int(input())
H=[0]*(N+1)
read = [int(n) for n in input().split()]
H=[0]+read
print(H)
H=[0,1,2,3,4]
print(fragOptimalJump(H,4))

### FIXED CODE ###

def fragOptimalJump(h,n,k):
    dp=[0]*(n+1)
    dp[2]=abs(h[1]-h[2])
    for i in range(3,n+1):
        l=i-k
        if l<0:
            l=1
        min=10000000000
        for j in range(l,i):
            d=dp[j]+abs(h[i]-h[j])
            if d<min:
                min=d
            
        dp[i]=min
    return dp[n]



N,k=input().split()
N,k=int(N),int(k)
H=[0]*(N+1)
read = [int(n) for n in input().split()]
H=[0]+read
print(fragOptimalJump(H,N,k))
import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k <= b[-1] and k >= b[0]:
			x = bisect.bisect_left(b,k)
			if x >= 0 and x < len(b):
				if b[x] == k:
					ans -= 1
		if m <= b[-1] and m >= b[0]:
			x = bisect.bisect_left(b,m)
			if x >= 0 and x < len(b):
				if b[x] == m:
					ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			x = bisect.bisect_left(b,l)
			if x >= 0 and x < len(b):
				if b[x] == l:
					ans -= 1
print (ans)

### FIXED CODE ###

import bisect
n = int(input())
s = input()
r = []
g = []
b = []
for i in range(n):
	if s[i] == "R":
		r.append(i+1)
	elif s[i] == "G":
		g.append(i+1)
	else:
		b.append(i+1)
ans = 0
if len(r) == 0 or len(g) == 0 or len(b) == 0:
	print (0)
	exit()
for i in r:
	for j in g:
		ans += len(b)
		if i > j:
			k = j-abs(i-j)
			m = i+abs(i-j)
		else:
			k = j+abs(i-j)
			m = i-abs(i-j)
		if k <= b[-1] and k >= b[0]:
			x = bisect.bisect_left(b,k)
			if x >= 0 and x < len(b):
				if b[x] == k:
					ans -= 1
		if m <= b[-1] and m >= b[0]:
			x = bisect.bisect_left(b,m)
			if x >= 0 and x < len(b):
				if b[x] == m:
					ans -= 1
		l = (i+j)//2
		if abs(i-l) == abs(j-l):
			x = bisect.bisect_left(b,l)
			if x >= 0 and x < len(b):
				if b[x] == l:
					ans -= 1
print (ans)
N = int(input())
L = [ int(input()) for i in range(N)]

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

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

x = L[0]
for i in range(len(L)-1):
    y = lcm(x, L[i+1])
    x = y
    
print(int(x))

### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

x = L[0]
for i in range(len(L)-1):
    y = lcm(x, L[i+1])
    x = y
    
print(x)
if(input() == "ABC"):
  return "ARC"

else:
  return "ABC"

### FIXED CODE ###

s = input()

if(s == 'ABC'):
  print("ARC")

else:
  print("ABC")
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

def gcd(a, b):
    while b != 0:
        a, b = b, a % b

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    a, b = a // gcd(a, b), b // gcd(a, b)
    if a == b == 0:
        zeros += 1
        continue

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    if b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    if a < 0 or b < 0:
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += zeros
print(ans)


### FIXED CODE ###

import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())

d = {}
zeros = 0

def gcd(a, b):
    while b != 0:
        a, b = b, a % b

    return a

MOD = int(1e9) + 7
p = [1] * (N + 1)
for i in range(N):
    p[i + 1] = p[i] * 2 % MOD
    a, b = map(int, input().split())
    if a == b == 0:
        zeros += 1
        continue
    a, b = a // abs(gcd(a, b)), b // abs(gcd(a, b))

    if a == 0:
        f, s = d.get((a, abs(b)), (0, 0))
        d[(a, abs(b))] = (f + 1, s)

    elif b == 0:
        f, s = d.get((b, abs(a)), (0, 0))
        d[(b, abs(a))] = (f, s + 1)

    elif (a < 0) ^ (b < 0):
        if a < 0:
            a, b = -a, -b
        f, s = d.get((abs(b), a), (0, 0))
        d[(abs(b), a)] = (f, s + 1)
    else:
        f, s = d.get((abs(a), abs(b)), (0, 0))
        d[(abs(a), abs(b))] = (f + 1, s)

ans = 1
for _, (f, s) in d.items():
    cnt = p[f] - 1
    cnt += p[s] - 1
    cnt += 1
    cnt %= MOD
    ans *= cnt
    ans %= MOD

ans -= 1
ans += MOD
ans += zeros
ans %= MOD
print(ans)
N=int(input())
d+=list(map(int,input().split()))
s=0
for j in range(N-1):
  for i in range(j+1,N):
    s+=d[j]*d[i]
print(s)

### FIXED CODE ###

N=int(input())
d=list(map(int,input().split()))
s=0
for j in range(N-1):
  for i in range(j+1,N):
    s+=d[j]*d[i]
print(s)
n = int(input())
lst_take = []
max_val = 100000
used = []
for i in range(1,15):
  if 6 ** i <=  max_val:
    lst_take.append(6**i)
  if 9 ** i <= max_val:
    lst_take.append(9**i)  
lst_take = sorted(set(lst_take), reverse=True)
while True:
  if n==0:
    break
    
  flag = True
  for i in lst_take:
    if i <= n and i not in used:
      n -= i
      count += 1
      used.append(i)
      flag = False
      break
  if flag:
    count += n
    break
print(count)

### FIXED CODE ###

N=int(input())
ans=N
for i in range(N+1):
    cnt=0
    t=i
    while t>0:
        cnt+=t%6
        t//=6
    j=N-i
    while j>0:
        cnt+=j%9
        j//=9
    ans = min(ans,cnt)
print(ans)
a,b=map(int(),input.split())
if a>9 or b>9 :
  print(-1)
else:
  print(a*b)

### FIXED CODE ###

a,b=map(int,input().split())
if a>9 or b>9 :
    print(-1)
else:
    print(a*b)
import math
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
if a >= 100:
    a1 = a % 10
else:
    a2 = a - 100
    a1 = a2 % 10
if b >= 100:
    b1 = b % 10
else:
    b2 = b - 100
    b1 = b2 % 10
if c >= 100:
    c1 = c % 10
else:
    c2 = c - 100
    c1 = c2 % 10
if d >= 100:
    d1 = d % 10
else:
    d2 = d - 100
    d1 = d2 % 10
if e >= 100:
    e1 = e % 10
else:
    e2 = e - 100
    e1 = e2 % 10
if a1 == 0:
    a1 = 9
if b1 == 0:
    b1 = 9
if c1 == 0:
    c1 = 9
if d1 == 0:
    a1 = 9
if e1 == 0:
    e1 = 9
lis = [a1,b1,c1,d1,e1]
if a1 == min(lis) :
    answer = math.ceil(b / 10) * 10 + math.ceil(c/ 10) * 10 + math.ceil(e/ 10* 10+ math.ceil(d/ 10 * 10 + a
if b1 == min(lis):
    answer = math.ceil(a/ 10)* 10 + math.ceil(c/ 10)* 10 + math.ceil(e/ 10)* 10 + math.ceil(d/ 10)* 10 + b
if c1 == min(lis):
    answer = math.ceil(b/ 10)* 10 + math.ceil(a/ 10)* 10 + math.ceil(e/ 10)* 10 + math.ceil(d/ 10)* 10 + c
if d1 == min(lis):
    answer = math.ceil(b/ 10)* 10 + math.ceil(c/ 10)* 10 + math.ceil(e/ 10)* 10 + math.ceil(a/ 10)* 10 + d
if e1 == min(lis):
    answer = math.ceil(b/ 10)* 10 + math.ceil(c/ 10)* 10 + math.ceil(e/ 10)* 10 + math.ceil(a/ 10)* 10 + e
print(answer)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
k = int(input())
k1 = e - a
if k >= k1:
    print("Yay!")
else:
    print(":(")
n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * n
D[0], D[1] = 1, 1
for _ in range(m):
    D[int(input())] = -1
for i in range(2, n):
    if D[i] == -1:
        continue
    if D[i-1] != -1:
        D[i] += D[i-1]
    if D[i-2] != -1:
        D[i] += D[i-2]
    D[i]%=MOD
ans = 0
if D[n-1] != -1:
    ans += D[n-1]
if D[n-2] != -1:
    ans += D[n-2]
print(ans % MOD)

### FIXED CODE ###

n,m=map(int,input().split())
MOD = 1000000007 
D=[0] * (n+2)
D[0] = 1
for _ in range(m):
    D[int(input())] = -1
for i in range(n):
    if D[i] == -1:
        continue
    if D[i+1] != -1:
        D[i+1] += D[i]
    if D[i+2] != -1:
        D[i+2] += D[i]
    D[i]%=MOD
print(D[n] % MOD)
N=input()
d=list(map(int, input().strip().split()))
ans=0

for i in range(int(max(d)+1)):
    ABC=0
    ARC=0
    for j in range(int(N)):

        if d[j]<i:
            ABC+=1
        else:
            ARC+=1

    if ARC==ABC:
        ans+=1

print(ans)


### FIXED CODE ###

S = input()


list_S=list(S)

if list_S[0]==list_S[1] and list_S[2]==list_S[3] and list_S[0] != list_S[2]:
    print("Yes")
elif list_S[0]==list_S[2] and list_S[1]==list_S[3] and list_S[0] != list_S[1]:
    print("Yes")
elif list_S[0]==list_S[3] and list_S[1]==list_S[2] and list_S[0] != list_S[1]:
    print("Yes")
else:
    print("No")
i=input;print'Hello World'*(i()-1)or i()+i()

### FIXED CODE ###

*a,=map(int,open(0).read().split())
print(a[1]+a[2]if a[0]>1else'Hello World')
import collections
s = input()


cnt = collections.Counter(s)
used = set(cnt.keys())
c = -1
if len(used) < 26:
    for i in range(26):
        if not chr(i+ord("a")) in used:
            c = chr(i+ord("a"))
            break
if c != -1:
    print(s+c)
else:
    i = 25
    while s[i-1] > s[i]:
        i -= 1
        lused = sorted(s[i-1:])
        print(s[:i-1]+lused[lused.index(s[i-1])+1])
        break
    else:
        print("-1")


### FIXED CODE ###

import collections
s = input()


cnt = collections.Counter(s)
used = set(cnt.keys())
c = -1
if len(used) < 26:
    for i in range(26):
        if not chr(i+ord("a")) in used:
            c = chr(i+ord("a"))
            break
if c != -1:
    print(s+c)
else:
    if s == "zyxwvutsrqponmlkjihgfedcba":
        print("-1")
        exit()
    i = 25
    while i > 1 and s[i-1] > s[i]:
        i -= 1
    lused = sorted(s[i-1:])
    print(s[:i-1]+lused[lused.index(s[i-1])+1])
import copy

def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]

print(sum(dp_list)%mod)


### FIXED CODE ###

import copy
def acgt_2(t):
    w = ["A","C","G","T"]
    string_list = []
    for i in range(4):
        a = t // (4**(3-i))
        t = t % (4**(3-i))
        s = w[a]
        string_list.append(s)
    
    def acgt_sw(inst,a,b):
        st = copy.deepcopy(inst)
        st[a], st[b] = st[b], st[a]
        return "".join(st)

    
    string_list_2 = ["".join(string_list)] + [acgt_sw(string_list,i,i+1) for i in range(3)] 
    judge = False
    for i in string_list_2:

        if i[:3] == "AGC":
            judge = True

        if i[1:] == "AGC":
            judge = True

    return judge, "".join(string_list)
        

mod = 10**9+7
ng_list = []
for i in range(256):
    if acgt_2(i)[0]:
        ng_list.append(i)



n = int(input())
if n == 3:
    ans = 61
else:
    dp_list = [ 1 for i in range(4**4) ]
    for i in ng_list:
        dp_list[i] = 0

    for i in range(n-4):
        new_dp_list = [ 0 for i in range(4**4) ]
        for j in range(4**4):
            base = dp_list[j]
            new_index = [ 4*(j % 64) + k for k in range(4) ]
            for k in new_index:
                new_dp_list[k] += base
        for j in ng_list:
            new_dp_list[j] = 0
            dp_list = [ i%mod for i in new_dp_list]
    ans = sum(dp_list)%mod

print(ans)