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

# dpぽい気がするのでそうする
# なぜかREなる....
# pythonだとrecursion limitがアレなのを忘れていた...

import sys

sys.setrecursionlimit(10 ** 8)


s = input()
dp = {}


def rec(i, cur_g, cur_p, tmp):
    if i in dp:
        return dp[i]
    if i == len(s):
        ret = 0
        for j in range(len(s)):
            if tmp[j] == "p" and s[j] == "g":
                ret += 1
            elif tmp[j] == "g" and s[j] == "p":
                ret -= 1
        dp[i] = ret
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        ret = max(
            rec(i + 1, cur_g, cur_p + 1, tmp + "p"),
            rec(i + 1, cur_g + 1, cur_p, tmp + "g"),
        )
        dp[i] = ret
        return ret

    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        ret = rec(i + 1, cur_g + 1, cur_p, tmp + "g")
        dp[i] = ret
        return ret


print(rec(0, 0, 0, ""))


### FIXED CODE ###

# dpぽい気がするのでそうする
# なぜかREなる....
# pythonだとrecursion limitがアレなのを忘れていた...
# なぜかTLEなる....

import sys

sys.setrecursionlimit(10 ** 8)


s = input()
dp = {}


def rec(i, cur_g, cur_p, g, p):
    if i in dp:
        return dp[i]
    if i == len(s):
        ret = p - g
        dp[i] = ret
        return ret
    if cur_g > cur_p:
        # パーを出せる（出さなくてもいい）
        if s[i] == "g":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p + 1),
                rec(i + 1, cur_g + 1, cur_p, g, p),
            )
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = max(
                rec(i + 1, cur_g, cur_p + 1, g, p),
                rec(i + 1, cur_g + 1, cur_p, g + 1, p),
            )
            dp[i] = ret
            return ret
    else:
        # 勝てるかどうかにかかわらずグーを出すしか無い
        if s[i] == "g":
            ret = rec(i + 1, cur_g + 1, cur_p, g, p)
            dp[i] = ret
            return ret
        elif s[i] == "p":
            ret = rec(i + 1, cur_g + 1, cur_p, g + 1, p)
            dp[i] = ret
            return ret


print(rec(0, 0, 0, 0, 0))
### BUGGY CODE ###

N, C = map(int, input().split())
X = []
V = []
for _ in range(N):
  x, v = map(int, input().split())
  X.append(x)
  V.append(v)

A = [0] * (N + 1)
A_max = [0] * (N + 1)
B = [0] * (N + 1)
B_max = [0] * (N + 1)
a_sum = 0
b_sum = 0
for i in range(N):
  a_sum += V[i]
  A[i + 1] = a_sum- X[i]
  A_max[i + 1] = max(A)
  b_sum += V[- i - 1]
  B[i + 1] = b_sum - (C - X[- i - 1])
  B_max[i + 1] = max(B)

X = [0] + X
V = [0] + V

m = max(0, A_max[-1], B_max[-1])
for i in range(1, N + 1):
  m = max(m, A[i] + B_max[N - i] - X[i], B[i] + A_max[N - i] - (C - X[N - i + 1]))

print(m)

### FIXED CODE ###

N, C = map(int, input().split())
X = []
V = []
for _ in range(N):
  x, v = map(int, input().split())
  X.append(x)
  V.append(v)

A = [0] * (N + 1)
A_max = [0] * (N + 1)
B = [0] * (N + 1)
B_max = [0] * (N + 1)
a_sum = 0
b_sum = 0
for i in range(N):
  a_sum += V[i]
  A[i + 1] = a_sum - X[i]
  A_max[i + 1] = max(A_max[i], A[i + 1])
  b_sum += V[- i - 1]
  B[i + 1] = b_sum - (C - X[- i - 1])
  B_max[i + 1] = max(B_max[i], B[i + 1])

X = [0] + X
V = [0] + V

m = max(0, A_max[-1], B_max[-1])
for i in range(1, N + 1):
  m = max(m, A[i] + B_max[N - i] - X[i], B[i] + A_max[N - i] - (C - X[N - i + 1]))

print(m)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))

