Harryxun/stf_run huggingface dataset:
# coding: utf-8
import os
from sys import stdin
from functools import total_ordering

__dirname = os.path.dirname(__file__)
__basename = os.path.splitext(os.path.basename(__file__))[0]
__targetname = './input/' + __basename + '.txt'
target_path = os.path.join(__dirname, __targetname)
stdin = open(target_path)

@total_ordering
class struct(object):
    def __init__(self,a,b):
        self.a=a
        self.b=b
    def __lt__	(self,other):
        return self.a < other.a
    def __eq__	(self,other):
        return self.a == other.a

def main():
    # st = struct(10,1)
    # print(st.a)
    input_line = stdin.readline().rstrip().split(' ')
    N, M = map(int, input_line)
    A = list()
    for _ in range(N):
        input_line = stdin.readline().rstrip().split(' ')
        a,b=map(int, input_line)
        st=struct(a,b)
        A.append(st)
    A.sort()
    ans=0
    time=0
    for x in A:
        # print(x.a,x.b)
        if(time>M):
            continue
        if((time+x.b)<=M):
            ans += x.a*x.b
            time += x.b
        else:
            ans += x.a*(M-time)
            time = M
    print(ans)



if __name__ == "__main__":
    main()
    

### FIXED CODE ###

# coding: utf-8
import os
from sys import stdin
from functools import total_ordering

# __dirname = os.path.dirname(__file__)
# __basename = os.path.splitext(os.path.basename(__file__))[0]
# __targetname = './input/' + __basename + '.txt'
# target_path = os.path.join(__dirname, __targetname)
# stdin = open(target_path)

@total_ordering
class struct(object):
    def __init__(self,a,b):
        self.a=a
        self.b=b
    def __lt__	(self,other):
        return self.a < other.a
    def __eq__	(self,other):
        return self.a == other.a

def main():
    # st = struct(10,1)
    # print(st.a)
    input_line = stdin.readline().rstrip().split(' ')
    N, M = map(int, input_line)
    A = list()
    for _ in range(N):
        input_line = stdin.readline().rstrip().split(' ')
        a,b=map(int, input_line)
        st=struct(a,b)
        A.append(st)
    A.sort()
    ans=0
    time=0
    for x in A:
        # print(x.a,x.b)
        if(time>M):
            continue
        if((time+x.b)<=M):
            ans += x.a*x.b
            time += x.b
        else:
            ans += x.a*(M-time)
            time = M
    print(ans)



if __name__ == "__main__":
    main()
#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    ns = list(map(int, sys.stdin.readline().strip()))
    ns.append(0)
    ns.reverse()

    pay = [0] * (len(ns) + 1)
    charge = [0] * (len(ns) + 1)
    for i in range(len(ns)):
        if pay[i] == 0:
            if ns[i] <= 4 or (ns[i] == 5 and ns[i + 1] <= 4):
                pay[i] = ns[i]
                charge[i] = 0
            else:
                pay[i] = 0
                pay[i + 1] = 1
                charge[i] = 10 - ns[i]
        else:
            if pay[i] + ns[i] <= 4 or (pay[i] + ns[i] == 5 and ns[i + 1] <= 4):
                pay[i] += ns[i]
                charge[i] = 0
            else:
                pay[i] = 0
                pay[i + 1] = 1
                charge[i] = 9 - ns[i]
    #print(''.join(map(str, reversed(pay))))
    #print(''.join(map(str, reversed(charge))))
    print(sum(pay) + sum(charge))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
import itertools

def main():
    ns = list(map(int, sys.stdin.readline().strip()))
    ns.reverse()
    ns.append(0)

    ans = 0
    lastpay = 0

    for i in range(len(ns)):
        if lastpay == 0:
            if ns[i] <= 4 or (ns[i] == 5 and ns[i + 1] <= 4):
                ans += ns[i]
                lastpay = 0
            else:
                ans += 1 + (10 - ns[i])
                lastpay = 1
        else:
            if lastpay + ns[i] <= 4 or (lastpay + ns[i] == 5 and ns[i + 1] <= 4):
                ans += ns[i]
                lastpay = 0
            else:
                ans += 1 - 1 + (9 - ns[i])
                lastpay = 1
    print(ans)

