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

n,m  =map(int,input().split())
lm = []
for _ in range(n):
    lm.append(list(map(int,input().split())))
s = 0
mon = 0
lm.sort()
 
while s + lm[0][1] < m:
    s += lm[0][1]
    mon += lm[0][1]*lm[0][0]
    lm = lm[1::]
if s +lm[0][1] >= m:
    mon += lm[0][0]*(m-s)
    
print(mon)

### FIXED CODE ###

N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]
 
AB.sort()
Ans = 0
for i in AB:
  if i[1] >= M:
    Ans += i[0] * M
    break
  else:
    Ans += i[0] * i[1]
    M -= i[1]
 
print(Ans)
### BUGGY CODE ###

from collections import deque
import copy
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = deque(OK.copy())
        Origin = deque(OK.copy())
        T_3 = deque(OK.copy())
        Enable.append(i)
        Origin.append(P[i])
        T_3.append(i)
        T_3.append(P[i])
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    T_3.append(j)
                    T_3.append(P[j])
                    S.append(j)
    T_1 = list(set(Enable))
    T_2 = list(set(Origin))
    ans = max(ans, len(T_1) + len(T_2) - len(set(T_3)))

print(ans)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
P = list(map(int, input().split()))
K = [[] for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    K[x].append(y)
    K[y].append(x)
used = [0]*N
OK = []
for i in range(N):
    P[i] -= 1
    if i == P[i]:
        OK.append(i)
ans = 0
for i in range(N):
    if used[i] == 0:
        used[i] = 1
        S = deque([i])
        Enable = [i]
        Origin = [P[i]]
        while S:
            t = S.popleft()
            for j in K[t]:
                if used[j] == 0:
                    used[j] = 1
                    Enable.append(j)
                    Origin.append(P[j])
                    S.append(j)
        T_1 = list(set(OK + Enable))
        T_2 = list(set(OK + Origin))
        ans = max(ans, len(T_1) + len(T_2) - len(set(T_1 + T_2)))

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

n,a,b,c,d,e=[int(input()) for i in range(6)]
dist=[n,0,0,0,0,0]
move=[a,b,c,d,e]
t=0
while dist[5]<n:
  dist[0]=max(0,dist[0]-move[0])
  for j in range(1,5):
    dist[j]=max(0,dist[j]-move[j])+min(dist[j-1],move[j-1])
  dist[5]=dist[5]+min(dist[4],move[4])
  t=t+1
print(t)
    


### FIXED CODE ###

n=int(input())
A=[int(input()) for i in range(5)]
print(5+(n-1)//min(A))
### BUGGY CODE ###

def f(x,a):
    while x>0:
        a*=10
        x//=10
    return a

n,m=map(int,input().split())
cost=[0,2,5,5,4,5,6,3,7,6]
la=[int(i) for i in input().split()]
la.sort()
ma=[0 for i in range(10010)]
for a in la:
    ma[cost[a]]=a
for i in range(2,n+1):
    if ma[i]==0:
        continue
    for a in la:
        ma[i+cost[a]]=max(ma[i+cost[a]],max(ma[i]*10+a,ma[i]+f(ma[i],a)))
print(ma[n])

### FIXED CODE ###

def greater(a,b):
    if len(a)>len(b):
        return a
    elif len(b)>len(a):
        return b
    for i in range(len(a)):
        if a[i]<b[i]:
            return b
        if b[i]<a[i]:
            return a
    return a

cost=[0,2,5,5,4,5,6,3,7,6]
n,m=map(int,input().split())
la=[int(a) for a in input().split()]
la.sort()
sa=[str(a) for a in la]
ca=[cost[a] for a in la]
max=[None for i in range(10010)]
for i in range(m):
    max[ca[i]]=sa[i]
for i in range(2,n):
    if max[i]==None:
        continue
    for j in range(m):
        if max[i][0]>sa[j]:
            k=max[i]+sa[j]
        else:
            k=sa[j]+max[i]
        if max[i+ca[j]]==None:
            max[i+ca[j]]=k
        else:
            max[i+ca[j]]=greater(max[i+ca[j]],k)
print(max[n])
### BUGGY CODE ###

S = list(str(input()))
N = int(input())


order = []
state = True

for n in range(N):
    order.append(input().split())


for n in range(N):
    if order[n][0] == '2':
        if (order[n][1] == '1') == state:
            S.insert(0,order[n][2])
        else:
            S.append(order[n][2])
    elif order[n][0] == '1':
        if state:
            state = False
        else:
            state = True


if state:
    out = ''.join(S)
else:
    out = ''.join(S[::-1])

print(out)

### FIXED CODE ###

S = list(str(input()))
N = int(input())

top = []
end = []


order = []
state = True

for n in range(N):
    order = input().split()
    if order[0] == '2':
        if (order[1] == '1') == state:
            top.append(order[2])
        else:
            end.append(order[2])
    elif state:
        state = False
    else:
        state = True


if state:
    S = ''.join(S)
    top = ''.join(top[::-1])
    end = ''.join(end)
    out = top + S + end
    
else:
    S = ''.join(S[::-1])
    top = ''.join(top)
    end = ''.join(end[::-1])
    out = end + S + top

print(out)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

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

cum = 1
over = False
for x in a:
    if x == 0:
        cum = 0
        break

    cum *= x
    if (cum > 1e18):
        over = True

print(-1) if (over and cum != 0) else print(cum)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

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

cum = 1
over = False
for x in a:
    if x == 0:
        cum = 0
        break

if cum == 0:
    print(0)
else:
    for x in a:
        cum *= x
        if (cum > 1e18):
            over = True
            break
    print(-1) if over else print(cum)
### BUGGY CODE ###

import math

n=int(input())
A=list(map(int, input().split()))
B=[0]*n
c=0

for i,a in enumerate(A):
  B[i]=i-A[i]
  A[i]=i+A[i]
  
for i in range(n):
  a=A.count(i)
  b=B.count(i)
  c+=a*b
  
print(c)

### FIXED CODE ###

n=int(input())
A=list(map(int, input().split()))
d={}
c=0

for i,a in enumerate(A):
  if i+a not in d:
    d[i+a]=1
  else:
    d[i+a]+=1
  if i-a in d:
    c+=d[i-a]

print(c)
### BUGGY CODE ###

n = int(input())
t, a = list(map(int, input().split()))
for _ in range(n-1):
    ti, ai = list(map(int, input().split()))
    tt, aa = ti, ai
    while tt < t or aa < a:
        tt += ti
        aa += ai

    t = tt
    a = aa

print(t + a)

### FIXED CODE ###

n = int(input())
t, a = list(map(int, input().split()))
for _ in range(n-1):
    ti, ai = list(map(int, input().split()))
    mt = t // ti if t % ti == 0 else t // ti + 1
    ma = a // ai if a % ai == 0 else a // ai + 1
    m = max(mt, ma)

    t = m * ti
    a = m * ai

print(t + a)
### BUGGY CODE ###

N = int(input())
A = [0] + list(map(int, input().split()))

#  nの約数をO(root(n))で全列挙、
# sortするなら O(root(n) * root(n)log(root(n))) --> O(n * log(n))
def make_divisors(n):
    import math
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0: #割り切れるとき
            divisors.append(i)
            if i != n//i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors

B = [0] * (N + 1)
ans = [0] * (N + 1)
for i in range(N, 0, -1):
    if B[i] == A[i]:
        continue
    ans[i] = 1
    lst = make_divisors(i)
    for tmp in lst:
        B[tmp] += 1
        B[tmp] %= 2

M = sum(ans)
print (M)
for index, b in enumerate(ans):
    if b == 1:
        print (index, end = ' ')


### FIXED CODE ###

N = int(input())
a = [0] + list(map(int, input().split()))

ans = [-1] * (N+1)
count = 0
for i in range(N, 0, -1):
    tmp = 0
    p = i
    p += p
    # print (i, p)
    while p <= N: #pの倍数について確認
        tmp += ans[p]
        p += i
    ans[i] = abs(a[i] - (tmp%2))
    if ans[i] == 1:
        count += 1
    # print (ans)
    
# print (ans)
print (count)
for i in range(1, N + 1):
    if ans[i] == 1:
        print (i)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = [[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)]
  v = numpy.zeros((r, c), dtype=numpy.int)

  for y in range(r):
    s = 0
    for x in range(c):
      if g[y][x] == 0:
        v[y, s:x] += x - s
        s = x + 1

    v[y, s:] += c - s

  for x in range(c):
    s = 0
    for y in range(r):
      if g[y][x] == 0:
        v[s:y, x] += y - s
        s = y + 1

    v[s:, x] += r - s

  print(numpy.max(v) - 1)


if __name__ == '__main__':
  main()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy


def main():
  r, c = map(int, input().split())
  g = numpy.array([[1 if v == '.' else 0 for v in input().strip()] for _ in range(r)])
  g = numpy.array([g, g])

  for x in range(1, c):
    g[0, :, x] += g[0, :, x] * g[0, :, x - 1]

  for x in range(c - 2, -1, -1):
    g[0, :, x] = (g[0, :, x] != 0) * numpy.maximum(g[0, :, x], g[0, :, x + 1])

  for y in range(1, r):
    g[1, y] += g[1, y] * g[1, y - 1]

  for y in range(r - 2, -1, -1):
    g[1, y] = (g[1, y] != 0) * numpy.maximum(g[1, y], g[1, y + 1])

  g = g[0] + g[1]

  print(numpy.max(g) - 1)


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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n = int(input())
arr = []
ans = 0
for i in range(n):
    arr.append([i] + list(map(int,input().split())))
x_sort = sorted(arr, key = lambda x:x[1])
y_sort = sorted(arr, key = lambda x:x[2])

import heapq as hq

q = []

for i in range(n-1):
    costx = x_sort[i+1][1] - x_sort[i][1]
    costy = y_sort[i+1][2] - y_sort[i][2]
    hq.heappush(q, [costx, x_sort[i][0], x_sort[i+1][0] ])
    hq.heappush(q, [costy, y_sort[i][0], y_sort[i+1][0] ])

uf = UnionFind(n)
for rep in range(3*10**5):
    cost, a, b = hq.heappop(q)
    if uf.isSameGroup(a, b):
        continue
    else:
        uf.Unite(a, b)
        ans += cost
    if uf.Count(0) == n:
        break
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]

n = int(input())
arr = []
ans = 0
for i in range(n):
    arr.append([i] + list(map(int,input().split())))
x_sort = sorted(arr, key = lambda x:x[1])
y_sort = sorted(arr, key = lambda x:x[2])

import heapq as hq

q = []

for i in range(n-1):
    costx = x_sort[i+1][1] - x_sort[i][1]
    costy = y_sort[i+1][2] - y_sort[i][2]
    hq.heappush(q, [costx, x_sort[i][0], x_sort[i+1][0] ])
    hq.heappush(q, [costy, y_sort[i][0], y_sort[i+1][0] ])

uf = UnionFind(n)
for rep in range(3*10**5):
    cost, a, b = hq.heappop(q)
    if uf.isSameGroup(a, b):
        continue
    else:
        uf.Unite(a, b)
        ans += cost
    if uf.Count(0) == n:
        break
print(ans)
### BUGGY CODE ###

# 頂点n個 辺iは頂点aiとbiを結ぶ 各頂点には初期値0のカウンターがある
# 操作j: 頂点pjを根とする部分木に含まれるすべてのカウンターにxj足す
# Q回の操作のあと各カウンターの数値を求める

# 方針: 操作の際に最初に部分木の根にだけ点を加え最後に親の点を子に与えていく
import sys
sys.setrecursionlimit(10**9)

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

count = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    count[p-1] += x


def dfs(now=0, prev=-1):
    for i in range(len(connect[now])):
        kid = connect[now][i]
        if kid == prev:
            continue
        count[kid] += count[now]
        dfs(kid, now)


dfs()

for i in range(n):
    print(count[i])


### FIXED CODE ###

# 頂点n個 辺iは頂点aiとbiを結ぶ 各頂点には初期値0のカウンターがある
# 操作j: 頂点pjを根とする部分木に含まれるすべてのカウンターにxj足す
# Q回の操作のあと各カウンターの数値を求める

# 方針: 操作の際に最初に部分木の根にだけ点を加え最後に親の点を子に与えていく
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

count = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    count[p-1] += x


def dfs(now=0, prev=-1):
    kids = connect[now]
    for kid in kids:
        if kid == prev:
            continue
        count[kid] += count[now]
        dfs(kid, now)


dfs()

for i in range(n):
    print(count[i])
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())
a.sort()
key = [False]*n
for i in range(n-1):
  if key[i]: continue
  for j in range(i+1, n):
    if a[j]==a[i]:
      key[i] = True
      key[j] = True
    elif a[j]%a[i]==0:
      key[j] = True
