Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from math import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    d=defaultdict(lambda:[0,0])
    for _ in range(N):
        a,b=map(int,input().split())
        g=gcd(a,b)
        a//=g
        b//=g
        if a<0:
            a*=-1
            b*=-1
        if a*b>0:
            d[(a,b)][0]+=1
        elif a*b<0:
            d[(-b,a)][1]+=1
        else:
            d[0][0]+=1
    l=[]
    zero=0
    other=0
    for k,a in d.items():
        if k==0:
            zero=a[0]
        else:
            if a[0] and a[1]:
                l.append((a[0],a[1]))
            else:
                other+=sum(a)
    ans=pow(2,other,MOD)*(zero+1)
    ans%=MOD
    dp=[[0]*2 for _ in range(len(l)+1)]
    dp[0][0]=1
    for i in range(len(l)):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        dp[i+1][1]=(dp[i][0]+dp[i][1])*(pow(2,l[i][0],MOD)+pow(2,l[i][1],MOD)-2)
        dp[i+1][0]%=MOD
        dp[i+1][1]%=MOD
    ans*=sum(dp[-1])
    ans-=1
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
from math import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    d=defaultdict(lambda:[0,0])
    zz=0
    for _ in range(N):
        a,b=map(int,input().split())
        g=gcd(a,b)
        if g==0:
            zz+=1
        else:
            a//=g
            b//=g
            if a<0:
                a*=-1
                b*=-1
            if a*b>0:
                d[(a,b)][0]+=1
            elif a*b<0:
                d[(-b,a)][1]+=1
            else:
                if a:
                    d[(1,0)][0]+=1
                else:
                    d[(1,0)][1]+=1
    l=[]
    other=0
    for k,a in d.items():
        if a[0] and a[1]:
            l.append((a[0],a[1]))
        else:
            other+=sum(a)
    ans=pow(2,other,MOD)
    ans%=MOD
    dp=[[0]*2 for _ in range(len(l)+1)]
    dp[0][0]=1
    for i in range(len(l)):
        dp[i+1][0]=dp[i][0]+dp[i][1]
        dp[i+1][1]=(dp[i][0]+dp[i][1])*(pow(2,l[i][0],MOD)+pow(2,l[i][1],MOD)-2)
        dp[i+1][0]%=MOD
        dp[i+1][1]%=MOD
    ans*=sum(dp[-1])
    ans-=1
    ans+=zz
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()
mod = 10 ** 9 + 7


def p(n, r):
    if n < r:
        return 0
    return fact[n] * invs[n - r] % mod


def dfs(v, bf):
    global ans
    if v == 0:
        ans *= p(k, len(es[v]) + 1)
        ans %= mod
    else:
        ans *= p(k - 2, len(es[v]) - 1)
        ans %= mod

    for nv in es[v]:
        if nv == bf: continue
        dfs(nv, v)


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

es = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

fact = [1]
for i in range(1, k + 1):
    fact.append(fact[-1] * i % mod)

invs = [None] * (k + 1)
invs[k] = pow(fact[-1], mod - 2, mod)
for i in range(k - 1, -1, -1):
    invs[i] = invs[i + 1] * (i + 1) % mod

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


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

input = sys.stdin.readline


def rec(v, bf):
    global ans
    gs[v] += 1
    gs[bf] += 1
    ans = ans * (K - gs[bf]) % mod
    for nv in es[v]:
        if nv == bf: continue
        rec(nv, v)
    return


N, K = map(int, input().split())

es = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    es[a].append(b)
    es[b].append(a)

gs = [0] * (N + 1)
gs[0] = -1
gs[N] = -1

ans = 1

rec(0, N)
print(ans)
k = int(input())
mo = 0
for i in range(1, k + 1):
    mo = mo * 10 + 7
    k = mo % k
    if mod == 0:
        print(i)
        break
else:
    print(-1)

### FIXED CODE ###

k = int(input())
mo = 7
mo = mo % k
for i in range(1 , k + 1):
  if mo == 0:
    print(i)
    break
  if mo != 0:
    mo = (mo * 10 + 7) % k