mod=10**9+7
sum_all=[]
for i in range(N-1):
    for j in range(i+1,N):
        A[i]=A[i]%mod
        A[j]=A[j]%mod
        sum_all.append((A[i])*(A[j]))

sum=0
for n in sum_all:
    sum+=n%mod
print(sum%mod)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))

mod=10**9+7

B=[0]
for i in range(1,N+1):
    B.append(A[i-1]+B[i-1])

ans=0
for i in range(N-1):
    ans+=A[i]*(B[N]-B[i+1])
    ans%=mod

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

n, w = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]

dp = [0]*(w + 1)
for i in range(n):
    for j in range(w + 1)[::-1]:
        if j - info[i][0] < 0:
            break
        else:
            dp[j] = max(dp[j], dp[j - info[i][0]] + info[i][1])
print(dp[w])

### FIXED CODE ###

n,w = map(int,input().split())
info = [[0,0]]+[list(map(int,input().split())) for i in range(n)]

## dp[i][j]:i番目までのアイテムを重さjのナップサックに詰めるときの最大価値
dp = [[0]*(w+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(w+1):
    if j-info[i][0]>=0:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-info[i][0]]+info[i][1])
    else:
      dp[i][j] = dp[i-1][j]

print(dp[n][w])
### BUGGY CODE ###

# encoding: utf-8
N, X = map(int, input().split())
dx = list(map(lambda x: x - X, map(int, input().split())))

dx_nearest = 10**9
for dxi in dx:
    if (2 *(dxi > 0) - 1) * dxi < dx_nearest: dx_nearest = (2 *(dxi > 0) - 1) * dxi

for D in range(dx_nearest + 1)[::-1]:
    for dxi in dx:
        if dxi % D > 0: break
        else: continue
    else:
        print(D)
        break
else: print("oops")

### FIXED CODE ###

# encoding: utf-8
import math

N, X = map(int, input().split())
x = sorted(list(map(int, input().split())) + [X])

def gcf2(a, b):
    if b == 0: return a
    else: return gcf2(b, (a % b))

# Greatest common factor
# print(x)
GCF = x[1] - x[0]
x_min = x[0]
for i, xi in enumerate(x):
    if i == 0: continue
    GCF = gcf2(GCF, (xi - x_min))

print(GCF)
### BUGGY CODE ###

