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

N, K = map(int, input().split())
if N % K == 0:
    print(0)

else:
    while True:
        delta = abs(N - K)
        if delta <N:
            N = delta

        else:
            print(N)
            break



### FIXED CODE ###

N, K = map(int, input().split())
if N % K == 0:
    print(0)

else:
    num = N//K
    delta = abs(N-num*K)
    if delta > abs(delta-K):
        print(abs(delta-K))
    else:
        print(delta)
### BUGGY CODE ###

def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def nibutan(n,list):
    left = 0
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle] <= n:
            left = middle
        else:
            right = middle
    return left+1

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

for i in range(Q):
    cnt = 0
    start, end = IL()
    for j in range(start,end+1):
        if len(l[j]) == 0 or l[j][0] > end:
            continue
        elif l[j][-1] <= end:
            cnt += len(l[j])
        else:
            cnt += nibutan(end,l[j])
    print(cnt)

### FIXED CODE ###

import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def imos():
  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[j][i]
      l[j][i] += cnt
      cnt += tmp

  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[i][j]
      l[i][j] += cnt
      cnt += tmp

N,M,Q = IL()
l = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
  a,b = IL()
  l[1][b] += 1
  if a+1 <= N:
    l[a+1][b] += -1

imos()

ans = [IL() for i in range(Q)]
for i in range(Q):
    print(l[ans[i][0]][ans[i][1]])
### BUGGY CODE ###

N, K = [int(x) for x in input().split()]

result = []
for _ in range(N):
    a, b = [int(x) for x in input().split()]
    result.extend([a] * b)

result.sort()
print(result[K-1])


### FIXED CODE ###

N, K = [int(x) for x in input().split()]

result = {}
for _ in range(N):
    a, b = [int(x) for x in input().split()]
    if a in result:
        result[a] += b
    else:
        result[a] = b

result = sorted(result.items())

now = 0
for key, value in result:
    now += value

    if now >= K:
        print(key)
        exit()
### BUGGY CODE ###

import os

def main():
        n = int(input())
        a_list = list(map(int, input().split()))
        result = [a_list.count(i) for i in range(1,n+1)]
        for i in result:
                print(i)
        
if __name__ == "__main__":
        main()       

### FIXED CODE ###

import os

def main():
	n = int(input())
	a_list = list(map(int, input().split()))
	result = [0]*n
	for i in a_list:
		result[i-1] += 1
	for i in result:
		print(i)

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

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

class Node:
    def __init__(self, root):
        self.root = root
        self.children = []
        self.val = 0

    def add_child(self, child_node):
        self.children.append(child_node)
        if self.root is not None:
            self.root.add_child(child_node)

    def calc(self):
        if self.root is not None:
            self.val += self.root.val
        return self.val

nodes = [Node(None)] * n

for i in range(1, n):
    a, b = map(int, input().split())
    a_node = nodes[a - 1]
    nodes[b - 1] = Node(a_node)
    a_node.add_child(nodes[b - 1])

for j in range(q):
    p, x = map(int, input().split())
    node = nodes[p - 1]
    node.val += x

res = []
for node in nodes:
    res.append(str(node.calc()))
print(" ".join(res))

### FIXED CODE ###

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

children_map = [None] * n
vals = [0] * n

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

for j in range(q):
    p, x = map(int, input().split())
    vals[p - 1] += x

res = []
for i in range(n):
    parent = children_map[i]
    if parent is not None:
        vals[i] += vals[parent]
    res.append(str(vals[i]))

print(" ".join(res))
### BUGGY CODE ###

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

ans = 0
for i in range(k):
  if a > 0:
    ans = ans + 1
    a = a - 1
  elif b > 0:
    b = b - 1
  else:
    ans = ans - 1
    c = c - 1

print(ans)

### FIXED CODE ###

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

ans = 0
if k > a:
    ans = ans + a
    k = k - a
else:
    ans = ans + k
    k = 0
if k > b:
    k = k - b
else:
    k = 0
if k > c:
    ans = ans - c
else:
    ans = ans - k
print(ans)
### BUGGY CODE ###

x,y=map(int, input().split())
while x != 0 or y != 0 :
 if x < y : print(x, y)
 else : print(y, x)

### FIXED CODE ###

x, y = map(int, input().split())
while not( x == 0 and y == 0 ):
 if x < y : print(x, y)
 else : print(y, x)
 x, y = map(int, input().split())
### BUGGY CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