else:
  print(-1)
sys.setrecursionlimit(100000)
def lcm(x,y):
    return (x*y)//gcd(x,y)

def gcd(x,y):
    if y <= 0:
        return x
    else:
        return gcd(y,x%y)

N = int(input())
T = [int(input()) for _ in range(N)]
ans = lcm(T[0],T[1])
for i in range(2,N):
    ans = lcm(ans,T[i])
print(ans)

### FIXED CODE ###

import sys
import os
sys.setrecursionlimit(100000000)

def lcm(x,y):
    return (x*y)//gcd(x,y)

def gcd(x,y):
    if y <= 0:
        return x
    else:
        return gcd(y,x%y)

N = int(input())
T = [int(input()) for _ in range(N)]
if N == 1:
    print(T[0])
    sys.exit()

ans = lcm(T[0],T[1])
for i in range(2,N):
    ans = lcm(ans,T[i])
print(ans)
n = int(input())
x = int(input(),2)
# b = int(2**(n-1))
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1

mp =  x%(pc+1)
mm = x%(pc-1)
# print(x,pc,mp,mm)
for i in range(n):
    if d[-i-1]==0:
        m = 1
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
    else:
        m = -1
        temp = (mm-pow(2,n-i-1,pc+1)) % (pc-1)
    # temppc = pc+m
    # temp = x^b
    ans = 1
    # print(temp,x,b)
    # print(temp,mp,pc,pow(2,n-i,pc+1))
    while temp:
        
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        # print(temp)
        # print(i,temp,ans,temppc)
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        # c = temp
        # temppc = 0
        # while c:
        #     if c&1 == 1:
        #         temppc += 1
        #     c=c>>1
        # print(temp,s)
        # break
    # b=b>>1
    print(ans)

### FIXED CODE ###

n = int(input())
x = int(input(),2)
# b = int(2**(n-1))
pc = 0
d = []
c = x
for i in range(n):
    d.append(c&1)
    if c&1 == 1:
        pc += 1
    c=c>>1

mp =  x%(pc+1)
if pc == 1:
    mm = -1
else:
    mm = x%(pc-1)
# print(x,pc,mp,mm)
for i in range(n):
    if d[-i-1]==0:
        m = 1
        temp = (mp+pow(2,n-i-1,pc+1)) % (pc+1)
        ans = 1
    else:
        if mm == -1:
            temp = 0
            ans = 0
        else:    
            m = -1
            temp = (mm-pow(2,n-i-1,pc-1)) % (pc-1)
            ans = 1
    # temppc = pc+m
    # temp = x^b
    # ans = 1
    # print(temp)
    # print(temp,mm,pc,pow(2,n-i,pc+1),(mm-pow(2,n-i-1,pc+1)) % (pc-1))
    while temp:
        
        c = temp
        temppc = 0
        while c:
            if c&1 == 1:
                temppc += 1
            c=c>>1
        # print(temp)
        # print(i,temp,ans,temppc)
        # print(temp)
        # s = str(bin(temp))
        # print(temp,popcount(temp))
        if temppc == 0:
            break
        temp = temp % temppc
        ans += 1
        # c = temp
        # temppc = 0
        # while c:
        #     if c&1 == 1:
        #         temppc += 1
        #     c=c>>1
        # print(temp,s)
        # break
    # b=b>>1
    print(ans)
N, M = map(int, input().split()) 
A = list(map(int, input().split()))

seg = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]

B = {}
for a in A:
    ind = seg[a]
    if not ind in B.keys():
        B[ind] = a
    else:
        if B[ind] < a:
            B[ind] = a

I = sorted(list(B.keys()))
#print(I)
def search(ind, remain, ret):
    if ind >= len(I):
        return False, ret
    #print(I[ind], remain, ret)
    a = I[ind]
    p = remain // a
    r = remain % a 
    if p == 0:
        return False, ret
    if r == 0:
        ret.append((a, p))
        return True, ret
    for q in range(p-1, -1, -1):
        r += a
        oldr = ret[:]
        ok, newr = search(ind+1, r, oldr)
        if ok:
            newr.append((a, q))
            if ind == 0:
                Ap.append(newr)
                continue
            return True, newr
    if ind == 0:
        return Ap
    return False, ret