print(key.count(False))

### FIXED CODE ###

N, *A = map(int, open(0).read().split())
A.sort()
dp = [True]*3*int(1e6)
x = -1
for a in A:
  if a == -1: continue
  x = a
  while x <= A[-1]:
    x += a
    dp[x] = False
  x = a

res = 0
for i, a in enumerate(A):
  if i > 0 and a == A[i-1]: continue
  if i < N-1 and a == A[i+1]: continue
  if dp[a]: res += 1
print(res)
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[0] = w
for i in range(n):
  keys = list(sorted(t.keys(), reverse = True)) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  updates = []
  for j in keys:
    nw = t[j] - tw
    if nw < 0:
      continue
    nv = j + tv
    if nv in t:
      if nw > t[nv]:
        t[nv] = nw
        updates.append([nw, nv])
    else:
      t[nv] = nw
      updates.append([nw, nv])
  for u in updates:
    for key in list(t.keys()):
      if u[0] > t[key] and u[1] > key:
        del t[key]
print(max(t.keys()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
A = sum(a)
ans = 100 ** 100

for i in range(1, N):
    x = sum(a[:i])
    ans = min(ans, abs(A - 2 * x))

print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
A = sum(a)
ans = 100 ** 100
x = 0

for i in range(N - 1):
    x += a[i]
    ans = min(ans, abs(A - 2 * x))

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

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_min = int(S,2) % (bit_count-1) if bit_count-1!=0 else 0
S_plu = int(S,2) % (bit_count+1)
S_num = int(S,2)

def mods(temp, count):
    count+=1
    while temp!=0:

#         if temp in res_dict:
#             print(count, temp, res_dict[temp])
#             print("come")
#             print()
#             return count+res_dict[temp]
        
#         if calc_dict[temp]==-1:
        bits = bin(temp).count("1")
            
        temp = temp%bits
        count+=1

    return count

for i in range(len(S)):
    if S[i]=="0":
        part = (2**(N-i-1))% (bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = (2**(N-i-1))% (bit_count-1)
        num = (S_min - part)%(bit_count-1)
        if num==0:
            print(1)
        else:
            print(mods(num, 0))


### FIXED CODE ###

def input_int():
    return map(int, input().split())

def one_int():
    return int(input())

def one_str():
    return input()

def many_int():
    return list(map(int, input().split()))

N=one_int()
S=one_str()

bit_count = S.count("1")
S_num = int(S,2)
S_min = S_num % (bit_count-1) if bit_count-1!=0 else 0
S_plu = S_num % (bit_count+1)




# calc_dict = {i:-1 for i in range(10000)}
# res_dict =  {i:-1 for i in range(10**4)}

# for i in range(1, 10000):
#     if calc_dict[i]==-1:
#         calc_dict[i] = bin(i).count("1")

#     res_dict[i] = i%calc_dict[i]+1

def mods(temp, count):
    count+=1
    if temp!=0:

#         if temp in res_dict:
#             return count+res_dict[temp]
        
#         if temp not in calc_dict:
#             calc_dict[temp]= bin(temp).count("1") 
        count = mods(temp%bin(temp).count("1") , count)

    return count

for i in range(N):
    if S[i]=="0":
        part = pow(2, (N-i-1), bit_count+1)
        num = (S_plu + part ) % (bit_count+1)
        print(mods(num, 0))
    else:
        if S_num == 2**(N-i-1):
            print(0)
            continue
        part = pow(2, (N-i-1), bit_count-1)
        num = (S_min - part)%(bit_count-1)
        print(mods(num, 0))
### BUGGY CODE ###

import sys

def f(a,b,c,cur):
    if max(a,b,c)>lim:
        return 0
    if cur==n:
        return 1
    t=(a,b,c,cur)
    if t in memo:
        return memo[t]
    re1=f(a+ms[cur],b,c,cur+1)
    re2=f(a,b+ms[cur],c,cur+1)
    re3=f(a,b,c+ms[cur],cur+1)
    re=re1+re2+re3
    memo[t]=re
    return re

memo={}
n=int(sys.stdin.readline())
ms=[]
for i in range(n):
    ms+=[int(sys.stdin.readline())]
lim=(sum(ms)-1)//2
print(f(0,0,0,0)%998244353)

### FIXED CODE ###

import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()
### BUGGY CODE ###

N = int(input())
S = input()

S_dict = {}
for i, s in enumerate(list(S)):
    if s in S_dict:
        S_dict[s].append(i)
    else:
        S_dict[s] = [i]
#print(S_dict)

S_set = set()
for nums in S_dict.values():
    for i, a in enumerate(nums):
        for b in nums[i+1:]:
            S_set.add((a, b))
#print(S_set)
#print("---")

ans = 0
for a, b in sorted(S_set):
    i = 0
    if not (a, b) in S_set:
        continue
    while 1:
        #print(i, a+i, b+i)
        if (a+i, b+i) in S_set and a+i < b:
            S_set.discard((a+i, b+i))
            i += 1
        else:
            break
    ans = max(ans, i)
print(ans)
    
    


### FIXED CODE ###

def resolve():
    import sys
    input=sys.stdin.readline
    N = int(input().rstrip())
    S = input().rstrip()

    def z_algo(s):
        """
        param s:str
        return list of int with length len(s)
        """
        # initialization
        n=len(s)
        z=[0]*n
        z[0]=n
        # construct
        L,R=0,0
        for i in range(1,n):
            if i>R: # 過去の結果が全く使えない
                L=R=i
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1 # 0-indexedでiと比較するため
            elif z[i-L]<R-i+1:
                z[i]=z[i-L]
            else:
                L=i
                R+=1 # Rまでは確定しているので、R+1から確認
                while(R<n and s[R-L]==s[R]): R+=1
                z[i]=R-L
                R-=1
        return z

    ans = 0
    for i in range(N-1):
        z = z_algo(S[i:])
        for j, _z in enumerate(z):
            ans=max(ans,min(j,z[j]))
    print(ans)

resolve()
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    t = input().split()
    if t[0] == '1':
        s = s[::-1]
    elif t[0] == '2':
        if t[1] == '1':
            s = t[2]+s
        elif t[1] == '2':
            s = s + t[2]

print (s)


### FIXED CODE ###

s = input()
q = int(input())
v = 0
fs = ''
rs = ''

for i in range(q):
    t = input().split()
    if t[0] == '1':
        v = v + 1
    elif t[0] == '2':
        if (t[1] == '1') and (v % 2 == 0):
            fs = t[2]+fs
        elif (t[1] == '1') and (v % 2 == 1):
            rs = rs + t[2]
        elif (t[1] == '2') and (v % 2 == 0):
            rs = rs + t[2]
        elif (t[1] == '2') and (v % 2 == 1):
            fs = t[2]+fs

if v % 2 == 0:
    s = fs + s + rs
else:
    s = fs + s + rs
    s = s[::-1]        
            
print (s)
### BUGGY CODE ###

from collections import deque
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=deque([K])
while len(stack)>0:
    n=stack.pop()
    for s,t in numbers[n]:
        if visited[s]==inf:
            stack.appendleft(s)
        visited[s]=min(visited[s],visited[n]+t)
for z in keika:
    print(visited[z[0]]+visited[z[1]])
    

### FIXED CODE ###

from collections import deque
import heapq
N=int(input())
numbers=[[] for _ in range(N)]
for _ in range(N-1):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    numbers[a].append((b,c))
    numbers[b].append((a,c))
Q,K=map(int,input().split())
K-=1
keika=[]
for _ in range(Q):
    x,y=map(int,input().split())
    keika.append([x-1,y-1])
inf=pow(10,10)
visited=[inf for _ in range(N)]
visited[K]=0
stack=[K]
heapq.heapify(stack)
while len(stack)>0:
    n=heapq.heappop(stack)
    for s,t in numbers[n]:
        if visited[s]==inf:
            heapq.heappush(stack,s)
            visited[s]=visited[n]+t
for z in keika:
    print(visited[z[0]]+visited[z[1]])