if __name__ == '__main__':
    main()
s = input().split('/')
if s[0] <= 2018:
    print('Heisei')
elif s[0] == 2019 and s[1] <=4:
    print('Heisei')
elif s[0] == 2019 and s[1] >= 5:
    print('TBD')
elif s[0] >= 2020:
    print('TBD')


### FIXED CODE ###

s =list(map(int,input().split('/')))

if s[0] <= 2018:
    print('Heisei')
elif s[0] == 2019 and s[1] <=4:
    print('Heisei')
elif s[0] == 2019 and s[1] >= 5:
    print('TBD')
elif s[0] >= 2020:
    print('TBD')
H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    w = input()
    grid.append(w)

output = [[0] * W for _ in range(H)]
k = 1
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            output[i][j] = k
            k += 1

def h_paint(i, j):
    dj = j
    k = output[i][j]
    while (dj-1 >= 0):
        if output[i][dj - 1] == 0:
            output[i][dj - 1] = k
            dj -= 1
        else:
            break
    dj = j
    while (dj + 1 < W):
        if output[i][dj + 1] == 0:
            output[i][dj + 1] = k
            dj += 1
        else:
            break
            

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            h_paint(i, j)

for i in range(H-1, -1, -1):
    for j in range(W):
        if output[i][j] == 0:
            output[i][j] = output[i + 1][j]

for i in range(1, H):
    for j in range(W):
        if output[i][j] == 0:
            output[i][j] = output[i-1][j]

for o in output:
    print(*o)

### FIXED CODE ###

H, W, K = map(int, input().split())
grid = []
for _ in range(H):
    w = input()
    grid.append(w)

output = [[0] * W for _ in range(H)]
k = 1
for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            output[i][j] = k
            k += 1

def h_paint(i, j):
    dj = j
    k = output[i][j]
    while (dj-1 >= 0):
        if output[i][dj - 1] == 0:
            output[i][dj - 1] = k
            dj -= 1
        else:
            break
    dj = j
    while (dj + 1 < W):
        if output[i][dj + 1] == 0:
            output[i][dj + 1] = k
            dj += 1
        else:
            break
            

for i in range(H):
    for j in range(W):
        if grid[i][j] == '#':
            h_paint(i, j)

for i in range(H-2, -1, -1):
    for j in range(W):
        if output[i][j] == 0:
            output[i][j] = output[i + 1][j]

for i in range(1, H):
    for j in range(W):
        if output[i][j] == 0:
            output[i][j] = output[i-1][j]

for o in output:
    print(*o)
n,m,k=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
for i in range(n+1):
    if k<a[i]:
        break
    j=m
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)

### FIXED CODE ###

a=int(input())
print(a+a*a+a*a*a)
inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1 and abci[1]=n-1:
                print('inf')
                exit()

print(-d[n-1])

### FIXED CODE ###

inf=float('inf')
n, m=map(int, input().split())
abc=[list(map(int, input().split())) for i in range(m)]
abc=[[ai[0]-1, ai[1]-1, -ai[2]] for ai in abc]
d=[inf]*n
d[0]=0
for i in range(n):
    flag=False
    for abci in abc:
        if d[abci[1]]>d[abci[0]]+abci[2]:
            flag=True
            d[abci[1]]=d[abci[0]]+abci[2]
            if i==n-1 and abci[1]==n-1:
                print('inf')
                exit()

print(-d[n-1])
N, K = map(int,input().split())
A = list(map(int,input().split()))
ans = 0
B = [0]*20

for i in A:
    B[i] += 1
B.sort(reverse = True)

for i in range(K,N):
    ans += B[i]
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int,input().split()))
 
b = [0]*200002
 
for a in A:
  b[a] += 1