index = 1
prev = -1
max_num = -1
flag = True
while flag and index <= N:
    tmp = calc(index)
    if tmp < prev:
        flag = False
    else:
        prev = tmp
    if max_num < tmp:
        max_num = tmp

    index += 1

print(max_num)


### FIXED CODE ###

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


def calc(x):
    return (A*x)//B - A*(x//B)

print(calc(min(B-1, N)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools as itr

N, M = map(int, input().split())
a = [int(input()) for x in range(M)]

def calc_routes(dan):
    tmp = 1
    for i in range(int(dan/2)):
        i += 1
        n = dan - i
        tmp += len(list(itr.combinations(range(n), i)))

    return tmp

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * calc_routes(dan)) % 1000000007
        prev = x+1

routes = (routes * calc_routes(N-prev)) % 1000000007
print(int(routes))

### FIXED CODE ###

# -*- coding: utf-8 -*-
from math import factorial

N, M = map(int, input().split())
a = [int(input()) for x in range(M)]

def fibo(dan):
    tmp = [1, 1]
    for i in range(2, dan+1):
        tmp.append(tmp[i-1] + tmp[i-2])
    return tmp[dan]

routes = 1
prev = 0
for x in a:
    if x == prev:
        routes = 0
        break
    else:
        dan = (x-1) - prev
        routes = (routes * fibo(dan))
        prev = x+1

routes = (routes * fibo(N-prev)) % 1000000007
print(int(routes))
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n = inp()
x = ip()
ctr = 0
for i in range(n-1):
    for j in range(i+1,n):
        if (j-i) == x[i]+x[j]:
            ctr += 1
print(ctr)

### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
#dt = {k:v for k,v in sorted(x.items(), key=lambda i: i[1])}
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]
mp = lambda :map(int,input().split())

n = inp()
x = ip()
ctr = 0
a = [i+x[i] for i in range(n)]
b = [i-x[i] for i in range(n)]

dt1 = {} 
for i in a: dt1[i] = dt1.get(i,0)+1
dt2 = {} 
for i in b: dt2[i] = dt2.get(i,0)+1

for i in dt1:
    if i in dt2:
        ctr += dt1[i]*dt2[i]
print(ctr)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
res = 0
for i in range(n-1):
    for j in range(i+1,n):
        if a[i]==j+1 and a[j]==i+1:
            res += 1
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
res = 0
for i in range(n):
    if a[i]>i+1 and a[a[i]-1]==i+1:
        res += 1
print(res)
### BUGGY CODE ###

K, S = map(int, input().split(' '))
count = 0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            result = x + y + z
            if result == S:
                count += 1
print(count)

### FIXED CODE ###

K, S = map(int, input().split(' '))
count = 0
for x in range(K+1):
    t1 = S - x
    for y in range(K+1):
        z = S - x - y
        if 0 <= z <= K:
            count+=1
print(count)
### BUGGY CODE ###

N,M = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
l_b = []
ans = 0
for i in range(M):
    b,c = map(int,input().split())
    l_b.extend([c]*b)
l_b.sort()
for i in range(N):
    if l_b ==[] or l_a[-1]>= l_b[-1]:
        ans += l_a[-1]
        del l_a[-1]
    else:
        ans += l_b[-1]
        del l_b[-1]
print(ans)


### FIXED CODE ###

from operator import itemgetter
N,M = map(int,input().split())
l_a = sorted(list(map(int,input().split())))
#O(NlogN)
l_bc = [list(map(int,input().split())) for i in range(M)]
l_bc.sort(key = itemgetter(1), reverse = True)
#O(MlogM)
for b,c in l_bc:
    l_a.extend([c]*b)
    if len(l_a) > N*2:
        break
l_a.sort(reverse = True)
print(sum(l_a[:N]))
### BUGGY CODE ###

import sys
read = sys.stdin.read
from functools import reduce
from operator import mul
def main():
    n = int(input())
    # n=1ならprint(1)してexit(コーナーケース対策).
    if n == 1:
        print(1)
        sys.exit()

    jisu = [[] for _ in range(n + 1)]
    jisu[1].append(1)
    num = [i for i in range(n + 1)]
    for i1 in range(2, n + 1):
        if jisu[i1]:
            continue
        else:
            jisu[i1].append(1)
            for i2 in range(i1, n + 1, i1):
                if num[i2] == 1 or i2 % i1 != 0:
                    continue
                else:
                    tmp1 = 2
                    num[i2] /= i1
                    while num[i2] > 1:
                        if num[i2] % i1 == 0:
                            num[i2] /= i1
                            tmp1 += 1
                        else:
                            break
                    jisu[i2].append(tmp1)
    r = 1
    for j1 in range(2, n + 1):
        t = reduce(mul, jisu[j1])
        t *= j1
        r += t
    print(r)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