k, s = map(int, input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                cnt += 1

print(cnt)

### FIXED CODE ###

k, s = map(int, input().split())
cnt = 0

for x in range(k+1):
    for y in range(k+1):
        if x + y <= s <= x + y + k:
            cnt += 1

print(cnt)
### BUGGY CODE ###

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

arr = []
for i in range(len(s)):
  for j in range(i+1,len(s)):
    for k in range(j+1, len(s)):
      if (s[i] != s[j]) & (s[i] != s[k]) & (s[j] != s[k]):
        arr.append((i,j,k))

sum = 0
for l in range(len(arr)):
  if abs(arr[l][1] - arr[l][0]) != abs(arr[l][2] - arr[l][1]):
    sum += 1
print(sum)


### FIXED CODE ###

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

arr = []
R = len(list(filter(lambda x:x == 'R', s)))
G = len(list(filter(lambda x:x == 'G', s)))
B = len(list(filter(lambda x:x == 'B', s)))
tot = R*G*B

for i in range(n):
  for j in range(i+1, n):
    k = 2*j-i
    if k >= n:
      continue
    if (s[i] != s[j]) and (s[i] != s[k]) and (s[j] != s[k]):
      tot -= 1

print(tot)
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
s = np.array(s)
s = (s == ".") * 1
def neext(a):
    l, m = a[0], a[1]
    return [(l, m+1), (l, m-1), (l+1, m), (l-1, m)]
def solve(i, j):
    if s[i][j] == 0:
        return 0
    else:
        pre = 0
        p = np.full_like(s, -1)
        check = deque([((-1, -1), (i, j), 0)])#(from,now, dist)
        while check:
            From, now, d = check.popleft()
            p[now[0]][now[1]] = d
            pre = max(pre, d)
            for b, c in neext((now[0], now[1])):
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                if (b == From[0] and c == From[1]) or p[b][c] != -1 or s[b][c] == 0:
                    continue
                else:
                    check.append(((i, j), (b, c), d + 1))
        return pre
ans = 0
for H in range(len(s)):
    for W in range(len(s[0])):
        ans = max(ans, solve(H, W))
print(ans)

### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(len(s)):
    for j in range(len(s[0])):
        if s[i][j] == '#':
            continue
        pre = 0
        p = np.full((h, w), -1)
        p[i][j] = 0
        check = deque([((i, j), 0)])#(from,now, dist)
        while check:
            now, d = check.popleft()
            pre = max(pre, d)
            for k, l in [(1,0), (-1,0),(0,1), (0,-1)]:
                b = now[0] + k
                c = now[1] + l
                if b < 0 or c < 0 or b >= h or c >= w:
                    continue 
                elif p[b][c] == -1 and s[b][c] != '#':
                    check.append(((b, c), d + 1))
                    p[b][c] = d + 1
        ans = max(ans, pre)

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

s = input()
q = int(input())
for i in range(q):
    t = input()
    if len(t) == 1:
        s = s[::-1]
    else:
        _, a, b = (str(i) for i in t.split())
        if a == "1":
            s = b + s
        elif a == "2":
            s = s + b

print(s)

### FIXED CODE ###

def main():
    s = input()
    q = int(input())
    flag = 0
    cnt = 0
    front = []
    back = []

    for i in range(q):
        t = input()
        if len(t) == 1:
            cnt += 1
            if flag == 0:
                flag = 1
            elif flag == 1:
                flag = 0
        else:
            _, a, b = (str(i) for i in t.split())
            if a == "1":
                if flag == 0:
                    front.append(b)
                elif flag == 1:
                    back.append(b)
            elif a == "2":
                if flag == 0:
                    back.append(b)
                elif flag == 1:
                    front.append(b)

    if cnt % 2 == 0:
        front = front[::-1]
        s = ''.join(front) + s + ''.join(back)
    else:
        back = back[::-1]
        s = ''.join(back) + s[::-1] + ''.join(front)

    print(s)

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

n, w = map(int, input().split())
W = [0] * n
V = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    W[i] = a
    V[i] = b


dp = [[0] * (10 ** 5 + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_num in range(w + 1):
        if sum_num - W[i] >= 0:
            dp[i + 1][sum_num] = max(dp[i][sum_num - W[i]] + V[i], dp[i][sum_num])
        else:
            dp[i + 1][sum_num] = dp[i][sum_num]

print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
W = [0] * n
V = [0] * n
for i in range(n):
    a, b = map(int, input().split())
    W[i] = a
    V[i] = b


dp = [[0] * (10 ** 5 + 10) for _ in range(n + 10)]
for i in range(n):
    for sum_num in range(w + 1):
        if sum_num - W[i] >= 0:
            dp[i + 1][sum_num] = max(dp[i][sum_num - W[i]] + V[i], dp[i][sum_num])
        else:
            dp[i + 1][sum_num] = dp[i][sum_num]

print(dp[n][w])
### BUGGY CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
ans = 0
if x_max >= a:
    dp = [[[0 for k in range(x_sum + 1)] for j in range(n + 1)] for i in range(2)]
    dp[0][0][0] = 1
    for i in range(1, n + 1):
        idx = i % 2
        for j in range(n + 1):
            for k in range(x[i - 1]):
                dp[idx][j][k] = dp[1 - idx][j][k]
            if j > 0:
                for k in range(x[i - 1], x_sum + 1):
                    dp[idx][j][k] = dp[1 - idx][j][k] + dp[1 - idx][j - 1][k - x[i - 1]]

    for j in range(1, min(x_sum // a + 1, n + 1)):
        ans += dp[idx][j][j * a]
print(ans)


### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(x)
x_sum = sum(x)
ans = 0
if x_max >= a:
    dp = [[0 for j in range(2 * x_sum + 1)] for i in range(2)]
    dp[0][x_sum] = 1
    for i in range(1, n + 1):
        idx = i % 2
        y = x[i - 1] - a
        for j in range(2 * x_sum + 1):
            if 0 <= j - y <= 2 * x_sum:
                dp[idx][j] = dp[1 - idx][j] + dp[1 - idx][j - y]
            else:
                dp[idx][j] = dp[1 - idx][j]
    ans = dp[n % 2][x_sum] - 1
print(ans)
### BUGGY CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
s=1
pres=0
while s!=pres:
    pres=s
    for l,r,c in LRC:
        if l<=s<r:
            s=max(s,r)
    if s==N:
        break
else:
    print(-1)
    exit()
stack=[[0,-1]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
while stack:
    m,a=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for l,r,c in LRC:
            if l<=a<r:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r])
else:
    print(-1)


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import time
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))

N,M=map(int,input().split())
LRC=[list(map(int,input().split())) for i in range(M)]
LRC.sort()


stack=[[0,-1,0]]
idle_max=10**18
visited=[idle_max for i in range(N+1)]
visited2=[0 for i in range(N+1)]
visited[1]=0
x=0
while stack:
    #print(stack)
    m,a,p=heappop(stack)
    a=-a
    if a==N:
        print(m)
        break
    if not visited2[a]:
        visited2[a]=1
        for i in range(x,M):
            l,r,c=LRC[i]
            x=i
            if l<=a:
                _m=m+c
                if _m<visited[r]:
                    visited[r]=_m
                    heappush(stack,[_m,-r,a+1])
            else:
                break
else:
    print(-1)
### BUGGY CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    cnt = 0
    for w in range(W):
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        left[h][w] = cnt

for h in range(H):
    cnt = 0
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        right[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H):
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        up[h][w] = cnt

for w in range(W):
    cnt = 0
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            cnt += 1
        else:
            cnt = 0
        down[h][w] = cnt

ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in a[1:]:
  ans = ans*i
if ans > 10**18:
	print(-1)
else:
  	print(ans)

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int, input().split()))
if 0 in a:
  print(0)
  sys.exit()
