Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[[] for i in s_x]
dpy=[[] for i in s_y]
dpx[0].append(s_x[0])
dpy[0].append(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.append(xx-l)
        ll.append(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.append(yy-l)
        ll.append(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
s=input().strip()
x,y=map(int,input().split())
sl=[len(i) for i in s.split('T')]
x0,y0=sl[0],0
s_x = sl[::2]
s_y = sl[1::2]
s_y=[0]+s_y
dpx=[set() for i in s_x]
dpy=[set() for i in s_y]
dpx[0].add(s_x[0])
dpy[0].add(0)
for i,l in enumerate(s_x):
    if i==0:continue
    ll=dpx[i]
    for xx in dpx[i-1]:
        ll.add(xx-l)
        ll.add(xx+l)
for i,l in enumerate(s_y):
    if i==0:continue
    ll=dpy[i]
    for yy in dpy[i-1]:
        ll.add(yy-l)
        ll.add(yy+l)
print('Yes' if x in dpx[-1] and y in dpy[-1] else 'No')
### BUGGY CODE ###

S = input()
Q = int(input())
bol = 0
for i in range(Q):
    a = input().split()
    if a[0] == "1":
        bol = 0 if bol else 1
    elif a[1] == "1":
        if not bol:
            S = a[2] + S
        else:
            S = S + a[2]
    else:
        if not bol:
            S = S + a[2]
        else:
            S = a[2] + S
print(S if not bol else "".join(reversed(S)))

### FIXED CODE ###

from collections import deque
S = input()
d = deque([S[i] for i in range(len(S))])
Q = int(input())
bol = 0
for i in range(Q):
    a = input().split()
    if a[0] == "1":
        bol = 0 if bol else 1
    elif a[1] == "1":
        if not bol:
            d.appendleft(a[2])
        else:
            d.append(a[2])
    else:
        if not bol:
            d.append(a[2])
        else:
            d.appendleft(a[2])
print("".join(d) if not bol else "".join(reversed(d)))
### BUGGY CODE ###

N = int(input())
A = list([int(input()) for _ in range(N)])
ans = []

for a in A:
    if a not in ans:
        ans.append(a)
    else:
        ans.remove(a)
print(len(ans))


### FIXED CODE ###

import collections

N = int(input())
A = list([int(input()) for _ in range(N)])
A = collections.Counter(A).values()

ans = [x for x in A if x&1]
print(len(ans))
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = list(map(int, input().split()))[:k]
b = list(map(int, input().split()))[:k]
c = list(map(int, input().split()))[:k]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
def f(a, b):
    return [i + j for i in a for j in b]
ab_results = f(a, b)
ab_results.sort(reverse=True)
results = f(c, ab_results[:k])
results.sort(reverse=True)

print("\n".join(map(str, results[:k])))


### FIXED CODE ###

import numpy as np
x, y, z, k = map(int, input().split())
k = min(x * y * z, k)
a = np.array(list(map(int, input().split())))
b = np.array(list(map(int, input().split())))
c = np.array(list(map(int, input().split())))

ab = np.ravel(a + b[:, None])
ab.sort()
abc = np.ravel(c + ab[-k:, None])
abc.sort()
print(np.sum(abc[-k:][::-1].astype(str).astype(object) + "\n"), end="")
### BUGGY CODE ###

import bisect

n=int(input())
a=[int(input()) for i in range(n)]

c=0
b=[]
for i in range(n):
  p=bisect.bisect_left(b,a[i])
  if p==0:
    b.insert(0,a[i])
    c += 1
  else:
    b[p-1]=a[i]

print(c)


### FIXED CODE ###

import bisect

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

B=[]
c=0
for a in A:
  p=bisect.bisect_right(B,a)
  if p==c:
    B.append(a)
    c += 1
  else:
    B[p]=a

print(len(B))
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
s=sum(a[0:k])
for i in range(1,n-k+1):
    ns=sum(a[i:k+i])
    if ns>s:
        print("Yes")
    else:
        print("No")
    s=ns

### FIXED CODE ###

import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(0,n-k):
    if a[i]<a[i+k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
book = {}
array = [int(i) for i in input().split()]

for i in array:
    book[i] = book.get(i, 0) + 1

for i in range(n):
    s = 0
    for k, v in book.items():
        if k == array[i]:
            v -= 1
        s += (v * (v - 1)) // 2 if v > 0 else 0
    print(s)


### FIXED CODE ###

n = int(input())
book = {}
array = [int(i) for i in input().split()]

for i in array:
    book[i] = book.get(i, 0) + 1

sum_val = 0
delta = {}
for k, v in book.items():
    t = (v * (v - 1)) // 2 if v > 0 else 0
    sum_val += t
    u = v - 1
    delta[k] = t - (u * (u - 1)) // 2 if u > 0 else 0

for i in range(n):
    print(sum_val - delta[array[i]])
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]

b_check = [0] * n
for i,j in enumerate(sorted(b)):
    for k,l in enumerate(sorted(c)):
        if l > j:
            b_check[i] = n - k
            break
            
ans = 0
for i,j in enumerate(sorted(a)):
    for k,l in enumerate(sorted(b)):
        if l > j:
            ans += sum(b_check[k:n])
            break
print(ans)

### FIXED CODE ###

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

a = sorted(a)
b = sorted(b)
c = sorted(c)

import bisect
count = 0
for i in b:
    a_count = bisect.bisect_left(a, i)
    c_count = n - bisect.bisect_right(c, i)
    count += a_count * c_count
    
print(count)
### BUGGY CODE ###

def knapsack(W,v,w,n,d):
    
    if n<0:
        return 0
    
    if d[W][n]!=-1:
        return d[W][n]
    if w[n]>W:
        d[W][n]=knapsack(W,v,w,n-1,d)
        return d[W][n]
    else:
        d[W][n]=max(v[n]+ knapsack(W-w[n],v,w,n-1,d),knapsack(W,v,w,n-1,d))
        return d[W][n]


q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  



d=[[-1 for j in range(n+1)] for i in range(W+1)]
print(knapsack(W,v,w,n-1,d))


### FIXED CODE ###

def knapSack(W, wt, val, n): 
	K = [[0 for x in range(W+1)] for x in range(n+1)] 

	
	for i in range(n+1): 
		for w in range(W+1): 
			if i==0 or w==0: 
				K[i][w] = 0
			elif wt[i-1] <= w: 
				K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]) 
			else: 
				K[i][w] = K[i-1][w] 

	return K[n][W] 




q=list(map(int,input().split()))
n=q[0]
W=q[1]
v=[0]*n
w=[0]*n
for _ in range(n):
  r=list(map(int,input().split()))
  w[_]=r[0]
  v[_]=r[1]
  




print(knapSack(W,w,v,n))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, u, v = [int(i) for i in input().split()]
u -= 1
v -= 1
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

uu = [0] * n
vv = [0] * n


def dfs(ve, r=u, d=0, rr=-1):
    ve[r] = d
    for i in e[r]:
        if i == rr:
            continue
        dfs(ve, i, d + 1, r)


dfs(uu, u)
dfs(vv, v)


ans = 0
for i, j in zip(uu, vv):
    if i <= j:
        ans = max(ans, j)
print(ans-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n, u, v = [int(i) for i in input().split()]
u -= 1
v -= 1
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i)-1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

uu = [0] * n
vv = [0] * n


def dfs(ve, r=u, d=0, rr=-1):
    ve[r] = d
    for i in e[r]:
        if i == rr:
            continue
        dfs(ve, i, d + 1, r)


dfs(uu, u)
dfs(vv, v)


ans = 0
for i, j in zip(uu, vv):
    if i <= j:
        ans = max(ans, j)
print(ans-1)
### BUGGY CODE ###

from collections import deque
n=int(input())
p= list(map(int, input().split()))

# 迷路　BFS
def bfs(sx,sy):
    d = deque()
    d.append((sx, sy,distance[sx][sy]))
    ans=distance[sx][sy]
    v=distance[sx][sy]
    check[sx][sy]=0

    while len(d):
        x, y,dis = d.popleft()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

            if 0 <= nx < n and 0 <= ny < n:
                # 更新できるマスは更新
                if distance[nx][ny]>dis:
                    distance[nx][ny]=dis
                    d.append((nx, ny,dis+check[nx][ny]))

    return ans

distance = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        distance[i][j]+=min(i,j,n-i-1,n-j-1)
check = [[1]*n for i in range(n)]


anss=0
for i in p:
    x=(i-1)//n
    y=(i-1)%n
    anss+=bfs(x,y)

print(anss)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

distance = [[min(i, j, n - i - 1, n - j - 1) for i in range(n)] for j in range(n)]
check = [[1] * n for i in range(n)]
p = [((i - 1) // n, (i - 1) % n) for i in p]

def move(x,y,nx,ny):
    if distance[nx][ny] > distance[x][y] + check[x][y]:
        distance[nx][ny] = distance[x][y] + check[x][y]
        d.append((nx,ny))

ans = 0
for i, j in p:
    ans += distance[j][i]
    d=[]
    d.append((j,i))
    check[j][i] = 0
    while len(d):
        x, y = d.pop()
        if x!=0:
            move(x,y,x-1,y)
        if x!=n-1:
            move(x,y,x+1,y)
        if y!=0:
            move(x,y,x,y-1)
        if y!=n-1:
            move(x,y,x,y+1)

print(ans)
### BUGGY CODE ###

import heapq
import bisect

S = input()
T = input()
lenS = len(S)
lenT = len(T)
F1 = [False]*26
F2 = [False]*26
alpha = 'abcdefghijklmnopqrstuvwxyz'
for i in range(lenS):
    F1[alpha.index(S[i])] = True
for i in range(lenT):
    F2[alpha.index(T[i])] = True
for i in range(26):
    if not F1[i] and F2[i]:
        print(-1)
        exit()

ind = S.index(T[0])
ans = ind+1
for i in range(1,lenT):
    S = S[ind+1:] + S[:ind+1]
    ind = S.index(T[i])
    ans += ind+1

print(ans)

### FIXED CODE ###

from collections import*
from bisect import*
s=input()
n=len(s)
t=input()
d=defaultdict(list)
for i,c in enumerate(s):
    d[c].append(i)
m=-1
o=0
for c in t:
    if not d[c]:
        print(-1)
        exit()
    i=bisect(d[c],m)
    if len(d[c])==i:
        o+=1
        m=d[c][0]
    else:
        m=d[c][i]
print(o*n+m+1)
### BUGGY CODE ###

N = int(input())
pwr = 1
for i in range(1, N+1):
    pwr *= i
print(pwr % 1000000007)

### FIXED CODE ###

N = int(input())
pwr = 1
for i in range(1, N+1):
    pwr *= i
    pwr = pwr % 1000000007
print(pwr)
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
for n in range(N):
  for m in range(n+1, N):
    p += X[n]*X[m]
  if p >= 10**9 + 7:
     p = p % (10**9 + 7)
      
      #while p >= 10**9 + 7:
        #p -= 10**9 + 7
      
print(p)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
p = 0
s = sum(X)
for n in range(N):
  s -= X[n] 
  s = s % (10**9 + 7)
  p += s * X[n]
  p = p % (10**9 + 7)

print(p)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
items = []
ap = items.append
a_sum =0
b_sum = 0
for i in range(N):
    a, b, c = map(int, input().split())
    ap((a, b, c))
    a_sum += a
    b_sum += b

inf = float("inf")
dp = [[[inf for _ in range(b_sum + 10)] for _ in range(a_sum + 10)] for i in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
    for a in range(a_sum):
        for b in range(b_sum):
            if dp[i + 1][a][b] > dp[i][a][b]:
                dp[i + 1][a][b] = dp[i][a][b]
            if dp[i + 1][a + items[i][0]][b + items[i][1]] > dp[i][a][b] + items[i][2]:
                dp[i + 1][a + items[i][0]][b + items[i][1]] = dp[i][a][b] + items[i][2]

ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            if ans > dp[N][a][b]:
                ans = dp[N][a][b]
if ans != inf:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
items = []
for i in range(N):
    a, b, c = map(int, input().split())
    items.append((a, b, c))

a_sum = sum([item[0] for item in items])
b_sum = sum([item[1] for item in items])
inf = float("inf")
dp = [[[inf for _ in range(a_sum + 100)] for _ in range(b_sum + 100)] for i in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for a in range(a_sum + 1):
        for b in range(b_sum + 1):
            dp[i + 1][a][b] = min(dp[i + 1][a][b], dp[i][a][b])
            dp[i + 1][a + items[i][0]][b + items[i][1]] = min(dp[i + 1][a + items[i][0]][b + items[i][1]],
                                                              dp[i][a][b] + items[i][2])
ans = inf
for a in range(1, a_sum + 1):
    for b in range(1, b_sum + 1):
        if a * Mb == b * Ma:
            ans = min(ans, dp[N][a][b])
if ans != inf:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

B = [bin(a)[2:].zfill(61)[::-1] for a in A]
N1 = []
for i in range(0,61):
    m = 0
    for b in B:
        if b[i] == "1":
            m += 1
    N1.append(m)

ans = 0
for i,n1 in enumerate(N1):
    n0 = N-n1
    m = n0 * n1
    ans += 2**i * m
    ans = ans % MOD
print(ans % MOD)






### FIXED CODE ###

MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

#B = [bin(a)[2:].zfill(61)[::-1] for a in A]
N1 = []
for i in range(0,61):
    m = sum([a % 2 for a in A])
    N1.append(m)
    for j in range(N):
        A[j] = A[j] >> 1

ans = 0
for i,n1 in enumerate(N1):
    n0 = N-n1
    m = n0 * n1
    ans += 2**i * m
    ans = ans % MOD
print(ans % MOD)
### BUGGY CODE ###

s=raw_input()
n=len(s)
cnt=[[0]*26 for _ in xrange(n+1)]
for i in xrange(n):
    for j in xrange(26):
        cnt[i+1][j]=cnt[i][j]
    cnt[i+1][ord(s[i])-ord("a")]+=1
if n==2:
    if s[0]==s[1]:
        print 1,2
        quit()
    else:
        print -1,-1
        quit()
for i in xrange(n):
    for j in xrange(i+3,n+1):
        max_cnt=0
        for k in xrange(26):
            max_cnt=max(max_cnt,cnt[j][k]-cnt[i][k])
        if (j-i)/2<max_cnt:
            print i+1,j
            quit()
print -1,-1

### FIXED CODE ###

s=raw_input()
n=len(s)
if n==2:
    if s[0]==s[1]:
        print 1,2
        quit()
    else:
        print -1,-1
        quit()
for i in xrange(n-2):
    if s[i]==s[i+1] or s[i]==s[i+2] or s[i+1]==s[i+2]:
        print i+1,i+3
        quit()
print -1,-1
### BUGGY CODE ###

import functools
import operator

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

i = 2
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  while i <= P**1/N:
    while P % i**N == 0:
      P /= i**N
      res.append(i)
    else:
      if i == 2:
        i += 1
      else:
        i += 2
  res.append(1)
  result = functools.reduce(operator.mul, res)
  print(result)
  exit()

### FIXED CODE ###

N,P = map(int,input().split())
i = round(P**(1/N))
res = []
if N == 1:
  print(P)
elif P == 1:
  print(1)
else:
  for i in range(i,0,-1):
    if P%i**N==0:
      print(i)
      break
### BUGGY CODE ###

import heapq as hq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [tuple(map(int, input().split())) for _ in range(M)]

hq.heapify(A)
for b, c in BC:
    for i in range(b):
        a = hq.heappop(A)
        if a < c:
            hq.heappush(A, c)
        else:
            hq.heappush(A, a)
            break

print(sum(A))

### FIXED CODE ###

import heapq as hq

N, M = map(int, input().split())
A = [int(a) for a in input().split()]
BC = [tuple(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)

hq.heapify(A)
for b, c in BC:
    for i in range(b):
        a = hq.heappop(A)
        if a < c:
            hq.heappush(A, c)
        else:
            hq.heappush(A, a)
            break

print(sum(A))
### BUGGY CODE ###

def func_R(li, s, hi):
    for wi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi-1] + 1

def func_L(li, s, hi):
    for wi, si in enumerate(s[::-1]):
        wi = w - wi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if wi == w-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi][wi+1] + 1

def func_U(li, s, wi):
    for hi, si in enumerate(s):
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == 0:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi-1][wi] + 1

def func_D(li, s, wi):
    for hi, si in enumerate(s[::-1]):
        hi = h - hi - 1
        if si == '#':
            li[hi][wi] = 0
        else:
            if hi == h-1:
                li[hi][wi] = 1
            else:
                li[hi][wi] = li[hi+1][wi] + 1

def main():
    import sys
    input = sys.stdin.readline
    global h, w
    h, w = map(int, input().split())
    L = [[0]*w for _ in range(h)]
    R = [[0]*w for _ in range(h)]
    U = [[0]*w for _ in range(h)]
    D = [[0]*w for _ in range(h)]
    s_list = ['']*w
    for hi in range(h):
        s = input()[:-1]
        func_L(L, s, hi)
        func_R(R, s, hi)
        for wi, si in enumerate(s):
            s_list[wi] += si

    for wi in range(w):
        s = s_list[wi]
        func_U(U, s, wi)
        func_D(D, s, wi)

    ans = 0
    for hi in range(h):
        for wi in range(w):
            ans = max(ans, L[hi][wi] + R[hi][wi] + U[hi][wi] + D[hi][wi])

    print(ans-3)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import numpy as np

def main():
    H, W = map(int, input().split())
    S = np.array([list(input()) for _ in range(H)]) == '.'

    L = np.zeros((H, W), dtype=int)
    R = np.zeros((H, W), dtype=int)
    U = np.zeros((H, W), dtype=int)
    D = np.zeros((H, W), dtype=int)

    for w in range(1, W):
        L[:, w] = (L[:, w-1] + 1) * S[:, w-1]
    for w in range(W-2, -1, -1):
        R[:, w] = (R[:, w+1] + 1) * S[:, w+1]
    for h in range(1, H):
        U[h, :] = (U[h-1, :] + 1) * S[h-1, :]
    for h in range(H-2, -1, -1):
        D[h, :] = (D[h+1, :] + 1) * S[h+1, :]

    print(((L+R+U+D)*S).max() + 1)

if __name__ == '__main__':
    main()
### BUGGY CODE ###


import math


def main():
    N = int(input())
    A = [int(arg) for arg in input().split()]
    ans = 1
    for i in range(N):
        ans *= A[i]

    if ans > pow(10, 18):
        print("-1")
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N = int(input())
    A = [int(arg) for arg in input().split()]
    ans = 1

    for i in range(N):
        if A[i] == 0:
            print(0)
            return

    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            return

    print(ans)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = input()
all_int = list()
ans = 0
for i in range(len(n)):
    for j in range(i+1,len(n)+1):
        s = n[i:j]
        if(int(s) > 0 and len(s)>=4 and int(s)%2019 == 0):
            ans += 1
print(ans)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

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

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

list1, list2 = [1], [1]
try:
    list1.extend([i for i in range(1+1, A+1) if A % i == 0
    and is_prime(i) == True])
    list2.extend([i for i in range(1+1, B+1) if B % i == 0
    and is_prime(i) == True])
except:
    pass

print(len(set(list1) & set(list2)))

### FIXED CODE ###

A, B = map(int, input().split())
 
def gcd(a, b):  # a,bの最大公約数
    while b:
        a, b = b, a % b
    return a

def factorization(n):  # nを素因数分解
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1): 
        if temp % i == 0: # 割り切れるとき
            cnt = 0
            while temp % i == 0: # 割れる限りカウント
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1: # まだ因数があるとき
        arr.append([temp, 1])
    if arr == []: # ｎが1のとき
        arr.append([n, 1])
    return arr
 
g = gcd(A, B) 
ans = len(factorization(g))

if g != 1:
    ans += 1
print(ans)
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
hs = [int(x) for x in input().split()]
dp = [0 for _ in range(n+1)]
for i in range(2, n + 1):
    mn = 10**10
    minIndex = max(1, i - k)
    for j in range(minIndex, i):
        v = dp[j] + abs(hs[i-1] - hs[j-1])
        mn = min(mn, v)
    dp[i] = mn
print(dp[n])


### FIXED CODE ###

n, k = [int(x) for x in input().split()]

hs = [int(x) for x in input().split()]

dp = [0] * n

for i in range(1, min(k,n)):
	dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[:i], hs[:i])])