Ap = []
Ls = search(0, N, [])
#print(Ls)
anss = []
for L in Ls:
    Q = []
    for k, v in L:
        Q.extend([B[k]]*v)
    Q.sort(reverse=True)
    num = int(''.join([str(q) for q in Q]))
    anss.append(num)

print(max(anss))

### FIXED CODE ###

import sys
input = sys.stdin.readline

NUM = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
INF = 10**14

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

dp = [-INF]*(N+1)
dp[0] = 0
for i in range(N):
    for a in A:
        c = NUM[a]
        if i + c <= N:
            dp[i+c] = max(dp[i+c], dp[i]+1)

D = dp[N]
ind = N
ans = ''
for _ in range(D):
    for a in A:
        c = NUM[a]
        if ind - c < 0: continue
        if dp[ind] == dp[ind-c] + 1:
            ind -= c
            ans += str(a)
            break
print(ans)
a, b, k = map(int, input().split())
m = min(a, b)
cnt = 0
for i in range(m, 0, -1):
	if (a % i == 0) and (b % i == 0):
      cnt += 1
      if cnt == k:
        print(i)
        

### FIXED CODE ###

a, b, k = map(int, input().split())
m = min(a, b)
cnt = 0
for i in range(m, 0 ,-1):
    if (a % i == 0) and (b % i == 0):
        cnt += 1
        if cnt == k:
            print(i)
            exit()
