Harryxun/stf_run huggingface dataset:
from typing import List


L = 40

def get_binary_str(n: int) -> str:
    binary = bin(n)[2:]
    padding_length = L - len(binary)
    return '0' * padding_length + binary

def get_first_one_pos(s: str) -> int:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return i

def xor(x: int, y: int) -> int:
    if x == y:
        return 0
    else:
        return 1

def calc_xor(i: int, x: int, binary_As: List[List[str]]) -> int:
    ret = 0
    for binary_A in binary_As:
        ret += xor(x, int(binary_A[i]))
    return ret


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

binary_As = [get_binary_str(A) for A in As]
binary_K = get_binary_str(K)
one_pos = get_first_one_pos(binary_K)

i = 0
ret = 0
while i < one_pos:
    ret += calc_xor(i, 0, binary_As) * 2**(L-i-1)
    i += 1

while i < L:
    a = calc_xor(i, 0, binary_As)
    b = calc_xor(i, 1, binary_As)
    ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
    i += 1

print(ret)

### FIXED CODE ###

L = 50

def get_binary_str(n: int) -> str:
    binary = bin(n)[2:]
    padding_length = L - len(binary)
    return '0' * padding_length + binary

def get_first_one_pos(s: str) -> int:
    i = 0
    while i < len(s) and s[i] == '0':
        i += 1
    return i

def xor(x: int, y: int) -> int:
    if x == y:
        return 0
    else:
        return 1

def calc_xor(i: int, x: int, binary_As) -> int:
    ret = 0
    for binary_A in binary_As:
        ret += xor(x, int(binary_A[i]))
    return ret


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

binary_As = [get_binary_str(A) for A in As]
binary_K = get_binary_str(K)
one_pos = get_first_one_pos(binary_K)

i = 0
ret = 0
while i < one_pos:
    ret += calc_xor(i, 0, binary_As) * 2**(L-i-1)
    i += 1

flag = False
while i < L:
    a = calc_xor(i, 0, binary_As)
    b = N - a
    if flag:
        ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
    else:
        if binary_K[i] == '1':
            if a > b:
                flag = True
            ret += a * 2**(L-i-1) if a > b else b * 2**(L-i-1)
        else:
            ret += a * 2**(L-i-1)

    i += 1

print(ret)
"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d = map(int, readline().split())
print(min(a, b) + min(c + d))


### FIXED CODE ###

"""
author : halo2halo
date : 24, Jan, 2020
"""

import sys

# import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

a, b, c, d = map(int, read().split())
print(min(a, b) + min(c,d))
import sys
N,Q = map(int,sys.stdin.readline().rstrip().split())
S = sys.stdin.readline().rstrip()
for _ in range(Q):
  l,r  = map(int,sys.stdin.readline().rstrip().split())
  print(S[l-1:r].count("AC"))
  del l
  del r

### FIXED CODE ###

star = {"A":"T",
        "T":"A",
        "C":"G",
        "G":"C"}
print(star[input()])
s = input()

for i in range(len(s)):
    print("x", end=""aa)

### FIXED CODE ###

s = input()

for i in range(len(s)):
    print("x", end="")
N,M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

out=0
for i in range(0,N,1):
  if i in A:
    continue
  if i==N:
    out+=1
  for j in range(i,N,2):
    if j in A:
      continue
    if j==N:
      out+=1
  
print(out%1000000007)

### FIXED CODE ###

import sys
mod = 10**9+7

def main():
    n, m = map(int, input().split(' '))
    if m > 0:
        aaa = set(map(int, sys.stdin))
    else:
        aaa = set()
 
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if 1 not in aaa else 0
    
    for i in range(2, n+1):
        if i in aaa:
            continue
        dp[i] = (dp[i-1]+dp[i-2])%mod
 
    print(dp[n])
 
main()
def get_max(n):
    if n==1:
        return 0
    if n % 2 == 0:
        return (n/2+(n-1))*n/2/2-1 + get_max((n-1)/2)
    else:
        return ((n-1)/2+(n-1))*(n+1)/2/2 + get_max((n-1)/2)

