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

N = int(input())
edges = []
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges.append([a-1, b-1, c])
    edges.append([b-1, a-1, c])
Q, K = map(int, input().split())
K -= 1
def bellman_ford(edges, num_v, start):
    dist = [float('inf') for _ in range(num_v)]
    dist[start] = 0

    changed = True
    while changed:
        changed = False
        for edge in edges:
            if dist[edge[1]] > dist[edge[0]] + edge[2]:
                dist[edge[1]] = dist[edge[0]] + edge[2]
                changed = True
    return dist

ans_list = []

for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = bellman_ford(edges, N, x)[K]
    K_y = bellman_ford(edges, N, K)[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)

### FIXED CODE ###

import heapq
N = int(input())
edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    edges[a-1].append([b-1, c])
    edges[b-1].append([a-1, c])
Q, K = map(int, input().split())
K -= 1


ans_list = []
def dijkstra(edges, num_v, start):
    dist = [float('inf')] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q, [0, start])

    while len(q) > 0:
        _, u = heapq.heappop(q)
        for edge in edges[u]:
            if dist[edge[0]] > dist[u] + edge[1]:
                dist[edge[0]] = dist[u] + edge[1]
                heapq.heappush(q, [dist[u] + edge[1], edge[0]])
    return dist
base = dijkstra(edges,  N, K)
for i in range(Q):
    x, y = map(lambda n: int(n) - 1, input().split())
    x_K = base[x]
    K_y = base[y]
    ans_list.append(x_K + K_y)

for i in ans_list:
    print(i)
### BUGGY CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
seq = list(range(D))
x = list(permutations(seq, D))
#print(x)
ans = float("inf")
G2=G
for cand in x:
    cnt = 0
    G=G2
    for ind in cand:
        probpoint = (ind + 1) * 100
        if G<=0:
            break
        if G <= probpoint * (probs[ind][0] - 1):
            cnt = cnt + ceil(G / probpoint)
            G=G-probpoint*ceil(G / probpoint)
        else:
            cnt=cnt+probs[ind][0]
            G=G-(probpoint * probs[ind][0]+probs[ind][1])
    ans=min(ans,cnt)
print(ans)




### FIXED CODE ###

import sys
from itertools import *
from math import *
input=sys.stdin.readline
D, G = map(int, input().split())
probs = [list(map(int, input().split())) for _ in range(D)]
G2 = G
seq = tuple(range(D))
x=[]
for i in range(0,D+1):
    l=combinations(seq,i)
    for j in l:
        x.append(j)
x=tuple(x)
#print(x)
infty=100000
#print(x)
ans = infty
for cand in x:
    cnt = 0
    G=G2
    l=[0]*D
    for ind in cand:
        probpoint = (ind + 1) * 100
        G=G-(probpoint * probs[ind][0]+probs[ind][1])
        cnt = cnt + probs[ind][0]
        l[ind]=1
    #print(l,G,cnt)
    for i in range(D-1,-1,-1):
        if G<=0:
            break
        elif l[i]==0:
            probpoint = (i + 1) * 100
            num=ceil(G/probpoint)
            if num<probs[i][0]:
                G=G-num*probpoint
                cnt=cnt+num
            #print(cnt)
            break
    if G<=0:
        ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
L = [int(v) for v in input().split()]
L.sort()

import math
m = {}
def f(n):
    if m.get(n) != None:
        return m[n]
    a = math.factorial(n)
    m[n] = a
    return a
def comb(n, r):
    return f(n) // f(r) // f(n - r)

ans = 0
t = 0
for i in range(N - 1):
    a = comb(L[-1], L[i])
    if ans < a:
        ans = a
        t = i

print(L[-1], L[t])

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, = map(int, input().split())
L = [int(v) for v in input().split()]
L.sort()

ans = 0
for i in range(N):
    if ans < min(L[i], L[-1] - L[i]):
        ans = L[i]

print(L[i], ans)
### BUGGY CODE ###

import numpy as np
N, K, Q = input().split(' ')
n, k, q = int(N), int(K), int(Q)
a = []
p = np.array([k] * n)
d = np.array([1] * n)
for i in range(q):
    a.append(int(input()) - 1)

for i in a:
    d[i] = 0
    p -= d
    d[i] = 1