if k < n:
	for i in range(k, n):
		dp[i] = min([dpj + abs(hs[i] - hj) for dpj, hj in zip(dp[i-k:i], hs[i-k:i])])

print(dp[-1])
### BUGGY CODE ###

N = int(input())
k = []
for _ in range(N):
    k.append(input())
    x = set(k)
print (len(x))

### FIXED CODE ###

N = int(input())
k = set()
for _ in range(N):
    k.add(input())
print (len(k))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(1, N):
    ans += A[i - 1] * sum(A[i:])
print(ans % (10**9 + 7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
s = sum(A) % mod
ans = 0
for i in range(N):
    s -= A[i]
    if 0 > s:
        s += mod
    ans += A[i] * s
    ans %= mod
print(ans)
### BUGGY CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
while(count < M):
  min_A = A[0]
  B_min = B[0]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    del A[0]
    del B[0]


### FIXED CODE ###

def unzip(li):
  return map(list, zip(*li))

N, M = map(int, input().split())
tmp_C = [0 for i in range(N)]

for i in range(N):
  a,b = map(int, input().split())
  tmp_C[i] = (a,b)
  
C = sorted(tmp_C)
A, B = unzip(C)
ans = 0
count = 0
cur = 0
while(count < M):
  min_A = A[cur]
  B_min = B[cur]
  if count + B_min >= M:
    print(ans + min_A * (M - count))
    break
  else:
    ans += min_A * B_min
    count += B_min
    cur += 1