n=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        t1=n*i*j
        t2=4*i*j-n*j-n*i
        if t1%t2==0 and 1<=t1//t2<3500:
            print(i,j,t1//t2)
            exit()

### FIXED CODE ###

n=int(input())
for i in range(1,3501):
    for j in range(1,3501):
        t1=n*i*j
        t2=4*i*j-n*j-n*i
        if t2>0 and t1%t2==0:
            print(i,j,t1//t2)
            exit()
x = input()
return x*x*x

### FIXED CODE ###

x = input()
print x*x*x
S = {i: input() for i in 'abc'}
s = 'a'
while S[s]:
  s = S[s].pop(0)
print(s)

### FIXED CODE ###

S = {i: list(input()) for i in 'abc'}
s = 'a'
while S[s]:
  s = S[s].pop(0)
print(s.upper())
# ARC076C - Reconciled?
def factorial_mod(x):
    MOD = 10 ** 9 + 7
    ret = 1
    for i in range(1, x + 1):
        ret = (ret * i) % MOD
    return ret


def main():
    n, m = list(map(int, input().rstrip().split()))
    MOD = 10 ** 9 + 7
    n, m = min(n, m), max(n, m)
    dif = m - n
    if dif > 1:  # must be ...DDM...
        print(0)
    else:
        if dif == 0:  # start with either D or M (DM..., MD...)
            ans = (factorial_mod(n) ** 2 * 2) % MOD
        else:  # sandwich (DMD or MDM)
            ans = (factorial(n) ** 2 * m) % MOD
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ARC076C - Reconciled?
from math import factorial


def main():
    n, m = list(map(int, input().rstrip().split()))
    MOD = 10 ** 9 + 7
    dif = abs(n - m)
    if abs(n - m) not in (0, 1):
        print(0)
    else:
        if dif == 0:
            ans = (factorial(n) * factorial(m) * 2) % MOD
        else:
            ans = (factorial(n) * factorial(m)) % MOD
        print(ans)


if __name__ == "__main__":
    main()
A, B, C = input().split()
 
if B + C <= A:
  result = 0
else:
  result = B+C-A
 
print(result)

### FIXED CODE ###

A, B, C = input().split()

a = int(A)
b = int(B)
c = int(C)
if b + c <= a:
  result = 0
else:
  result = b+c-a
 
print(result)
while 1:
    n,w = map(int,raw_input().split())
    if n == 0: break
    v = [0]*10
    m = 0
    for i in range(n):
        p = int(raw_input())/w
        v[p] += 1
        m = max(m,p)
    ans = 0.01
    for i in range(10):
        ans += (v[i]*1.0/max(v))*(1-i*1.0/m)
    print ans

### FIXED CODE ###

while 1:
    n,w = map(int,raw_input().split())
    if n == 0: break
    v = [0.]*11
    m = 0
    for i in range(n):
        p = int(raw_input())/w
        v[p] += 1.
        m = max(m,p)
    vm = max(v)
    ans = 0.01+sum((v[i]/vm)*(1-i*1.0/m) for i in range(m))
    print ans
n = int(input())
m = n

count = 0
for i in range(1,100):
    if n >= 26 ** i:
        n = n - 26 ** i
        count += 1
    else:
        break

a = []
b = list('abcdefghijklmnopqrstuvwxyz')
#print(n,count,n // (26 ** A5))
count2 = 0
while 1:
    #print(n)
    count2 = n // (26 ** count)
    n = n % 26 ** count
    if n < 26 ** count:
        a.append(count2)
    count -= 1
    if count == 0:
        a.append(n-1)
        break
#print(n)
x = [b[a[i]]for i in range(len(a))]
print("".join(x))



### FIXED CODE ###

n = int(input()) - 1

a = []
b = list('abcdefghijklmnopqrstuvwxyz')

if n <= 25:
    print(b[n])
    exit()
count = 0
for i in range(1,100):
    if n >= 26 ** i:
        n = n - 26 ** i
        count += 1
    else:
        break


#print(n,count,n // (26 ** A5))
count2 = 0


while 1:
    #print(n)
    #print(n,count,a)
    if count == 0:
        a.append(n)
        break
    count2 = n // (26 ** count)
    n = n % 26 ** count
    a.append(count2)
    count -= 1

#print(n)
x = [b[a[i]]for i in range(len(a))]
print("".join(x))
S=input()

print(S.rfind("Z")-S.find("A"+1))

### FIXED CODE ###

S=input()

print(S.rfind("Z")-S.find("A")+1)
def main():
    input = sys.stdin.readline
    Dy = [0,1,0,-1]
    Dx = [1,0,-1,0]
    H, W, K = map(int, input().split())
    y1,x1,y2,x2 = map(int, input().split())
    C = ["@" + input() for _ in range(H)]
    C = ["@"*(W+2)] + C + ["@"*(W+2)]
    Closed = [[False]*(W+2) for _ in range(H+2)]
    Nexts = [[[(y+dy, x+dx) for x in range(W+2)] for y in range(H+2)] for dy, dx in zip(Dy, Dx)]
    def root(y, x, Next):
        yp, xp = Next[y][x]
        if not Closed[yp][xp]:
            return yp, xp
        else:
            yp, xp = root(yp, xp, Next)
            Next[y][x] = (yp, xp)
            return yp, xp
    def remove(y, x):
        for i in range(2):
            y1, x1 = Nexts[i][y][x]
            y2, x2 = Nexts[i+2][y][x]
            Nexts[i+2][y1][x1] = (y2, x2)
            Nexts[i][y2][x2] = (y1, x1)
        Closed[y][x] = True
    q = [(y1, x1)]
    remove(y1, x1)
    ans = 0
    while q:
        q_new = []
        for y0, x0 in q:
            if (y0, x0) == (y2, x2):
                print(ans)
                exit()
            for Next in Nexts:
                while True:
                    y, x = root(y0, x0, Next)
                    if abs(y-y0)+abs(x-x0) > K or C[y][x] != ".":
                        break
                    remove(y, x)
                    q_new.append((y, x))
        q = q_new
        ans += 1
    print(-1)

main()


### FIXED CODE ###

Dy = [0,1,0,-1]
Dx = [1,0,-1,0]
H, W, K = map(int, input().split())
y1,x1,y2,x2 = map(int, input().split())
C = ["@" + input() + "@" for _ in range(H)]
C = ["@"*(W+2)] + C + ["@"*(W+2)]
L = [[1]*(W+2) for _ in range(H+2)]
R = [[1]*(W+2) for _ in range(H+2)]
U = [[1]*(W+2) for _ in range(H+2)]
D = [[1]*(W+2) for _ in range(H+2)]
q = [(y1, x1)]
ans = 0
while q:
    q_new = []
    for y0, x0 in q:
        if (y0, x0) == (y2, x2):
            print(ans)
            exit()
        for dy, dx, Next in zip(Dy, Dx, [L, R, U, D]):
            y, x = y0, x0
            sum_next = 0
            Path = [(y, x)]
            while True:
                sum_next += Next[y][x]
                y = y0 + dy * sum_next
                x = x0 + dx * sum_next
                if sum_next > K:
                    break
                if C[y][x] == "@":
                    break
                Path.append((y, x))
                q_new.append((y, x))
            for path_y, path_x in Path:
                Next[path_y][path_x] = abs(path_y-y) + abs(path_x-x)
    q = q_new
    ans += 1

print(-1)
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
t = 999 #平均気温とAとの最短の差
p = 0 #その差を記録したポイント
for i in range(H):
  if t > abs(A - T - H[i]*0.006):
    t = abs(A - T - H[i]*0.006)
    p = i+1
print(p)

### FIXED CODE ###

N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
t = 999 #平均気温とAとの最短の差
p = 0 #その差を記録したポイント
for i in range(len(H)):
  if t > abs(A - T + H[i]*0.006):
    t = abs(A - T + H[i]*0.006)
    p = i+1
print(p)
from math import gcd

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()

ans = int(n*m / gcd(n,m))
for i in range(n):
    if (m*i)%n==0:
        if s[i] != t[(m*i)//n]:
            ans = -1
            
print(ans)


### FIXED CODE ###

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

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()
g = gcd(m,n)

ans = int(n*m / g)
for i in range(g):
    if s[(n//g)*i] != t[(m//g)*i]:
        ans = -1
            
print(ans)
n,p = map(int, input().split())
if n == 1:
  print(p)
  exit(0)
a = int(p**(1/n)+1)
for i in range(a,0,-1):
  if p%(i**n)==0:
    print(i)
    exit(0)

### FIXED CODE ###

n,p = map(int, input().split())
a = round(p**(1/n))
for i in range(a,-1,-1):
  if p%(i**n)==0:
    print(i)
    exit()
N = int(input())
T = [int(input()) for _ in range(N)]

import math
def lcm(x, y):
  return (x*y) // math.gcd(x, y)

result = []
for i in range(N):
  try:
    result.append(lcm(T[i], T[i+1]))
  except:
    break
print(max(result))

### FIXED CODE ###

N = int(input())

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

result = []
x = 1
for i in range(N):
  T = int(input())
  x = x * T // gcd(x, T)
  result.append(x)
print(max(result))
import math

x = int(input())
x_pow = round(math.pow(x, 1/5))
ok = 0

for a in range(-x_pow-10, x_pow+10):
  for b in range(-x_pow-10, x_pow+10):
    if a**5 - b**5 == x:
      print(a,b)
      ok = 1
      eixt()

### FIXED CODE ###

import math
 
x = int(input())
x_pow = round(math.pow(x, 1/5))
ok = 0
 
for a in range(-300,300):
  for b in range(-300,300):
    if a**5 - b**5 == x:
      print(a,b)
      ok = 1
      exit()
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

x=[i for i in range(2,55556)if is_prime(i)and i%5==1]
print(*x[:int(input())])

### FIXED CODE ###

import math
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

x=[i for i in range(2,55556)if is_prime(i)and i%5==1]
print(*x[:int(input())])
N=input()
answer="No"
for i in range(len(N)-2)
  if N[i]==N[i+1]:
    if N[i+1]==N[i+2]:
      answer="Yes"
print(answer)

### FIXED CODE ###

N=input()
answer="No"
for i in range(len(N)-2):
  if N[i]==N[i+1]:
    if N[i+1]==N[i+2]:
      answer="Yes"
print(answer)
import sys
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0, 0]
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] != -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == 0:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)
group = [-1] * N
count = [0] * 2
stack = []
group[0] = 0
count[0] = 1
stack.append(0)
while stack:
    u = stack.pop()
    for v in G[u]:
        if group[v] == -1:
            group[v] = 1 - group[u]
            count[group[v]] += 1
            stack.append(v)
zeros = list(range(3, N+1, 3))
ones = list(range(1, N+1, 3))
twos = list(range(2, N+1, 3))
ans = [0] * N
for g in range(2):
    if count[g] <= N//3:
        for i in range(N):
            if group[i] == g:
                ans[i] = zeros.pop()
            else:
                if len(twos) > 0:
                    ans[i] = twos.pop()
                elif len(ones) > 0:
                    ans[i] = ones.pop()
                else:
                    ans[i] = zeros.pop()
        print(' '.join(map(str, ans)))
        exit()
for i in range(N):
    if group[i] == 0 and len(ones) > 0:
        ans[i] = ones.pop()
    elif group[i] == 1 and len(twos) > 0:
        ans[i] = twos.pop()
    else:
        ans[i] = zeros.pop()
print(' '.join(map(str, ans)))
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))

sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

x = STR()
l = len(x)
ans = l
a = x[0]
st = []
tmp = 1
for i in range(1, l):
    if a[i] == a[i-1]:
        tmp += 1
    else:
        st.append(tmp)
        tmp = 1
st.append(tmp)

if a == 'S':
    for i in range(0, len(tmp), 2):
        ans -= min(tmp[i], tmp[i+1]) * 2
    print(ans)
else:
    for i in range(1, len(tmp), 2):
        ans -= min(tmp[i], tmp[i+1]) * 2
    print(ans)


### FIXED CODE ###

x = str(input())
n = len(x)
stack = []
for i in range(n):
    if x[i] == 'S':
        stack.append('S')
    elif len(stack) == 0 or stack[len(stack) - 1] == 'T':
        stack.append('T')
    else:
        stack.pop()
print(len(stack))
a, b = map(int, input().split())
s = input()

print(s[:k-1] + s[k-1].lower() + s[k:])


### FIXED CODE ###

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

print(s[:b-1] + s[b-1].lower() + s[b:])
a,b=input()
print('H' if a==H and b==H or a==D and b==D else 'D')


### FIXED CODE ###

a,_,b=input()
print('H' if a==b else 'D')
c= input().split("")
len = length(c)
for i in len-1:
  if c[i]="?":
    c[i]="D"