for i in p:
    res = 'Yes'
    if i < 1:
        res = 'No'
    print(res)

### FIXED CODE ###

N, K, Q = input().split(' ')
n, k, q = int(N), int(K), int(Q)
t = 'No'
if k - q > 0:
    t = 'Yes'
res = [t] * n

p = [k - q] * n
for i in range(q):
    r = int(input()) - 1
    p[r] += 1
    if p[r] > 0:
        res[r] = 'Yes'
for i in res:
    print(i)
### BUGGY CODE ###

MOD = 10 ** 9 + 7


def modFact(n):
    global MOD
    if n == 1:
        return 1
    else:
        return (n * modFact(n - 1)) % MOD


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


N = int(input())
C = list(map(int, input().split()))
C.sort()
modFacts, invs = prepare(N)

mod2 = [0] * (N + 1)
mod2[0] = 1
x = 1
for i in range(N):
    mod2[i + 1] = x = (x * 2) % MOD

ans = 0
for i, c in enumerate(C):
    c %= MOD
    N_ = N - i - 1
    for j in range(0, N_ + 1):
        ans += mod2[N_] * mod2[i + 1] * mod2[i] * c * (j + 1) * modFacts[N_] * invs[N_ - j] * invs[j]
        ans %= MOD

print(ans)


### FIXED CODE ###

MOD = 10 ** 9 + 7


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

mod4 = [0] * (N + 1)
mod4[0] = 1
for i in range(N):
    mod4[i + 1] = (mod4[i] * 4) % MOD

ans = 0
N4 = mod4[N - 1]
for i, c in enumerate(C):
    j = i + 1
    ans += N4 * (j + 1) * c
    ans %= MOD

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

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
a = LIST()
b = [LIST() for i in range(m)]
b.sort(key=itemgetter(1), reverse=True)

c = []
for i in range(m):
    c += [b[i][1]]*b[i][0]

a += c
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

from math import ceil,floor,comb,factorial,gcd,pow,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heappop,heappush
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
aa = Counter(LIST())
aa = sorted(aa.items(), key=itemgetter(0))
a = [[aa[i][1], aa[i][0]] for i in range(len(aa))]
b = sorted([LIST() for i in range(m)], key=itemgetter(1), reverse=True)

ans = 0
i = j = 0
while i < len(b) and j < len(a) and b[i][1] > a[j][1]:
    if b[i][0] >= a[j][0]:
        ans += b[i][1]*a[j][0]
        b[i][0] -= a[j][0]
        a[j][0] = 0
        j += 1
    else:
        ans += b[i][1]*b[i][0]
        a[j][0] -= b[i][0]
        b[i][0] = 0
        i += 1
reg = j
if reg < len(a):
    for i in range(j, len(a)):
        ans += a[i][0]*a[i][1]
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [[INF] * (H+1) for i in range(N+1)]

    for i in range(1,N+1):
        for j in range(1, H+1):
            if j-A[i-1] > 0:
                dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])
            else:
                dp[i][j] = min(dp[i-1][j], B[i-1])

    # for i in dp:
    #     print(i)
    print(dp[N][H])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(H: int, N: int, A: "List[int]", B: "List[int]"):
    dp = [[INF] * (H+1) for i in range(N+1)]

    for i in range(1,N+1):
        for j in range(1, H+1):
            if j-A[i-1] > 0:
                dp[i][j] = min(dp[i-1][j], dp[i][j-A[i-1]]+B[i-1])
            else:
                dp[i][j] = min(dp[i-1][j], B[i-1])

    # for i in dp:
    #     print(i)
    print(dp[N][H])
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int()] * (N)  # type: "List[int]"
    B = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(H, N, A, B)

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

N = int(input())
al = list(map(int,input().split()))
sss=0
for i in range(N):
    sss+=al[i]*sum(al[0:i])
print(sss%1000000007)

### FIXED CODE ###

N = int(input())
al = list(map(int,input().split()))
sss=0
pss=0
for i in range(1,N):
    pss+=al[i-1]
    sss+=al[i]*pss
print(sss%1000000007)
### BUGGY CODE ###

K, S = map(int, input().strip().split(' '))
cnt = 0
for X in range(0, K+1):
	for Y in range(0, K+1):
		for Z in range(0, K+1):
			if X+Y+Z == S:
				cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().strip().split(' '))