ans = a[0]
for i in a[1:]:
    ans = ans*i
    if ans > 10**18:
        print(-1)
        break
else:
  	print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
ab = []
for i in range(M):
    a, b = map(int, input().split())
    if a == 1 or b == N:
        ab.append([int(a), int(b)])

flag = False
for i in range(len(ab)):
    for k in range(len(ab)):
        if ab[i][1] == ab[k][0] or ab[i][0]==ab[k][1]:
            print('POSSIBLE')
            flag = True
            break
    if flag:
        break
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

#真に大切なのは中間点となる要素
N, M = map(int, input().split())
an = set()
nb = set()
for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        an.add(b)
    elif b == N:
        nb.add(a)

print('IMPOSSIBLE' if len(an&nb)==0 else 'POSSIBLE')
### BUGGY CODE ###

import re
N = int(input())
S = input()
ans = 0
tmp = [[m.start() for m in re.finditer(str(i), S)] for i in range(10)]
for i in range(10):
  if len(tmp[i]) == 0:
    continue
  for j in range(10):
    if len(tmp[j]) == 0:
      continue
    for k in range(10):
      if len(tmp[k]) == 0:
        continue
      l = tmp[i][0]
      r = tmp[k][-1]
      for m in range(l+1, r):
        if m in tmp[j]:
          ans += 1
          break
print(ans)

### FIXED CODE ###

import re
N = int(input())
S = input()
ans = 0
tmp = [[m.start() for m in re.finditer(str(i), S)] for i in range(10)]
for i in range(10):
  if len(tmp[i]) == 0:
    continue
  for j in range(10):
    if len(tmp[j]) == 0:
      continue
    for k in range(10):
      if len(tmp[k]) == 0:
        continue
      l = tmp[i][0]
      flag = True
      for m in tmp[j]:
        if m > l:
          flag = False
          break
      if flag:
        continue
      for n in tmp[k]:
        if n > m:
          ans += 1
          break
print(ans)
### BUGGY CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(0,n):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

print(ans)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

ans = r * g * b

for i in range(0,n-2):
    for j in range(1,int((n-i)/2)+1):
        if i + j + j <= n-1:
            if s[i] != s[i+j] and s[i] != s[i+j+j] and s[i+j] != s[i+j+j] :
                ans = ans - 1

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