def main():
    N = int(input())
    print(int(get_max(N)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    print(int((N*(N-1))//2))

if __name__ == '__main__':
    main()
N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])

### FIXED CODE ###


# 桁DP問題
N = int(input())
K = int(input())

dp = [[[0,0] for _ in range(4)] for _ in range(101)]

dp[0][0][0] = 1

# i = Nの●桁目
# j = 0以外の数字を何回利用しているか
# k == 0 Nを超えないように注意が必要
# k == 1 N以下が保証されている

keta = len(str(N))
for i in range(keta):
  for j in range(4):
    for k in range(2):
      num = int(str(N)[i])

      for n in range(10):
        ni, nj, nk = i+1, j, k

        if n != 0:
          nj += 1 # 0以外の数字を利用した数が増えた
        if nj > K: 
          continue # すでにKを使い切っているときはカウントしない
        if k == 0:
          if n > num:
            continue # Nを超えているので飛ばす
          if n < num:
            nk = 1 # 何でもOK

        dp[ni][nj][nk] += dp[i][j][k]

print(dp[keta][K][0] + dp[keta][K][1])
S = list(input())
n = len(S)

def Remove(binList,lenList):
    for i in range(0,lenList-1):
        if (binList[i] == "0" and binList[i+1] == "1") or (binList[i] == "1" and binList[i+1] == "0"):
            del binList[i:i+2]
            return Remove(binList,lenList - 2)
    return binList
S = Remove(S,n)
print(n-len(S))

### FIXED CODE ###

S = list(input())
obj = min(S.count("0"),S.count("1"))
print(obj*2)
from math import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans)


### FIXED CODE ###

# from math import *
from fractions import *

def next_int():
    return int(input())

def next_ints():
    return list(map(int, input().split()))

a, b = next_ints()
n = gcd(a, b)
ans = 1
i = 2
while i*i <= n:
    if n%i == 0:
        ans += 1
        while n%i == 0:
            n //= i
    i += 1
if n != 1:
    ans += 1
print(ans)
line = input.split()
l = list(map(int, line))
a = l[0]
b = l[1]
c = l[2]

print (a)
print (b)
print (c)

### FIXED CODE ###

line = input().split()
l = list(map(int, line))
a = l[0]
b = l[1]
c = l[2]

if a == b and b == c:
    print (1)
elif ( a == b and b != c ) or (a != b and b == c) or (a == c and a != b):
    print (2)
else:
    print (3)
import math
tol = 1e-6
ans = 1
cur = [0,0]
cur[0] += math.cos(ans*math.pi/x)
cur[1] += math.sin(ans*math.pi/x)
while cur[0]**2 + cur[1]**2 > tol:
    ans += 1
    cur[0] += math.cos(ans*math.pi/x)
    cur[1] += math.sin(ans*math.pi/x)
print(ans)


### FIXED CODE ###

import math
x = int(input())
tol = 1e-6
ans = 1
cur = [0,1]
unit = x/180*math.pi
while cur[0]**2 + cur[1]**2 > tol:
    cur[0] += math.sin(ans*unit)
    cur[1] += math.cos(ans*unit)
    ans += 1
print(ans)
n = int(input())
a = list(map(int, input().split()))
a_joined = 0

for i in range(n):

	a_joined = a_joined | a[i]

print(len(bin(a_joined)) - 3)


### FIXED CODE ###

print(str(input()).count("1"))
n, a, b = list(map(int, input().split()))

sum = a+b

if n < a+b:

    if n < a :
        print(n)
    else:
        print(a)

else: 
    if n%sum > a: 
        print ((n // sum)*a) + a

    else:
        res = ((n // sum)*a) + (n % sum)
        print(res)


### FIXED CODE ###


n, a, b = list(map(int, input().split()))

sum = a+b

if n < a+b:

    if n < a :
        print(n)
    else:
        print(a)

else: 
    if n%sum > a: 
        print (((n // sum)*a) + a)

    else:
        res = ((n // sum)*a) + (n % sum)
        print(res)
n = int(input())
ans = int(input())
 
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a
 
def lcm(x,y):
    return (x*y//gcd(x,y))
 
for i in range(N-1):
    t = int(input())
    ans = lcm(ans,t)
print(ans)

### FIXED CODE ###

n = int(input())
ans = int(input())
 
def gcd(a,b):
    while b:
        a,b = b,a%b
    return a
 
def lcm(x,y):
    return (x*y//gcd(x,y))
 
for i in range(n-1):
    t = int(input())
    ans = lcm(ans,t)
print(ans)
import sys

import numpy as np

readline = sys.stdin.buffer.readline


# 同じ数値が複数あるとおかしくなる
def binary_search(A, n):
    n -= 1
    left = 0
    right = len(A)-1

    if n < A[0]:
        return -1
    else:
        while left < right:
            # if right - left == 1:
            #     break

            mid = (left + right) // 2
            if A[mid] < n:
                left = mid + 1
            elif n < A[mid]:
                right = mid - 1
            else:
                left = len(A) - mid + left
                break
        if A[left] > n:
            left -= 1

        return left


def main():
    N = int(readline())
    A = np.array(list(map(int, readline().split())))
    B = np.array(list(map(int, readline().split())))
    C = np.array(list(map(int, readline().split())))

    A, B, C = np.sort(A), np.sort(B), np.sort(C)

    aa = np.zeros([N], dtype=np.int32)
    for i, b in enumerate(B):
        aa[i] = binary_search(A, b) + 1

    bb = np.cumsum(aa)

    cnt = 0
    for i, c in enumerate(C):
        m = binary_search(B, c)
        if m != -1:
            cnt += bb[m]

    print(cnt)


main()


### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline


def binary_search(A, n, p):
    if p == "+":
        n += 0.5
    else:
        n -= 0.5

    left = 0
    right = len(A) - 1

    if n < A[0]:
        return 0
    else:
        while left <= right:
            mid = (left + right) // 2
            if A[mid] < n:
                left = mid + 1
            else:
                right = mid - 1

        return left


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    A, B, C = sorted(A), sorted(B), sorted(C)

    cnt = 0
    for i, b in enumerate(B):
        ab = binary_search(A, b, "-")
        bc = N - binary_search(C, b, "+")
        cnt += ab * bc

    print(cnt)


main()
s=input()
ans=0
for i range 6:
  if int(s[i])==1:
    ans+=1
print(ans)

### FIXED CODE ###

s=input()
ans=0
for i in range (6):
  if int(s[i])==1:
    ans+=1
print(ans)
import numpy as np

X = int(input())

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

primes = sorted(get_primes(10000))

print(primes[list(np.array(primes) > X).index(True)])

### FIXED CODE ###

import numpy as np

X = int(input())

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

primes = sorted(get_primes(110000))

print(primes[list(np.array(primes) >= X).index(True)])
# coding: utf-8
from math import factorial
N, K = map(int, input().split())
mod = 10**9 + 7
def combination(n, r):
    if n > r:
        return int(factorial(n) / (factorial(r) * factorial(n - r)))
    else:
        return 1

for i in range(1, K+1):
    if N == i:
        print(1)
    elif i%2 == 0:
        print(combination(N-K+1, i)*2%mod)
    else:
        print(combination(N-K+1, i)%mod)

### FIXED CODE ###

# coding: utf-8
from math import factorial
def combination(n, r):
    if n >= r and n >= 0 and r >= 0:
        return int(factorial(n) // (factorial(r) * factorial(n - r)))
    else:
        return 0
N, K = map(int, input().split())
mod = 10**9 + 7

for i in range(1, K+1):
    print(combination(N-K+1, i) * combination(K-1, i-1)%mod)
n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
mod=10**9+7
ans=0
MOD=10**9+7
def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret
for i in range(n-k+1):
    ans-=a[i]*cmb(n-i-1,k-1)
    ans%=mod
a=a[::-1]
for i in range(n-k+1):
    ans+=a[i]*cmb(n-i-1,k-1)
    ans%=mod

print(ans%mod)

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())))
mod=10**9+7
ans=0
MOD=10**9+7

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % MOD)
    inverse.append(pow(factorial[-1], MOD - 2, MOD))
 
 
# 組み合わせ計算
def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD
for i in range(n-k+1):
    ans-=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod
a=a[::-1]
for i in range(n-k+1):
    ans+=a[i]*nCr(n-i-1,k-1)%mod
    ans%=mod

print(ans%mod)
from fractions import gcd
setrecursionlimit(10**9)

def inpl(): return list(map(int, input().split()))
N, A, B, C = inpl()

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

size = 2*100000 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size

g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

P = 0
Q = pow(100-C, 2*N, MOD)*(100-C)%MOD

for x in range(N):
    P = (P + cmb(N+x-1, x, MOD) * (N+x) * pow(100-C, N-x, MOD) * (pow(inverse[A], N-x, MOD) + pow(inverse[B], N-x, MOD)))%MOD
P = P*100*pow(A, N, MOD)*pow(B, N, MOD)%MOD

gcd_ = gcd(P, Q)
P = P//gcd_
Q = Q//gcd_

if A*B == 0:
    print(N*100*pow(100-C, MOD-2, MOD)%MOD)
else:
    print(P*pow(Q, MOD-2, MOD)%MOD)

### FIXED CODE ###

from fractions import gcd

def inpl(): return list(map(int, input().split()))
N, A, B, C = inpl()

MOD = 10**9 + 7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

size = 2*100000 + 1
g1, g2, inverse = [0]*size, [0]*size, [0]*size

g1[:2] = [1, 1] # 元テーブル
g2[:2] = [1, 1] #逆元テーブル
inverse[:2] = [0, 1] #逆元テーブル計算用テーブル
 
for i in range(2, size):
    g1[i] =  ( g1[i-1] * i ) % MOD 
    inverse[i] = (-inverse[MOD % i] * (MOD//i) ) % MOD 
    g2[i] =  (g2[i-1] * inverse[i]) % MOD

P = 0
Q = pow(100-C, 2*N, MOD)*(100-C)%MOD

for x in range(N):
    P = (P + cmb(N+x-1, x, MOD) * (N+x) * pow(100-C, N-x, MOD) * (pow(inverse[A], N-x, MOD) + pow(inverse[B], N-x, MOD)))%MOD
P = P*100*pow(A, N, MOD)*pow(B, N, MOD)%MOD

gcd_ = gcd(P, Q)
P = P//gcd_
Q = Q//gcd_

if A*B == 0:
    print(N*100*pow(100-C, MOD-2, MOD)%MOD)
else:
    print(P*pow(Q, MOD-2, MOD)%MOD)
a,b = [float(i) for i in input().split()]
d = int(a/b)
r = int(a) % int(b)
f = a/b
f2 = round(decimal.Decimal(f), 10)
print(str(d) + " " + str(r) + " " + str(f2))


### FIXED CODE ###

a,b = [float(i) for i in input().split()]
d = int(a/b)
r = int(a) % int(b)
f = a/b
f = "{:.6f}".format(f)

print(d,r,f)
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(float,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

A,B = input().split()
A = int(A)
B = int(B * 100)

print(A*B // 100)

### FIXED CODE ###

from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import numpy as np
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(float,input().split())
def FLI(): return [int(i) for i in input().split()]
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

A,B = input().split()
A = int(A)
B = B.replace(".","")
B = int(B)

print(A*B // 100)
import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, xy))
        print(ans%1000000007)

### FIXED CODE ###

import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)
while True:
	stack = []
	for s in raw_input().split():
		if s in ('+', '-', '*', '/'):
			stack.append(eval('{2}{1}{0}'.format(stack.pop(), s, stack.pop())))
		else:
			stack.append(float(s))
	print '%.6f' % stack.pop()

### FIXED CODE ###

while True:
	try:
		stack = []
		for s in raw_input().split():
			if s in ('+', '-', '*', '/'):
				stack.append(eval('{2}{1}{0}'.format(stack.pop(), s, stack.pop())))
			else:
				stack.append(float(s))
		print '%.6f' % stack.pop()
	except EOFError:
		break
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
# N = 9
# AB = [[1, 2], [2, 3], [9, 8], [8, 3], [3, 4], [4, 5], [3, 6], [6, 7]]
if N == 2:
    print(1, 2)
if N == 3:
    print(1, 2, 3)


class Node:
    def __init__(self, v):
        self.linked = set()
        self.v = v

    def add_node(self, node):
        self.linked.add(node)

    def set_rank(self, parent, rank):
        self.rank = rank
        for node in self.linked:
            if node == parent:
                continue
            node.set_rank(parent=self, rank=rank + 1)

    def __repr__(self):
        return '{}'.format(self.rank)


nodes = {v: Node(v) for v in range(1, N + 1)}
for a, b in AB:
    nodes[a].add_node(nodes[b])
    nodes[b].add_node(nodes[a])

root = nodes[1]
root.set_rank(None, 0)

group = [[], [], []]
for node in nodes.values():
    group[node.rank % 3].append(node)
group.sort(key=len)
indexes = [0] * 3
result = {}
last = set(range(1, N + 1))
for node in group[0]:
    indexes[0] += 1
    result[node.v] = indexes[0] * 3
    last.remove(indexes[0] * 3)
for node in group[1]:
    if indexes[1] >= N // 3 + ((N % 3) >= 1):
        indexes[0] += 1
        result[node.v] = indexes[0] * 3
        last.remove(indexes[0] * 3)
    else:
        result[node.v] = indexes[1] * 3 + 1
        last.remove(indexes[1] * 3 + 1)
        indexes[1] += 1
for node in group[2]:
    result[node.v] = last.pop()
#
#     result[node.v] = indexes[2] * 3 + 2
#     indexes[2] += 1
print(' '.join(str(result[i]) for i in range(1, N + 1)))


### FIXED CODE ###

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


class Tree:
    def __init__(self, v):
        self.v = v
        self.neighbors = []

    def set_rank(self, rank, parent):
        self.rank = rank
        for neighbor in self.neighbors:
            if neighbor is parent:
                continue
            neighbor.set_rank(rank=rank + 1, parent=self)


trees = {i: Tree(i) for i in range(1, N + 1)}

for a, b in AB:
    trees[a].neighbors.append(trees[b])
    trees[b].neighbors.append(trees[a])
try:
    trees[1].set_rank(1, None)
except:
    print(-1)
    exit()

group0 = [node.v for node in trees.values() if node.rank % 2 == 0]
group1 = [node.v for node in trees.values() if node.rank % 2]
x = [set(), set(), set()]
for i in range(1, N + 1):
    x[i % 3].add(i)
if len(group1) < len(group0):
    group1, group0 = group0, group1
result = {}
if len(group0) <= len(x[0]):
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    y = x[0] | x[1] | x[2]
    while group1 and y:
        result[group1.pop()] = y.pop()
else:
    while x[2] and group0:
        result[group0.pop()] = x[2].pop()
    while x[1] and group1:
        result[group1.pop()] = x[1].pop()
    while group0 and x[0]:
        result[group0.pop()] = x[0].pop()
    while group1 and x[0]:
        result[group1.pop()] = x[0].pop()
    if group0 or group1:
        print(-1)
        exit()

print(' '.join(str(result[i]) for i in range(1, N + 1)))
n = input()

S = map(int, raw_input().split())

q = input()

T = map(int, raw_input().split())

S.append(0)
cnt = 0
for i in range(q):
    j = 0
    S[n] = T[i]
    while S[j] != S[n]:
        j = j + 1
    if j != n:
        cnt = cnt + 1


print cnt

### FIXED CODE ###

n = input()

S = map(int, raw_input().split())

q = input()

T = map(int, raw_input().split())

S.append(0)
cnt = 0
for i in range(q):
    j = 0
    S[n] = T[i]
    while S[j] != S[n]:
        j = j + 1
    if j != n:
        cnt = cnt + 1


print cnt
def gcd(_a,_b):
    b,a=sorted((_a, _b))
    if b==0:
        return 0
    while True:
        m=a%b
        if m==0:
            return b
        a=b;b=m

a,b,k=(int(x) for x in input().split())
g=gcd(a,b)
cd=[]
i=g
while True:
    if g%i==0:
        cd.append(i)
        i=i//2
        if i==1 or i==0:
            break
    else:
        i-=1
print(cd[k-1])

### FIXED CODE ###

def gcd(t):
    b,a=sorted(t)
    while True:
        m=a%b
        if m==0:
            return b
        a=b;b=m
a,b,k=(int(x) for x in input().split())
g=gcd((a,b))
cd=[]
for i in range(g+1)[::-1]:
    if i==0:
        break
    if g%i==0:
        cd.append(i)
print(cd[k-1])
S = input()
T = input()
ans = 'No'
if S == T:
    ans = 'Yes'
for i in range(len(S)):
    S = S[-1] + S
    S = S.rstrip(S[-1])
    if S == T:
        ans = 'Yes'
print(ans)

### FIXED CODE ###

S = input()
T = input()
ans = 'No'
if S == T:
    ans = 'Yes'
for i in range(len(S)):
    S = S[-1] + S
    S = S[:-1]
    if S == T:
        ans = 'Yes'
print(ans)