cnt = 0
if S < K:
	for X in range(0, S+1):
		cnt += (S-X+1)
else:
	for X in range(0, K+1):
		if (S-X) <= (2*K):
			if (S-X) < K:
				cnt += (S-X+1)
			elif (S-X) > K:
				Z = S-X-K
				cnt += (K-Z+1)
			else:
				cnt += (K+1)
 
print(cnt)
### BUGGY CODE ###

import numpy as np
s = input()
t = input()

dp = np.zeros((len(s) + 1, len(t) + 1))

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        char = s[i-1]
        if char == t[j-1]:
            dp[i, j] = dp[i-1, j-1] + 1
        else:
            dp[i, j] = max(dp[i-1, j], dp[i, j-1])

answer = ''
i, j = len(s), len(t)
now = dp[i, j]
while i > 0 and j > 0:
    if dp[i-1, j] == now:
        i -= 1
        continue
    if dp[i, j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

print(answer[::-1])


### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        char = s[i-1]
        if char == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

answer = ''
i, j = len(s), len(t)
now = dp[i][j]
while i > 0 and j > 0:
    if dp[i-1][j] == now:
        i -= 1
        continue
    if dp[i][j-1] == now:
        j -= 1
        continue
    answer += s[i-1]
    i -= 1
    j -= 1
    now -= 1

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

n = int(input())
array = input().split()
b_list = list()
i = 0

while i < n:
    b_list.append(int(array[i]))
    new_list = []
    while len(b_list) != 0:
        new_list.append(b_list.pop())
    b_list = list(new_list)
    i += 1

i = 0
while i < n:
    print(b_list[i], end = ' ')
    i += 1

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int, input().split()))
b = collections.deque()

for i in range(N):
    if i % 2 == 0:
        b.appendleft(a[i])
    else:
        b.append(a[i])
    
if N % 2 == 0:
    i = N-1
    while i >= 0:
        print(b[i], end = ' ')
        i -= 1
else:
    for i in range(N):
        print(b[i], end = ' ')
### BUGGY CODE ###

R, C, K = map(int, input().split())
V = [[[] for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1].append(v)
M = [[[0, 0, 0, 0] for _ in range(C)] for _ in range(R)]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    V[r][c].sort(reverse=True)
    #candidates = [0 for _ in range(4)]
    #print(candidates)
    for n_pick in range(1 + min(3, len(V[r][c]))):
      s = sum(V[r][c][:n_pick])
      M[r][c][n_pick]=max(M[r][c][n_pick],s)
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[r-1][c][n_prev] > 0 or n_prev == 0:
            M[r][c][n_pick]=max(M[r][c][n_pick],
              M[r-1][c][n_prev] + s)
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r][c-1][n_prev]  > 0 or n_prev == 0:
            M[r][c][n_prev+n_pick]=max(M[r][c][n_prev+n_pick],
              M[r][c-1][n_prev] + s)
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[R-1][C-1]))

### FIXED CODE ###

R, C, K = map(int, input().split())
V = [[0 for _ in range(C)] for _ in range(R)]
for _ in range(K):
  r, c, v = map(int, input().split())
  V[r-1][c-1] = v
M = [0] * R * C * 4 
# M[r*C*4 + c*4 + i]
# M[(r-1)*C*4 + c*4 + i]
# M[r*C*4 + (c-1)*4 + i]
# M[r][c][count in column (c)]
for r in range(R):
  for c in range(C):
    for n_pick in [0, 1] if V[r][c] else [0]:
      M[r*C*4 + c*4 +n_pick] = max(M[r*C*4 + c*4 +n_pick], n_pick*V[r][c])
      if r > 0:
        for n_prev in range(4):
          #print('R++', r, c, n_pick, n_prev)
          if M[(r-1)*C*4 + c*4 +n_prev] > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_pick]=max(M[r*C*4 + c*4 +n_pick],
              M[(r-1)*C*4 + c*4 +n_prev] + n_pick*V[r][c])
      if c > 0:
        for n_prev in range(4 - n_pick):
          #print('C++', r, c, n_pick, n_prev)
          if  M[r*C*4 + (c-1)*4 +n_prev]  > 0 or n_prev == 0:
            M[r*C*4 + c*4 +n_prev+n_pick]=max(M[r*C*4 + c*4 + n_prev+n_pick],
              M[r*C*4 + (c-1)*4 +n_prev] + n_pick*V[r][c])
    #print(candidates)
    #print(r, c, candidates, M)
    #for i in range(4):
    #  M[r][c][i] = max(candidates[i])
    #print(r, c, M)