from math import sqrt, floor
def main():
    n = int(input())
    if n == 1:
        print(1)
        sys.exit()
    # nd:num of div
    nd = [2] * (n + 1)

    for i1 in range(2, floor(n / 2) + 1):
        for i2 in range(i1 * 2, n + 1, i1):
            nd[i2] += 1

    r = 1
    for j1 in range(2, n + 1):
        r += nd[j1] * j1
    print(r)

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

# https://atcoder.jp/contests/abc122/tasks/abc122_c
import numpy as np

N, Q = map(int, input().split())
N = int(N)
S = input()
lr = []
for _ in range(Q):
    l, r = map(int, input().split())
    lr.append((l - 1, r - 1))
locations = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        locations.append(i)
locations = np.array(locations)
# print(locations)

for l, r in lr:
    subset = locations[l <= locations]
    subset = subset[subset < r]
    # print(l, r, subset)
    print(len(subset))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]
for i in range(2, len(S) + 1):
    if S[i - 2:i] == 'AC':
        v = cnt[-1] + 1
    else:
        v = cnt[-1]
    cnt.append(v)

# print('cnt', cnt)
for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)
### BUGGY CODE ###

n=int(input())
a=[]
e=[]
ans=1
for i in range(n):
    b=int(input())
    a.append(b)
c=a[0]
if(c==2):
    print(ans)
else:
    while(c!=2):
        ans+=1
        e.append(c)
        c=a[c-1]
        if(c in e):
            print(-1)
            exit()
    print(ans)

### FIXED CODE ###

n=int(input())
a=[]
ans=1
for i in range(n):
    b=int(input())
    a.append(b)
c=a[0]
if(c==2):
    print(ans)
else:
    while(c!=2):
        ans+=1
        c=a[c-1]
        if(ans>len(a)):
            print(-1)
            exit()
    print(ans)
### BUGGY CODE ###

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

ans = 0

for j in range(1,m+1):
    # aがj以下で最大のbをもつもの
    bmax = 0
    bmaxind = n
    for i in range(n):
        if a[i] <= j and b[i] > bmax:
            bmax = b[i]
            bmaxind = i
    ans += bmax
    if bmaxind < n:
        a[bmaxind] = float('inf')
    
print(ans)


### FIXED CODE ###

import heapq

# max heap
class Heapq:
    def __init__(self, arr, desc=False):
        if desc:
            arr = [-a for a in arr]
        self.sign = -1 if desc else 1
        self.hq = arr
        heapq.heapify(self.hq)
 
    def pop(self):
        return heapq.heappop(self.hq) * self.sign
 
    def push(self, a):
        heapq.heappush(self.hq, a * self.sign)
 
    def top(self):
        return self.hq[0] * self.sign
 
    def size(self):
        return len(self.hq)

from collections import defaultdict
d = defaultdict(list)

n, m = map(int, input().split())
ab = [tuple(map(int,input().split())) for i in range(n)]
for a,b in ab:
    d[a].append(b)

q = Heapq([], True)
 
ans = 0
for i in range(1,m+1):
    for b in d[i]:
        q.push(b)
    if q.size():
        ans += q.pop()
print(ans)
### BUGGY CODE ###

import numpy as np
n,k=map(int,input().split())
h=list(map(int,input().split()))

# dp=[int(10e8)]*n
dp=np.full(n,10e8,dtype=np.int64)
dp[0]=0
for i in range(1,n):
    for j in range(min(i,k)):
        dp[i]=min(dp[i],dp[i-j-1]+abs(h[i]-h[i-j-1]))

print(dp[n-1])


### FIXED CODE ###

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

dp=[int(10e8)]*n
dp[0]=0
for i in range(1,n):
    for j in range(min(i,k)):
        dp[i]=min(dp[i],dp[i-j-1]+abs(h[i]-h[i-j-1]))

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

import bisect
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
count = 0
B = sorted(A,key=lambda x:x[1])
h = [x[1] for x in B]
for i in range(2,N):
    if h[0] + h[1] > i:
        continue
    elif h[-1] + h[-2] < i:
        break
    else:
        for j in range(N-1):
            c = h[j]
            if c >= i:
                break
            else:
                d = i - c
                bs = bisect.bisect_left(h,d)
                if bs < N:
                    if bs <= j:
                        bs = j + 1
                    for k in range(bs,N):
                        if h[k] == d:
                            if abs(B[j][0]-B[k][0]) == i:
                                count += 1
                        else:
                            break