b.sort(reverse = True)
print(n-sum(b[:k]))
import sys

H,W = map(int,input().split())
s = [list(input()) for i in range(W)]
a = [["."]*H for _ in range(W)]
for i in range(H):
    for j in range(1,W):
        if s[i][j-1] == "#" and s[i][j] == "#":
            a[i][j-1] = "#"
            a[i][j] = "#"

sT = list(zip(*s))
aT = [list(x) for x in zip(*a)]

for i in range(H):
    for j in range(1,W):
        if sT[i][j-1] == "#" and sT[i][j] == "#":
            aT[i][j-1] = "#"
            aT[i][j] = "#"

ans = list(zip(*aT))

for i in range(H):
    for j in range(W):
        if s[i][j] != ans[i][j]:
            print("No")
            sys.exit()
print("Yes")

### FIXED CODE ###

import sys

H,W = map(int,input().split())
s = [list(input()) for i in range(H)]
a = [["."]*W for _ in range(H)]
for i in range(H):
    for j in range(1,W):
        if s[i][j-1] == "#" and s[i][j] == "#":
            a[i][j-1] = "#"
            a[i][j] = "#"

sT = list(zip(*s))
aT = [list(x) for x in zip(*a)]

for i in range(W):
    for j in range(1,H):
        if sT[i][j-1] == "#" and sT[i][j] == "#":
            aT[i][j-1] = "#"
            aT[i][j] = "#"

ans = list(zip(*aT))

for i in range(H):
    for j in range(W):
        if s[i][j] != ans[i][j]:
            print("No")
            sys.exit()
print("Yes")
string = input()
ones = 0
zeros = 0
for s in string:
  if s == '1':
    ones += 1
  else:
    zeroes += 1
print(2*min(ones, zeros))

### FIXED CODE ###

string = input()
ones = 0
zeros = 0
for s in string:
  if s == '1':
    ones += 1
  else:
    zeros += 1
print(2*min(ones, zeros))
def put(i,n):
    global row,cur
    if cur[0]>W-1 or cur[0]<0:
        B.append(row)
        row = ["." for _ in range(W)]
        if cur==[-1,"L"]:
            cur = [0,"R"]
        elif cur==[W,"R"]:
            cur = [W-1,"L"]
    if n==0:
        return
    row[cur[0]] = i
    n -= 1
    if cur[1]=="R":
        cur[0] += 1
    elif cur[1]=="L":
        cur[0] -= 1
    put(i,n)
        
H,W = map(int,input().split())
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
B = []
row = ["." for _ in range(W)]
cur = [0,"R"]
for i in range(1,N+1):
    n = A[i]
    put(i,n)
    
for i in range(H):
    print(*B[i])

### FIXED CODE ###

def put(i):
    global n,row,cur
    while n>0:
        row[cur[0]] = i
        n -= 1
        if cur[1]=="R":
            cur[0] += 1
        elif cur[1]=="L":
            cur[0] -= 1
        if cur[0]>W-1 or cur[0]<0:
            B.append(row)
            row = ["." for _ in range(W)]
        if cur==[-1,"L"]:
            cur = [0,"R"]
        elif cur==[W,"R"]:
            cur = [W-1,"L"]
        
H,W = map(int,input().split())
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
B = []
row = ["." for _ in range(W)]
cur = [0,"R"]
for i in range(1,N+1):
    n = A[i]
    put(i)
    
for i in range(H):
    print(*B[i])
s=input()
t="keyence"
i=0
for x in s:
    if t[i]==x:i+=1
print("YES" if i>6 else "NO")

### FIXED CODE ###

s=input()
t="keyence"
f=False
if s[0:7]==t:f=True
for x in range(8):
    if s[:x]==t[:x] and s[-7+x:]==t[-7+x:]:f=True
print("YES" if f else "NO")
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,S = MI()
A = LI()
dp = FILL2(0,N+1,S+1)
for i in range(N):
    for j in range(S+1):
        if j>0 and j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]
        elif j==0:
            dp[i+1][A[i]] += i+1
        dp[i+1][j] += dp[i][j]