#print(V, M)
print(max(M[((R-1)*C*4 + (C-1) *4):((R-1)*C*4 + (C-1) *4+4)]))
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n = int(input())
    s = tuple(map(int, tuple(input())))
    num_pos = []
    for num in range(10):
        if num in s:
            num_pos.append(n - s[::-1].index(num) - 1)
    unique_num = [0] * n
    for i1 in range(n):
        unique_num[i1] = sum([np >= i1 for np in num_pos])
    d1 = defaultdict(int)
    for keta1 in range(n - 2):
        for keta2 in range(keta1 + 1, n - 1):
            d1[(s[keta1], s[keta2])] = max(d1[(s[keta1], s[keta2])], unique_num[keta2 + 1])
    r = sum(d1.values())
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
#from collections import defaultdict
def main():
    n = int(input())
    s = tuple(map(int, tuple(input())))
    num_pos = [] # 各数字がｓ中に最後にあらわれる位置。
    for num in range(10):
        if num in s:
            num_pos.append(n - s[::-1].index(num) - 1)
    unique_num = [0] * n # ｓの各桁でその桁以降にある数字の種類。
    for i1 in range(n):
        unique_num[i1] = sum([np >= i1 for np in num_pos])
    unique_num.append(0)
    r = 0
    for keta1 in range(10):
        if keta1 in s:
            keta1_pos = s.index(keta1)
            for keta2 in range(10):
                if keta2 in s[keta1_pos + 1:]:
                    keta2_pos = s[keta1_pos + 1:].index(keta2) + keta1_pos + 1
                    r += unique_num[keta2_pos + 1]
    print(r)

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

from bisect import bisect_left
from decimal import Decimal

N, *A = map(Decimal, open(0).read().split())
N = int(N)
A.sort()

ints = [d for d in A if int(d) == d]
decs = [d for d in A if int(d) != d]