print(count)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in b.items():
    count += x[1] * c[x[0]]
print(count)
### BUGGY CODE ###

import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (s1+1, i))
      ans[i] = s2
  
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
import heapq

def main():
  input = sys.stdin.readline
  n, m = map(int, input().split())
  s = input()
  
  inf = pow(10, 6)
  ans = [inf]*(n+1)
  key = []
  heapq.heapify(key)
  heapq.heappush(key, (0, n))
  ans[n] = 0
  index = n-1
  count = 0
  while key:
    sub = heapq.heappop(key)
    s1, s2 = sub[0], sub[1]
    if s1 < count:
      continue
    count = s1+1
    subindex = index
    for i in range(min([index, s2-1]), max([-1, s2-m-1]), -1):
      if ans[i] != inf:
        continue
      if s[i] == "1":
        continue
      heapq.heappush(key, (count, i))
      ans[i] = s2
      subindex = i
    index = subindex
      
  if ans[0] == inf:
    print(-1)
  else:
    index = 0
    answer = []
    while True:
      subindex = ans[index]
      answer.append(subindex-index)
      if subindex == n:
        break
      index = subindex
  
    print(*answer)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import math

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N+1):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(len(bin(b))-2)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now = now-x
  deme.append(x)
print(*deme[::-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline

import math
import bisect

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

if "1"*M in S:
  print(-1)
  exit()  

S = [int(S[i]) for i in range(N+1)]

L = [(1<<i) -1 for i in range(1,M+1)]

max_n = [0]
mask = (1<<M) -1
b = 0
for i in range(N):
  b = ((b<<1) + (1- S[i])) & mask
  max_n.append(bisect.bisect_left(L,b)+1)

now = N
deme = []
while now != 0:
  x = max_n[now]
  now -= x
  deme.append(x)
print(*deme[::-1])
### BUGGY CODE ###

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)

for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
    else:
        bn0 = bn00 - 1
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    x0 = x00 % bn0
    xi = x0 - b * pow(2,N-1-i,bn0) + bn * pow(2,N-1-i,bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)


### FIXED CODE ###

# 2125
# 方針．f(n)を求めるのがlog(N)で終わりそうだから普通に素直に実装すればいいのでは？
# ただし最初だけは別に実装する必要がある
N = int(input())
X = list(input())

# i番目のビットを反転させて,
# やってることは似てるはずなのになんかうまく行かない
dic={}
bn00 = X.count('1')
x00 = int(''.join(X),2)
aa = x00 % (bn00+1)
if bn00-1==0:
    bb = 0
else:
    bb = x00 % (bn00-1)
for i in range(N):
    # ちゃんともとに戻してね，ということで本のビット
    b = int(X[i]) & 1
    bn = b ^ 1
    if bn:
        bn0 = bn00 + 1
        x0 = aa
    else:
        bn0 = bn00 - 1
        x0 = bb
    if bn0==0: # ビットが全く立っていないつまり0の時，0%0はエラーを起こすので，n%0もエラーを起こす
        print(0)
        continue
    if b: # もとのビットが立っている場合は減らす，ここの計算量が一番重いので計算量を削減してみる
        xi = x0 - b * pow(2,N-1-i,bn0)
    if bn:
        xi = x0 + bn * pow(2, N - 1 - i, bn0)
    xi %= bn0
    num = xi
    count = 1
    while num > 0:
        p = format(num,'b').count('1') # 10進数を２進数にかえるなら，これがいいのかも,int(str(i),2)を使うっていう手もあるけど周りくどい
        num = num % p
        count += 1
    print(count)
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = ans * (prev**count)
    prev = count
print(ans%998244353)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

from fractions import gcd
n=int(input())
cnt=0
for i in range(1,n+1):
  for j in range(1,n+1):
    a=gcd(i,j)
    for k in range(1,n+1):
      cnt+=gcd(a,k)
print(cnt)


### FIXED CODE ###

from math import gcd
k=int(input())
cnt=0
for i in range(1,k+1):
  for j in range(1,k+1):
    a=gcd(i,j)
    for k in range(1,k+1):
      cnt+=gcd(a,k)
print(cnt)
### BUGGY CODE ###

n,q = map(int,input().split())
s = "0"+input()+"0"
info = [input().split() for i in range(q)]

def solve(pos):
  for i in range(q):
    if s[pos] == info[i][0]:
      if info[i][1] == "L":
        pos = pos - 1
      else:
        pos = pos + 1
    if pos == 0:
      return True
    elif pos == n+1:
      return False
  return False

def solve2(pos):
  for i in range(q):
    if s[pos] == info[i][0]:
      if info[i][1] == "R":
        pos = pos - 1
      else:
        pos = pos + 1
    if pos == 0:
      return True
    elif pos == n+1:
      return False
  return False
ans = n
ng = n+2
ok = 0
while abs(ng - ok) > 1:
  mid = (ng+ok)//2
  if solve(mid):
    ok = mid
  else:
    ng = mid

ans = ans - ok

s = s[::-1]

ng = n+2
ok = 0
while abs(ng - ok) > 1:
  mid = (ng+ok)//2
  if solve2(mid):
    ok = mid
  else:
    ng = mid

ans = ans - ok

print(ans)

### FIXED CODE ###

n,q = map(int,input().split())
s = "0"+input()+"0"
info = [input().split() for i in range(q)]

def solve(pos):
  for i in range(q):
    if s[pos] == info[i][0]:
      if info[i][1] == "L":
        pos = pos - 1
      else:
        pos = pos + 1
    if pos == 0:
      return True
    elif pos == n+1:
      return False
  return False

def solve2(pos):
  for i in range(q):
    if s[pos] == info[i][0]:
      if info[i][1] == "R":
        pos = pos - 1
      else:
        pos = pos + 1
    if pos == 0:
      return True
    elif pos == n+1:
      return False
  return False
ans = n
ng = n+2
ok = 0
while abs(ng - ok) > 1:
  mid = (ng+ok)//2
  if solve(mid):
    ok = mid
  else:
    ng = mid

ans = ans - ok

s = s[::-1]

ng = n+2
ok = 0
while abs(ng - ok) > 1:
  mid = (ng+ok)//2
  if solve2(mid):
    ok = mid
  else:
    ng = mid

ans = ans - ok

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
M = 0
for i in range(len(p) - k + 1):
    savesum = sum(p[i:i + k])
    if savesum > M:
        M = savesum
print((k+M)/2)

### FIXED CODE ###

import sys
n, k = map(int, input().split())
p = list(map(int, input().split()))
# 下の同値の場合を除外しないとrange(k,k)=[]となりfor文が回らない
if n == k:
    print((sum(p) + k) / 2)
    sys.exit(0)
saveSum = sum(p[0:k])
M = 0
for i in range(k, len(p)):
    saveSum = saveSum + p[i] - p[i - k]
    if saveSum > M:
        M = saveSum
print((k+M)/2)
### BUGGY CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
for i in range(n):
	b=a[i]
	a[i]=0
	print(max(a))
	a[i]=b

### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
f=max(a)
b=sorted(a,reverse=True)
s=b[1]
for i in range(n):
    if a[i]==f:
        print(s)
    else:
        print(f)
### BUGGY CODE ###

N = int(input())
S = [0 for i in range(N)]
S[0] = ''.join(sorted(list(input())))
ans = 0
for i in range(1, N):
    S[i] = ''.join(sorted(list(input())))
S2 = list(set(S))
for j in range(len(S2)):
    x = S.count(S2[j])
    if x != 1:
        ans += x * (x - 1) / 2
print(int(ans))

### FIXED CODE ###

n=int(input())
S=[''.join(sorted(input())) for i in range(n)]
c=0
dict={}
for s in S:
  if s in dict:
    c+=dict[s]
    dict[s]+=1
  else:
    dict[s]=1
print(c)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=[]
for i in range(n):
    for j in range(n):
        if i+1==l[j]:
            ans.append(j+1)
for i in ans:
    print(i, end=' ')

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ANS=[]
for i in range(N):
    ANS+=[[A[i],i+1]]
ANS.sort()
for i in range(N):
    print(ANS[i][1])
### BUGGY CODE ###

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1

i=0
while i!=n:
    a=s[0]
    del s[0]
    print(max(s))
    s.append(a)
    i+=1

### FIXED CODE ###

import copy
s=[]
i=0
n=int(input())
while i!=n:
    s.append(int(input()))
    i+=1
maxx=max(s)
g=s.count(maxx)
i=0
j=0

#print(g)
while i!=n:
    a = s[j]
    if maxx == a and g < 2:
        a=s[j]
        del s[j]
        print(max(s))
        s.append(a)
    else:
        print(maxx)
        j+=1

    i+=1