ans = 0
for i in range(N+1):
    ans += dp[i][S]
    ans %= MOD
print(ans)


### FIXED CODE ###

import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,S = MI()
A = LI()
dp = FILL2(0,N+1,S+1)
for i in range(N):
    for j in range(S+1):
        if j>0 and j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD
        elif j==0 and A[i]<=S:
            dp[i+1][A[i]] += i+1
            dp[i+1][A[i]] %= MOD
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
ans = 0
for i in range(N+1):
    ans += dp[i][S]
    ans %= MOD
print(ans)
n,x=map(int, input().split())
llist=list(map(int, input().split()))
sum=0
cnt=0
while sum+llist[cnt]<x and cnt<n:
  sum+=llist[cnt]
  cnt+=1
print(cnt+1)

### FIXED CODE ###

n,x=map(int, input().split())
llist=list(map(int, input().split()))
point=0
cnt=1
for i in range(n):
  point+=llist[i]
  if(point<=x):
    cnt+=1
print(cnt)
N, K = int(input().split())
juice = []
for i in range(N):
    juice.append(list(map(int,input().split())))
juice.sort()
for i in range(K):
  print (juice[0] + juice[1] + juice[2])

### FIXED CODE ###

N,K = map(int, input().split())
*a, = map(int, input().split())
print (sum(sorted(a)[:K]))
S=input()
Y=S[0:4]
M=S[5:7]
D=S[7:9]
YMD=int(Y+M+D)
if YMD<=20190430:
  print("Heisei")
else:
  print("TBD")

### FIXED CODE ###

S=input()
Y=S[0:4]
M=S[5:7]
D=S[8:10]
YMD=int(Y+M+D)
if YMD<=20190430:
  print("Heisei")
else:
  print("TBD")
def getAns(x,y):
    num=int(y/x)
    res=1
    while num>1:
        num/=2
        res+=1
    return res

x,y=map(int,input().split())
print getAns(x,y)

### FIXED CODE ###

x,y=map(int,input().split())
ans=0
while x<=y:
    x = x*2
    ans +=1
print(ans)
##import numpy as np???????????????
n, m = map(int, raw_input().split())
 
a = [[0]*m for i in xrange(n)]
 
b = [0]*m
 
for i in xrange(n):
    tmp = map(int, raw_input().split())
    for j in xrange(m):
        a[i][j] = tmp[j]
for i in xrange(m):
    b[i] = input()
for i in xrange(n):
    tmp = 0
    for j in xrange(m):
        tmp += a[i][j] * b[j]
    print tmp

### FIXED CODE ###

n, m = map(int, raw_input().split())
 
a = [[0]*m for i in xrange(n)]
 
b = [0]*m
 
for i in xrange(n):
    tmp = map(int, raw_input().split())
    for j in xrange(m):
        a[i][j] = tmp[j]
for i in xrange(m):
    b[i] = input()
for i in xrange(n):
    tmp = 0
    for j in xrange(m):
        tmp += a[i][j] * b[j]
    print tmp
from bisect import bisect_left
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
bisec = bisect_left
ex = A.extend
su =0
for i in range(M):
    if BC[i][1]<=A[0]:
        break
    B= BC[i][0]
    C = BC[i][1]
    b = bisec(A,C)
    if B>=b:
        su = C*b
        A = [A[i] for i in range(b,N)]
    else:
        su = C*B
        A = [A[i] for i in range(B,N)]
print(sum(A)+su)

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key= lambda x: x[1],reverse=True)
A.sort()
n = 0
i = 0
m = 0
while A[i]<BC[n][1]:
    A[i] = BC[n][1]
    m = m+1
    if m >=BC[n][0]:
        m = 0
        n = n+1
    i += 1
    if n==M:
      break
    if i == N:
      break
print(sum(A))
from collections import deque
a=int(input())
list=deque([])