K,S=map(int,input().split())
if 2<=K<=2500 and 0<=S<=3*K:
    Ks=[]
    wa=[]
    for i in range(K+1):
        Ks.append(i)
    X,Y,Z =Ks,Ks,Ks
    for x in X:
        if x<=S:
            X_=[]
            X_.append(x)
            for y in Y:
                X_Y_=[]
                X_Y_=X_.copy()
                X_Y_.append(y)
                for z in Z:
                    X_Y_Z_=X_Y_.copy()
                    X_Y_Z_.append(z) 
                    wa_=sum(X_Y_Z_)
                    wa.append(wa_)
    print(len([c for c in wa if c==S]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
K,S=map(int,input().split())
count=0
for x in range(K+1):
    for y in range(K+1):
        if S-(x+y)>=0 and S-(x+y)<=K: count+=1
print(count)
### BUGGY CODE ###

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 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

n, k  = MAP()
p = LIST()

def kitai(a):
    tmp = 0
    # for a in A:
    tmp = 1/a * (1/2 * a * (a+1))
    return tmp
    

ans = 0
# A = []
B = []
for i in range(n-k+1):
    A = p[i:i+k]
    B.append(A)
for A in B:
    k = 0
    for a in A:
        # print(a)
        k += kitai(a)
    ans = max(ans, k)
print(ans)







### FIXED CODE ###

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 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

n, k  = MAP()
p = LIST()

def kitai(a):
    tmp = 0
    # for a in A:
    tmp = 1/a * (1/2 * a * (a+1))
    return tmp
    
ans = 0
max_index = 0
# left = 0
# right = k
max_ruiseki = sum(p[0:k])
now_ruiseki = 0
ruiseki = [max_ruiseki]
for left in range(n-k+1):
    if left != 0:
        right = k + left 
        # print(left-1, p[left-1])
        
        # print(right-1 ,p[right-1])
        new_ruiseki = ruiseki[left-1] + p[right-1] - p[left-1]
        ruiseki.append(new_ruiseki)

# print(ruiseki)
m = 0
max_index = 0
for i in range(len(ruiseki)):
    if m != max(m, ruiseki[i]):
        m = ruiseki[i]
        index = i

# print(index)

A = p[index:index+k]
    # now_ruiseki = max_ruiseki
for a in A:
    ans += kitai(a)
print(ans)

    



# next_ruiseki = 0
# for i in range(n-k+1):
#     next_ruiseki = ruiseki    
#     ruiseki = max(ruiseki)


    # A
    # A = p[i:i+k]
    # if c != max(c, sum(A)):
    #     c = sum(A)
    #     C = deepcopy(A)
# for a in C:
#     ans += kitai(a)
# print(ans)
### BUGGY CODE ###

S = input()
T = input()
lenS = len(S)
lenT = len(T)

dp = [[0]*(lenS+1)for _ in range(lenT+1)]
for i in range(1,lenT+1):
  t = T[i-1]
  for j in range(1,lenS+1):
    s = S[j-1]
    if s==t:
      dp[i][j]=dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
      
ans = ""
m=lenT
n=lenS
while m and n:
  if dp[m][n] == dp[m-1][n]:
    m = m-1
  elif dp[m][n] == dp[m][n-1]:
    n = n-1
  else:
    m = m-1
    n = n-1
    ans = "".join([S[n],ans])
print(ans)

### FIXED CODE ###

# LongestCommonSubsequences
import numpy as np
S = np.array([ord(i)-97 for i in input()], dtype=int)
T = np.array([ord(i)-97 for i in input()], dtype=int)
Ns = len(S)
Nt = len(T)
equal = np.equal.outer(S, T).astype(int)

dp = [np.zeros(Nt + 1, dtype=int)]
for i in range(Ns):
    x = dp[-1].copy()
    newDP = x.copy()
    newDP[1:] = np.maximum(x[:-1] + equal[i], newDP[1:])
    np.maximum.accumulate(newDP, out=newDP)
    dp.append(newDP)


ans = ""
i, j = Ns, Nt
while i > 0 and j > 0:
    if S[i-1] == T[j-1]:
        ans += chr(S[i-1]+97)
        i -= 1
        j -= 1
        continue
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    else:
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

import math

K = int(input())

total = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += math.gcd(math.gcd(a,b),c)

print(total)  

### FIXED CODE ###

from math import gcd
 
K = int(input())
 
total = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += gcd(gcd(a,b),c)

print(total)