Harryxun/stf_run huggingface dataset:
from collections import Counter
import sys
sys.setrecursionlimit(1000000000)

N = int(input())

edges = {i:[] for i in range(1, N+1)}
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

vertice = [0 for _ in range(N+1)]

def dfs(v, color_i):
    vertice[v] = color_i
    for i in edges[v]:
        if vertice[i] == 0:
            dfs(i, color_i*(-1))

dfs(1, 1)

c = Counter(vertice)
ans = []
if c[1] > N/3 and c[2] > N/3:
    nums1 = [i for i in range(1, N+1) if i % 3 == 1]
    nums2 = [i for i in range(1, N+1) if i % 3 == 2]
    nums3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num1:
                ans.append(str(num1.pop()))
            else:
                ans.append(str(num3.pop()))
        else:
            if num2:
                ans.append(str(num2.pop()))
            else:
                ans.append(str(num3.pop()))
elif c[1] <= N/3:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == 1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))
else:
    num_not_3 = [i for i in range(1, N+1) if i % 3 != 0]
    num3 = [i for i in range(1, N+1) if i % 3 == 0]
    for v in vertice[1:]:
        if v == -1:
            if num3:
                ans.append(str(num3.pop()))
            else:
                ans.append(str(num_not_3.pop()))
        else:
            ans.append(str(num_not_3.pop()))

print(" ".join(ans))


### FIXED CODE ###

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
 
group = [False] * n
parent = list(range(n))
stack = [0]
while stack:
  v = stack.pop()
  while edge[v]:
    u = edge[v].pop()
    if parent[v] != u:
      group[u] = not group[v]
      parent[u] = v
      stack.append(u)
 
three = 3
p = [0] * n
if group.count(False) <= n // 3:
  other = 1
  for i in range(n):
    if group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
elif group.count(True) <= n // 3:
  other = 1
  for i in range(n):
    if not group[i] and other <= n:
      p[i] = other
      other += other % 3
    else:
      p[i] = three
      three += 3
else:
  one, two = 1, 2
  for i in range(n):
    if group[i] and one <= n:
      p[i] = one
      one += 3
    elif not group[i] and two <= n:
      p[i] = two
      two += 3
    else:
      p[i] = three
      three += 3
print(' '.join(map(str, p)))
import sys

sys.setrecursionlimit(100000)

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13
G = [[] for _ in range(N + 1)]
for a, b, c in egdes:
    G[a].append((b, c))

# ループをチェックしてコストが正ならinf
def check_loop(a, b, d):
    if a == b:
        return d > 0
    ret = False
    for to, c in G[a]:
        d += c
        ret |= check_loop(to, b, d)
    return ret


for a, b, c in egdes:
    if a > b:
        if check_loop(a, b, 0):
            print('inf')
            exit()