print(c)
    

### FIXED CODE ###

a= input()
c=""
for i in range(0, len(a)):
    if a[i]=="?":
        c=c+"D"
    else:
        c=c+a[i]
print(c)
n, l = map(int, input().split())
string_list = sorted([input() for i in range(l)])
print("".join(string_list))

### FIXED CODE ###

n, l = map(int, input().split())
string_list = sorted([input() for i in range(n)])
print("".join(string_list))
n=int(input())
s=input()

r_cnt=s.count("R")
g_cnt=s.count("G")
b_cnt=s.count("B")

ans=r_cnt*g_cnt*b*cnt

for i in range(n):
    for d in range(n):
        j=i+d
        k=j+d
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans-=1

print(ans)

### FIXED CODE ###

N=input()
if '7' in N:
  print('Yes')
else:
  print('No')
w,h,x,y=map(int,input().split())
ans1=(w*h)/2.0
ans=0
if (w/2==x)and(h/2==y):
    ans2=1
print('%f %d'%(ans1,ans2))

### FIXED CODE ###

w,h,x,y=map(int,input().split())
ans1=(w*h)/2.0
ans2=0
if (w/2==x)and(h/2==y):
    ans2=1
print('%f %d'%(ans1,ans2))
N,K = map(int,input().split())
ab = sorted([map(int,input().split()) for _ in [0]*N])
for a,b in ab:
    K -= b
    if K <= 0:
        print(a)
        break

### FIXED CODE ###

N,K = map(int,input().split())
ab = sorted([list(map(int,input().split())) for _ in [0]*N])
for a,b in ab:
    K -= b
    if K <= 0:
        print(a)
        break