for i in range(a):
    order=input().split()
    if order[0]=="insert":
        list.appendleft(order[1])
    elif order[0]=="delete":
        if order[1] in list:
            list.remove(order[1])
    elif order[0]=="deleteFirst":
        list.pop()
    elif order[0]=="deleteLast":
        list.pop()

print(*list)


### FIXED CODE ###

from collections import deque
a=int(input())
list=deque([])

for i in range(a):
    order=input().split()
    if order[0]=="insert":
        list.appendleft(order[1])
    elif order[0]=="delete":
        if order[1] in list:
            list.remove(order[1])
    elif order[0]=="deleteFirst":
        list.popleft()
    elif order[0]=="deleteLast":
        list.pop()

print(*list)
import math
A,B=map(int,input().split())
Amin=A/0.08
Amax=(A+1)/0.08
Bmin=B/0.1
Bmax=(B+1)/0.1


if Amax<Bmin or Bmax<Amin:
    print(-1)
else:
    p=(Amin,Bmin)
    print(math.ceil(p))



### FIXED CODE ###

import math
A,B=map(int,input().split())
Amin=A/0.08
Amax=(A+1)/0.08
Bmin=B/0.1
Bmax=(B+1)/0.1


if Amax<=Bmin or Bmax<=Amin:
    print(-1)
else:
  a=math.ceil(Amin)
  b=math.ceil(Bmin)
  if a<Bmax or b<Amax:
    print(max(a,b))
  else:
    print(-1)
a,b = map(int,input().split())

import math
ans = int(a * b / math.gcd(a, b))

print(ans)





### FIXED CODE ###


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

def gcd(a,b):
    if a%b==0:
        return b
    else:
        return gcd(b,a%b)
ans = a*b//gcd(a,b)
print(ans)
import math

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

count = 0
i = A
d = B - A

ta = d // C
tb = d // D
tc = d//(C * D // math.gcd(C, D))

print(d-(ta+tb-tc))

### FIXED CODE ###

import fractions

def calc(v):
    ta = v // C
    tb = v // D
    tc = v // ((C * D) // fractions.gcd(C, D))
    return v-(ta+tb-tc)


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

count = 0
i = A
a = calc(A-1)
b = calc(B)
print(abs(a-b))
a = input()
b = a[::2].index('0') + a[1::2].index('1')
c = min(b, len(a) - b)
print(c)

### FIXED CODE ###

a = list(input())
b = a[::2].count('0') + a[1::2].count('1')
c = min(b, len(a) - b)
print(c)
tx = [map(int, input().split())]
cx = sorted(x)

for i in range(2):
    if cx[i] == cx[i+1]:
        print(sum(cx) - 2*cx[i])

### FIXED CODE ###

a, b, c = map(int, input().split())
lst = sorted([a, b, c])

for i in range(2):
    if lst[i] == lst[i+1]:
        print(sum(lst) - 2*lst[i])
from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
# 0-2: amari
for i in range(1, n+1):
    nums[i%3].append(i)

ans = [0 for _ in range(n)]
def dfs(step, idx, pre_3, pre_2, pre_1):
    pre_3_mod = pre_3 % 3
    if pre_3 == -1:
        if len(nums[step%3]) > 0:
            out = nums[step%3].pop()
        else:
            for i in [1, 2, 0]:
                if len(nums[i]) > 0:
                    out = nums[i].pop()
                    break
    else:
        if pre_3_mod != 0:
            if len(nums[3 - (pre_3_mod)]) > 0:
                out = nums[3 - (pre_3_mod)].pop()
            else:
                if len(nums[0]) > 0:
                    out = nums[0].pop()
                else:
                    print(ans)
                    print(-1)
                    exit()
        else:
            if len(nums[1]) > len(nums[2]):
                out = nums[1].pop()
            else:
                out = nums[2].pop()
    ans[idx-1] = out
    for k in edges[idx].keys():
        if ans[k-1] == 0:
            dfs(step+1, k, pre_2, pre_1, out)