# 動的計画法のために隣接行列
G = [[-INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = c
dp = [-INF] * (N + 1)
dp[1] = 0
for i in range(1, N + 1):
    for j in range(1, i):
        dp[i] = max(dp[i], dp[j] + G[j][i])
print(dp[N])

### FIXED CODE ###

N, M = map(int, input().split())
egdes = [list(map(int, input().split())) for _ in range(M)]

INF = 10 ** 13

G = [[INF] * (N + 1) for _ in range(N + 1)]
for a, b, c in egdes:
    G[a][b] = -c
dist = [INF] * (N + 1)
dist[1] = 0
for _ in range(N - 1):
    for a, b, c in egdes:
        dist[b] = min(dist[b], dist[a] - c)
ans = dist[N]
for a, b, c in egdes:
    dist[b] = min(dist[b], dist[a] - c)
print(-ans if ans == dist[N] else 'inf')
ans=0
n=int(input())
for _ in range(n):
    x,u=input().split()
    if x=='JPY':
        ans+=int(u)
    else:
        ans+=(float(u)*380000.0)
print(ans)

### FIXED CODE ###

ans=0
n=int(input())
for _ in range(n):
    x,u=input().split()
    if u=='JPY':
        ans+=int(x)
    else:
        ans+=(float(x)*380000.0)
print(ans)
n = input()
a = list(map(int, input().split()))
flg = True
break_flg = False
total = 0
while True:
  for i, b in enumerate(a):
    if b%2 == 0:
      a[i] = b/2
    else:
      break_flg = True
      breake
  if break_flg :
    break
  else:
    total += 1
print(total)


### FIXED CODE ###

n = input()
a = list(map(int, input().split()))
flg = True
break_flg = False
total = 0
while True:
  for i, b in enumerate(a):
    if b%2 == 0:
      a[i] = b/2
    else:
      break_flg = True
  if break_flg :
    break
  else:
    total += 1
print(total)
nums=[]
for i in range(6):
  nums.append(int(input()))
s = "Yay!"
for i in nums:
  if abs(i - nums[i:-1]) > nums[-1]:
    s = ":("
print(s)

### FIXED CODE ###

nums = []
for i in range(5):
    nums.append(int(input()))
k = int(input())
s = "Yay!"
for i in range(5):
    for m in range(5 - i):
        a = nums[i]
        if abs(a - nums[m]) > k:
             s = ":("
             break
print(s)
a =  int(input())
b = int(input())


ans = a + b
if ans >= 10:
        print("error")
else :
        print(ans)


### FIXED CODE ###

ilist =  input().split(" ")
ans = int(ilist[0]) + int(ilist[1] )
if ans >= 10:
        print("error")
else :
        print(ans)
s = set(list(int(input())))
if s == {'a','b','c'}:
    print('Yes')
else:
  print('No')

### FIXED CODE ###

s = set(list(input()))
if s == {'a','b','c'}:
    print('Yes')
else:
  print('No')
n = int(input())
x = [int(input().split()) for i in range(n)]
 
ans = 1
for i in x:
  ans = ans*i
  
if ans > 1000000000000000000:
  ans = -1
print(ans)

### FIXED CODE ###

n=int(input())
x=list(map(int, input().split()))
 
ans=1
if 0 in x:
  ans=0
else:
  for i in x:
    ans=ans*i
    if ans>10**18:
      ans=-1
      break
print(ans)
import numpy as np
N,M,C = (int(j) for j in input().split())
B = [int(j) for j in input().split()]
list = [[0]* M]*N
for j in range(0,N):
        list[j] = [int(k) for k in input().split()]
count = 0
for j in range(0,N):
    if np.sum(np.array(list[j]) * np.array(B)) C >0:
        count = count + 1
print(count)

### FIXED CODE ###

import numpy as np
N,M,C = (int(j) for j in input().split())
B = [int(j) for j in input().split()]
list = [[0]* M]*N
for j in range(0,N):
        list[j] = [int(k) for k in input().split()]
count = 0
for j in range(0,N):
    if np.sum(np.array(list[j]) * np.array(B)) + C > 0:
        count = count + 1
print(count)
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

nn = int(input())
aa = list(map(int,input().split()))

ne = [0]*200000
cn = [0]*200000
cnminus1 = [0]*nn
#print(nn,aa)
#print(len(ne))
for i in range(nn):
    ne[aa[i]] += 1

for i in range(nn):
 #   print(ne[i])
    if ne[i] == 0:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 1:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 2:
        cn[i] = 1
        cnminus1[i] = 0
    else:
        cn[i] = combinations_count(ne[i],2)
        cnminus1[i] = combinations_count(ne[i]-1,2)

sum_cn = sum(cn)

for i in range(nn):
    print(sum_cn - cn[aa[i]] + cnminus1[aa[i]])



### FIXED CODE ###

import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

nn = int(input())
aa = list(map(int,input().split()))

ne = [0]*(nn+1)
cn = [0]*(nn+1)
cnminus1 = [0]*(nn+1)
#print(nn,aa)
#print(len(ne))
for i in range(nn):
    ne[aa[i]] += 1

for i in range(nn+1):
 #   print(ne[i])
    if ne[i] == 0:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 1:
        cn[i] = 0
        cnminus1[i] = 0
    elif ne[i] == 2:
        cn[i] = 1
        cnminus1[i] = 0
    else:
        cn[i] = combinations_count(ne[i],2)
        cnminus1[i] = combinations_count(ne[i]-1,2)

sum_cn = sum(cn)

for i in range(nn):
    print(sum_cn - cn[aa[i]] + cnminus1[aa[i]])
import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()


a,b,c = map(int, stdin.readlien().split())
if a <= c <= b:
    print("Yes")
else:
    print("No")
    

### FIXED CODE ###

import sys

stdin = sys.stdin


def na(): return map(int, stdin.readline().split())


def ns(): return stdin.readline().strip()


a,b,c = na()
if a <= c <= b:
    print("Yes")
else:
    print("No")
{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "1\n",
      "1\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "A = int(input())\n",
    "B = int(input())\n",
    "C = int(input())\n",
    "X = int(input())\n",
    "res=0\n",
    "for  i in range(A + 1):\n",
    "    for j in range(B + 1):\n",
    "        for k in range(C + 1):\n",
    "            if 500*i + 100*j + 50*k == X:\n",
    "                res += 1\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())
cnt = 0

for i in range(c+1):
    for j in range(b+1):
        if (x-50*i-100*j)%500==0 and ((x-50*i-100*j)/500)<=a and ((x-50*i-100*j)/500)>=0:
            cnt += 1

print(cnt)
import numpy as np
import copy

N = int(input())
A = [int(i) for i in input().split()]
A = list(set(A))

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

if N==2:
    print(max(A))
else:
    gcds = []
    for i in range(len(A)-1):
        if i == 0:
            gcds.append(gcd(A[0],A[1]))
        else:
            gcds.append(gcd(gcds[-1],A[i]))
    gcds = np.asarray(gcds)
    
    index = []
    for idx,n in enumerate(gcds.min() == gcds):
        if n==True:
            index.append(idx)
    a = []
    for i in index:
        if i+1 in index:
            None
        else:
            a.append(i+1)
    for i in a:
        index.append(i)
    gcds = []
    for idx in index:
        A_temp = copy.deepcopy(A)
        A_temp.pop(idx)
        gcds_temp = []
        for i in range(len(A_temp)-1):
            if i ==0:
                gcds_temp.append(gcd(A_temp[0],A_temp[1]))
            else:
                gcds_temp.append(gcd(gcds_temp[-1],A_temp[i]))
        gcds.append(min(gcds_temp))
    print(max(gcds))


### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  
lgcds = [A[0]]
rgcds = [A[N-1]]
for n in range(N-2):
    lgcds.append(gcd(lgcds[-1],A[n+1]))
    rgcds.append(gcd(rgcds[-1],A[-2-n]))
gcds = [lgcds[-1],rgcds[-1]]
for i in range(N-2):
    gcds.append(gcd(lgcds[i],rgcds[-2-i]))
print(max(gcds))
I=input()
if I==1:
 print('hello world')
else:
  A=input()
  B=input()
  print(int(A)+int(B))


### FIXED CODE ###

I=input()
if I=='1':
 print('Hello World')
else:
  A=input()
  B=input()
  print(int(A)+int(B))
#N,Kの取得
N,K = list(map(int,input().split()))

#[(a_1,b_1),(a_2,b_2),...]の形でリストを作成
numList = [ map(int,input().split()) for _ in range(N) ]

#作成したリストを、aの大きさで昇順ソート
numList = sorted(numList,key=lambda x:x[0])

#小さい順に要素数bを足していき、Kを超えた段階で出力、終了
count = 0
for a,b in numList:
	count += b
	if count>=K:
		print(a)
		quit()

### FIXED CODE ###

#N,Kの取得
N,K = list(map(int,input().split()))

#[(a_1,b_1),(a_2,b_2),...]の形でリストを作成
numList = []
for a,b in [ map(int,input().split()) for _ in range(N) ]:
	numList.append((a,b))

#作成したリストを、aの大きさで昇順ソート
numList = sorted(numList,key=lambda x:x[0])

#小さい順に要素数bを足していき、Kを超えた段階で出力、終了
count = 0
for a,b in numList:
	count += b
	if count>=K:
		print(a)
		quit()
r1,c1,r2,c2=map(int,input().split())
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 )
print((cmb(c2+r2+2,c2+1,mod)-cmb(c2+r1+1,c2+1,mod)-cmb(c1+r2+1,c1,mod)+cmb(c1+r1,c1,mod)+mod)%mod)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
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 = 2*10**6+10
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 )
print((cmb(c2+r2+2,c2+1,mod)-cmb(c2+r1+1,c2+1,mod)-cmb(c1+r2+1,c1,mod)+cmb(c1+r1,c1,mod)+mod)%mod)
n = int(input())
a = [int(_) for _ in input().split()]
b = []
ans = 0
for i in range(1,n):
    q = a[0] ^ a[i]
    b.append(q)
    ans += q
b = sorted(b)
s_b = [0] * n
for i in range(n-1):
    s_b[i+1] = b[i] + s_b[i]
for i in range(n-2):
    ans += s_b[n] - s_b[i+1] * (n-i)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [0 for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            if a_s[c] == '1':
                l[c] += 1
    for i in range(p):
        c1 = l[i]
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

if __name__ == '__main__':
    main()
a,b,c=[int() for x in input().split]
if a<b:
 if b<c:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a,b,c=[int(x) for x in input().split()]
if a<b<c:
    print("Yes")
else:
    print("No")
n,k=map(int,input().split())
p=list(map(int,input().split()))
s=0
sort(p)
for i in range(k):
    s+=p[i]

print(s)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=0
p.sort()
for i in range(k):
    s+=p[i]

print(s)
N = input()
N=int(N)
if N>=1,N<=999:
    print('ABC')
if N>=1000,N<=1998:
    print('ABD')

### FIXED CODE ###

N = input()
N=int(N)
if N>=1 and N<=999:
    print('ABC')
if N>=1000 and N<=1998:
    print('ABD')
n = int(input())
list = list(map(int,input().split()))

min_ = min(list)
max_ = max(list)

total = []
for i in range(min_, max_):
  length = 0
  for j in range(n):
  	length += (list[j] - i)**2
  total.append(length)
print(min(total))

### FIXED CODE ###

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

min_ = min(list)
max_ = max(list)

total = []
if min_ == max_:
  print(0)
else:
  for i in range(min_, max_):
    length = 0
    for j in range(n):
  	  length += (list[j] - i)**2
    total.append(length)
  print(min(total))
import math
A, B, K = map(int, input().split())
num = math.gcd(A,B)
a = []
a.append(num)
for i in range(1,num):
    if num % i == 0:
        a.append(i)
b = sorted(a)
print(b[len(b)-K])

### FIXED CODE ###

a,b,k=map(int,input().split())
li=[]
for i in range(1,min(a,b)+1):
    if a%i==0 and b%i==0:
        li.append(i)
print(li[len(li)-k])
import math
n,a,b=map(int,input().split())
na=1
m=7+10**9
def gyakugen(a,b):
    r=[1,0,a]
    w=[0,1,b]
    while(w[2]!=1):
        q=r[2]//w[2]
        r2=w
        w2=[r[0]-q*w[0],r[i]-q*w[i],r[2]-q*w[2]]
        r=r2
        w=w2
    return (b+w[0]%b)%b
ans=1
for i in range(n):
    ans*=2
    if ans>=m:
        ans%=m

for i in range(1,n+1):
    na=na*i%m
nb=na
for i in range(1,n-a+1):
    na=na*gyakugen(i,m)%m
for i in range(1,a+1):
    na=na*gyakugen(i,m)%m
for i in range(1,n-b+1):
    nb=nb*gyakugen(i,m)%m
for i in range(1,b+1):
    nb=nb*gyakugen(i,m)%m    
ans=ans-na-nb-1
ans%=m
print(ans)

### FIXED CODE ###

n,a,b=map(int,input().split())
m=10**9+7

#(a*x)をmで割った余りが1になるようなxを求める
#aで割ったときの余りはa^(-1)をかけた余りと同じ
#逆元a^(-1)を求める
#aとmが互いに素であることが条件

def gyakugen( a, m ):
  b = m
  x, y = 1, 0
  while b>0:
    q = a // b
    a, b = b, a-q*b
    x, y = y, x-q*y
  return x if x>0 else x+m

#nPrをmで割った余りを求める(ただしn<m、mは素数)
import sys
sys.setrecursionlimit(10**9)#再帰の回数の上限を設定

def perm_remainder(n,r,m):
    if r>=1:
        return (perm_remainder(n-1,r-1,m)*n)%m
    else:
        return 1

#nCrをmで割った余りを求める(ただしn<m,mは素数)

def comb_remainder(n,r,m):
    r=min(r,n-r)
    return (perm_remainder(n,r,m)*gyakugen(perm_remainder(r,r,m),m))%m

#(a**n)を素数mで割った余りを求める
#当然aはmで割り切れない整数

def power_remainder(a,x,m):
    a=a%m
    bi=str(format(x,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %m
        if bi[i]=="1":
            res=(res*a) %m
    return res

#2^n-nCa-nCb-1を計算
print((power_remainder(2,n,m)-1-comb_remainder(n,a,m)-comb_remainder(n,b,m))%m)
N=input()

if N%9==0:
	print("Yes")
else:
	print("No")

### FIXED CODE ###

N=input()
a=[int(i) for i in N]
b=sum(a)

if b%9==0:
	print("Yes")
else:
	print("No")
n=int(input())
v=sorted(list(map(float,input().split())))
x=-1
y=-1
z=10000
for k in range(n-1):
    for i in range(n-1):
        if v[i+1]-v[i] < z:
            x=i+1
            y=i
            z=v[i+1]-v[i]
    v[y]=(v[x]+v[y])/2
    del(v[x])
    n=len(v)
print(v[0])

### FIXED CODE ###

n=int(input())
v=sorted(list(map(float,input().split())))
z = v[0]
for i in range(1,n):
    z=(z+v[i])/2
print(z)
n=int(input())
print("Four" if sum(["Y" if in input().split() for i in range(n)])!=0 else "Three")

### FIXED CODE ###

n=int(input())
A=sorted(list(input().split()))
if A[-1]=="Y":
  print("Four")
else:
  print("Three")
,b,c = map(int,input().split())
print(min(c,b // a))

### FIXED CODE ###

a,b,c = map(int,input().split())
print(min(c,b // a))
n = input()
s = input().str()

ans = 0
for i in range(0, n):
    if s[i]=="I":
        ans+=1
    else:
        ans-=1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 0
x = 0
for i in range(n):
    if s[i]=="I":
        ans+=1
        x = max(ans, x)
    else:
        ans-=1
        x = max(ans, x)
print(x)
from math import sqrt
from math import factorial
n = int(input())
t = []
for i in range(n):
  t.append(list(map(int,input().split())))
l = [[0]*n for j in range(n)]
for k in range(n):
  for m in range(n):
    if k != m:
      d = sqrt((t[k][0]-t[m][0])**2+(t[k][1]-t[m][1])**2)
      l[k][m] = d
print(int(sum(l)*factorial(n-2)*2/n))

### FIXED CODE ###

from math import sqrt
from math import factorial
 
n = int(input())
t = []
for i in range(n):
  t.append(list(map(int,input().split())))
l = [[0]*n for j in range(n)]
for k in range(n):
  for m in range(n):
      l[k][m] = sqrt((t[k][0]-t[m][0])**2+(t[k][1]-t[m][1])**2)
ans = 0
for i in range(n):
  s = sum(l[i])
  ans += s*factorial(n-1)
z = ans/factorial(n)
print(z)
import math
A, B, C, D = map(int, input().split())

l = int((B-A)/C)
m = int((B-A)/D)
lcm = C*D/math.gcd(C,D)
c = B-A-l-m+int((B-A)/lcm)
print(c)


### FIXED CODE ###

import fractions
A, B, C, D = map(int, input().split())
def F(x):
    l = x//C
    l += x//D
    lcm = C*D//fractions.gcd(C,D)
    l -= x//lcm
    return x-l
print(F(B)-F(A-1))
s = input()
t = input()
ans = 0
for i in range(3):
	if s[i] == t[i]:
    	ans += 1
print(ans)

### FIXED CODE ###

s = input()
t = input()
ans = 0
for i in range(3):
    if s[i] == t[i]:
        ans += 1
print(ans)
N = int(input())
dp = [[float('inf') for i in range(N+1)] for j in range(4)]
dp[0][0] = 0
dp[3] = [i for i in range(N+1)]
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(nine,0,-1):
    dp[1][9**i] = 1
    x= (9**i)
    for j in range(x,N+1):
        dp[1][j] = min(dp[1][j],dp[1][j-x]+1)
for i in range(1,six+1):
    dp[2][6**i] = 1
    x= (6**i)
    for j in range(N+1):
        if j >= 9:
            dp[2][j] = min(dp[2][j],dp[2][j-x]+1)
        if j >= x:
            dp[2][j] = min(dp[2][j],dp[1][j-x]+1)
for i in range(1,6):
    dp[3][-1] = min(dp[3][-1],dp[2][N-i]+i)
print(dp[-1][-1])


### FIXED CODE ###

N = int(input())
dp = [float('inf') for i in range(N+1)]
dp[0] = 0
if N >= 6:
    dp[6] = 1
def below_power(n,a):
    "n以下になるa**xのxの最大値を求める"
    x = 0
    while n >= a**x:
        x += 1
    return x-1
nine = below_power(N,9)
six = below_power(N,6)
for i in range(six,0,-1):
    for j in range(N+1):
        if j - 6**i >= 0:
            dp[j] = min(dp[j],dp[j-6**i]+1)
for i in range(nine,0,-1):
    for j in range(N+1):
        if j - 9**i >= 0:
            dp[j] = min(dp[j],dp[j-9**i]+1)       
ans = dp[N]
for i in range(1,min(N+1,6)):
    ans = min(ans,dp[N-i]+i)
print(ans)
a, b = map(int, input().split())

A0 = 0
A1 = 0
B0 = 0
B1 = 0

A0 = a / 0.08
A1 = (a+1) / 0.08
B0 = b / 0.1
B1 = (b+1) / 0.1
ans1 = [i for i in range(int(A0), int(A1)+1)]
ans2 = [i for i in range(int(B0), int(B1)+1)]
ans = set(ans1) &  set(ans2)
if ans == {}:
    print('-1')
else:
    print(min(ans))

### FIXED CODE ###

import math as ma
def minCharge810(a, b):
    A0 = 0
    A1 = 0
    B0 = 0
    B1 = 0

    A0 = ma.ceil(a / 0.08)
    A1 = ma.floor((a+1) / 0.08)
    B0 = ma.ceil(b / 0.1)
    B1 = ma.floor((b+1) / 0.1)

    ans1 = [i for i in range(int(A0), int(A1))]
    ans2 = [i for i in range(int(B0), int(B1))]
    ans = set(ans1) &  set(ans2)
    if ans == set():
        return '-1'
    else:
        return min(ans)
a, b = map(int, input().split())
print(minCharge810(a, b))
import math
def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

d = list(map(int, input().split()))
print(d[0]-d[1]+1)
for i in range(2, d[1]+1): #2~k
    print(ncr(d[0]-d[1]+1, i)*ncr(d[1]-1, i-1)%1000000007)

### FIXED CODE ###

import math
def ncr(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

d = list(map(int, input().split()))
print(d[0]-d[1]+1)
for i in range(2, d[1]+1): #2~k
    if (d[0]-d[1]+1)<i:
        print(0)
    else:
        print(ncr(d[0]-d[1]+1, i)*ncr(d[1]-1, i-1)%1000000007)
b = input()
 
if b == A:
  print("T")
if b == T:
  print("A")
if b == C:
  print("G")
if b == G:
  print("C")

### FIXED CODE ###

b = input()
 
if b == "A":
  print("T")
if b == "T":
  print("A")
if b == "C":
  print("G")
if b == "G":
  print("C")
s = input()

def solve(i):
    
    if i == 2:
        if s[i - 1] == s[i]:
            return 2
        else:
            return solve(i - 1) + 1
    if i == 1:
        if s[i - 1] == s[i]:
            return 1
        else:
            return 2
    if i == 0:
        return 1

    if s[i] != s[i - 1]:
        return solve(i - 1) + 1
    else:
        return solve(i - 3) + 2


print(solve(len(s) - 1))


### FIXED CODE ###

import sys

sys.setrecursionlimit(2000000)

s = input()

def solve(i):
    if i == 2:
        if s[i - 1] == s[i]:
            return 2
        else:
            return solve(i - 1) + 1
    if i == 1:
        if s[i - 1] == s[i]:
            return 1
        else:
            return 2
    if i == 0:
        return 1

    if s[i] != s[i - 1]:
        return solve(i - 1) + 1
    else:
        return solve(i - 3) + 2


print(solve(len(s) - 1))
N = int(input())
S = list(input())
cnt = 0
i = 1
while True:
        if i == N:break
        if S[i-1] == "A" and S [i] == "B" and S[i+1] == "C":
                cnt += 1
        i += 1
print(cnt)





### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    if s[i:i+3] == "ABC":
        cnt += 1
print(cnt)
a=[]
while True:
 n=input()
 if n=='0 ? 0':break
 a.append(n)
for s in a:
 t=s.split()
 if t[1]=="/":
  print(t[0]//t[1])
 else:
  print(eval(''.join(t)))

### FIXED CODE ###

while 1:
 a=input()
 if'?'in a:break
 print(int(eval(a)))