result = len(ints) * (len(ints) - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    if a < 1:
        t = bisect_left(decs, 1 // a)
    else:
        t = i + 1
    for j in range(t, len(decs)):
        t = a * decs[j]
        if t == int(t):
            #print(a, decs[j])
            result += 1

    if a < 1:
        t = bisect_left(ints, 1 // a)
    else:
        t = 0
    for j in range(t, len(ints)):
        t = a * ints[j]
        if t == int(t):
            #print(a, ints[j])
            result += 1

print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

import functools
import operator
N =int(input())

B = 1

A = list(map(int,input().split()))
    
#print(A)

result = functools.reduce(operator.mul,A)

#print(B)
C = 10 ** 18
#print(C)
if result > C:
    print(-1)
else:
    print(result)


### FIXED CODE ###

N =int(input())

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

B = 1
C = 10 ** 18

for i in range(N):
    B = B * A[i]
    if B == 0:
        break
    elif B > C:
        B = -1
        break

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

from heapq import heappush, heappop

N, M, S = map(int, input().split())
mxCost = 0

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = map(int, input().split())
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

for i in range(N):
    C, D = map(int, input().split())
    edges[i].append((i, D, -C))

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        que.append((dist + d, cost, to))

for dist in minDsit[1:]:
    print(min(dist))


### FIXED CODE ###

from heapq import heappush, heappop

N, M, S = map(int, input().split())
mxCost = 0

edges = [[] for _ in range(N)]
for _ in range(M):
    fr, to, cost, dist = map(int, input().split())
    mxCost = max(mxCost, cost)
    fr -= 1
    to -= 1
    edges[fr].append((to, dist, cost))
    edges[to].append((fr, dist, cost))

for i in range(N):
    C, D = map(int, input().split())
    edges[i].append((i, D, -C))

que = [(0, S, 0)]
mxCost *= (N - 1)
minDsit = [[10**18] * (mxCost + 1) for _ in range(N)]
minDsit[0][0] = 0

while que:
    dist, s, now = heappop(que)

    for to, d, c in edges[now]:
        cost = min(mxCost, s - c)
        if cost < 0 or minDsit[to][cost] <= dist + d:
            continue
        minDsit[to][cost] = dist + d
        que.append((dist + d, cost, to))

for dist in minDsit[1:]:
    print(min(dist))
### BUGGY CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
ans = []
for i in range(n):
    for j in range(1,n):
        if a[j]-a[i] >= abs(a[j]-a[i]-k):
            ans.append(abs(a[j]-a[i]-k))
        else:
            ans.append(a[j]-a[i])
print(max(ans))

### FIXED CODE ###

k,n = map(int,input().split())
a = list(map(int,input().split()))
ans = a[0]+(k-a[-1])
for i in range(n-1):
    ans = max(ans,a[i+1]-a[i])
print(k-ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
move=[input().split() for i in range(Q)]
target=[m[0] for m in move]
d=[m[1] for m in move]

def check(i):
    now=i
    t=-1
    while True:
        if S[now] not in target[t+1:]:
            break
        t+=1+target[t+1:].index(S[now])
        if d[t]=="L":
            now-=1
        else:
            now+=1
        if now<0:
            return -1
        if now>=N:
            return 1
    return 0
Lmin=-1
Lmax=N
Rmin=-1
Rmax=N
C=[[1,2]]
while True:
    if len(C)==0:
        break
    c=C.pop()
    now=N*c[0]//c[1]
    x=check(now)
    if x==0:
        if Lmax>now:
            Lmax=now
            C.append([c[0]*2-1,c[1]*2])
        if Rmin<now:
            Rmin=now
            C.append([c[0]*2+1,c[1]*2])
    elif x==1:
        if now<Rmax:
            Rmax=now
            C.append([c[0]*2-1,c[1]*2])
    elif x==-1:
        if Lmin<now:
            Lmin=now
            C.append([c[0]*2+1,c[1]*2])
print(Rmax-Lmin-1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
s=input()
move=[input().split() for i in range(Q)]
inf=float('inf')
alive=[inf,-1*inf]
dead=[-1*inf,inf]
def check(i):
    now=i
    for m in move:
        if m[0]==s[now]:
            if m[1]=='L':
                now-=1
            elif m[1]=='R':
                now+=1
        if now<0:
            return 'left'
        if now>N-1:
            return 'right'
    return 'alive'
def search(now,alive,dead):
    if dead[0]+1==alive[0] and dead[1]-1==alive[1] or dead[0]+1==dead[1]:
        return alive,dead
    idx=now[0]*N//now[1]
    res=check(idx)
    if res=='alive':
        if alive[0]>alive[1]:
            alive=[idx,idx]
            alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
            alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx<alive[0]:
            alive[0]=idx
            if alive[0]-1!=dead[0]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
        elif idx>alive[1]:
            alive[1]=idx
            if alive[1]+1!=dead[1]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
        elif idx==0 or idx==N-1:
            return alive,dead
    elif res=='left':
        if idx>dead[0]:
            dead[0]=idx
            if dead[0]+1!=alive[0]:
                alive,dead=search((2*now[0]+1,2*now[1]),alive,dead)
    elif res=='right':
        if idx<dead[1]:
            dead[1]=idx
            if dead[1]-1!=alive[1]:
                alive,dead=search((2*now[0]-1,2*now[1]),alive,dead)
    return alive,dead
alive,dead=search((1,2),alive,dead)
if alive[0]>alive[1]:
    print(0)
else:
    print(alive[1]-alive[0]+1)
### BUGGY CODE ###

n,m=map(int,input().split())
gate=[]
for i in range(m):
  l=list(map(int,input().split()))
  gate.append(l)
count=[0]*n
for g in range(m):
  for j in range(gate[g][0],gate[g][1]+1):
      count[j-1]+=1
ans=0
for i in range(n):
    if count[i]==m:
        ans+=1
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline

n,m=map(int,input().split())
leftgate=[]
rightgate=[]
for i in range(m):
  l,r=map(int,input().split())
  leftgate.append(l)
  rightgate.append(r)
if (min(rightgate)-max(leftgate))>-1:
  print(min(rightgate)-max(leftgate)+1)
else:
  print(0)