dfs(1, 1, -1, -1, -1)

print(" ".join(list(map(str, ans))))

### FIXED CODE ###

from collections import deque, defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

n = int(input())
edges = defaultdict(lambda : defaultdict(lambda: False))
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a][b] = True
    edges[b][a] = True

nums = [deque() for _ in range(3)]
for i in range(1, n+1):
    nums[i%3].append(i)

color = [-1 for _ in range(n)]
cnts = [0 for _ in range(2)]
def coloring(num, pre_color):
    if pre_color:
        col = 0
    else:
        col = 1
    color[num-1] = col
    cnts[col] += 1
    for k in edges[num].keys():
        if color[k-1] == -1:
            coloring(k, col)

coloring(1, 1)

ans = [0 for _ in range(n)]
def solve(v):
    for i in range(n):
        if color[i] == v:
            ans[i] = nums[0].pop()
        else:
            for j in [1, 2, 0]:
                if len(nums[j]) > 0:
                    ans[i] = nums[j].pop()
                    break

if cnts[0] <= n // 3:
    # print("A")
    solve(0)
elif cnts[1] <= n // 3:
    # print("B")
    solve(1)
else:
    # print("C")
    for i in range(n):
        if color[i]:
            if len(nums[1]) > 0:
                ans[i] = nums[1].pop()
            else:
                ans[i] = nums[0].pop()
        else:
            if len(nums[2]) > 0:
                ans[i] = nums[2].pop()
            else:
                ans[i] = nums[0].pop()

print(" ".join(list(map(str, ans))))
import math

def using_sqrt(limit,elm):
    n = 0
    if limit < 2:
        return 0

    elm.append(2)

    for k in range(3, limit+1,2):
        factor = 0

        # 2以外の偶数は素数ではないので無視する
        if k % 2 == 0 and k != 2:
            continue

        # 繰り返しの上限を対象の平方根にする
        for divisor in range(2, math.floor(math.sqrt(k))+1):
            if k % divisor == 0:
                factor += 1

        if factor == 0:
            elm.append(k)
            n += 1

    return n


N = int(input())
A = []

using_sqrt(N,A)

A_len=len(A)

for i in range(A_len):
    chk = A[i]
    while True:
        chk *= A[i]
        if chk <= N:
            A.append(chk)
        else:
            break

A.sort()

A_len=len(A)
cnt = 0
chk_N = N
for i in range(A_len):
    if chk_N % A[i] == 0:
        chk_N = int(chk_N / A[i])
        cnt += 1
        
    if chk_N == 1:
        break

print(cnt)


### FIXED CODE ###

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

ans=A*B

print(ans)
import math
ans = 10**12
n = int(input())
for a in range(1,int(math.sqrt(n)):
  for b in range(1,int(math.sqrt(n)):
    if a * b == n:
      ans_n = a + b -2
      if ans > ans_n:
        ans = ans_n
print(ans) 

### FIXED CODE ###

n = int(input())
ans = float('inf')
 
for i in range(1, 10**6+1):
    q, m = divmod(n, i)
    if m == 0:
        ans = min(ans, q+i)
 
print(ans-2)
a,b=(int(x) for x in input().split())
lista=[]
listb=[]
for numa in range(a+1):
  lista.append(numa*2)
for numb in range(a+1):
  listb.append(numb*4)
listb.reverse()
count=0
combined1 = [x*y for (x, y) in (lista, listb)]
for num in combined1:
  if num==b:
    count+=1
if count>0:
  print("Yes")
else: 
  print("No")

### FIXED CODE ###

a,b=(int(x) for x in input().split())
lista=[]
listb=[]
for numa in range(a+1):
  lista.append(numa*2)
for numb in range(a+1):
  listb.append(numb*4)
listb.reverse()
count=0
combined1 = [x+y for (x, y) in zip(lista, listb)]
for num in combined1:
  if num==b:
    count+=1
if count>0:
  print("Yes")
else: 
  print("No")