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

def main():
    """
    Range:
        (x,y)
        X: x-K+1 〜 x+K-1
        Y: y-K+1 〜 y+K-1

    rangeをすべて試す: 無理
        1つの希望を満たすように範囲指定:
            模様は確定する
                (0,0)-(K,K) * 2(W or B)
                K^2 * N -> 10^3^2 * 10^5
            他の希望は満たされるか判定
    """
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y, c = input().split()
        a = K if c == "B" else 0
        xy.append((int(x), int(y) + a))

    TLE(K, xy)


def TLE(K, xy):
    ans = 0
    for i in range(2 * K):
        for j in range(2 * K):
            tmp_ans = 0
            for x, y in xy:
                x = (x + i) % (2 * K)
                y = (y + j) % (2 * K)

                w1 = x < K and y < K
                w2 = x >= K and y >= K
                if w1 or w2:
                    tmp_ans += 1

            ans = max(ans, tmp_ans)

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    """
    Range:
        (x,y)
        X: x-K+1 〜 x+K-1
        Y: y-K+1 〜 y+K-1

    rangeをすべて試す: 無理
        1つの希望を満たすように範囲指定:
            模様は確定する
                (0,0)-(K,K) * 2(W or B)
                K^2 * N -> 10^3^2 * 10^5
            他の希望は満たされるか判定
    """
    N, K = map(int, input().split())
    xy = []
    for _ in range(N):
        x, y, c = input().split()
        a = K if c == "B" else 0
        xy.append((int(x), int(y) + a))

    AC(K, xy)
    # TLE(K, xy)


def fix(x, K2):
    return min(max(0, x), K2)


def boundary(x, y, K):
    K2 = K * 2
    s = set()
    for i in range(-2, 2):
        for j in range(-2, 2):
            if (i + j) % 2 == 1:
                continue

            x1 = fix(x + i * K, K2)
            y1 = fix(y + j * K, K2)
            x2 = fix(x + (i + 1) * K, K2)
            y2 = fix(y + (j + 1) * K, K2)

            if x1 == x2 or y1 == y2:
                continue

            s.add(((x1, y1), (x2, y2)))

    return s

def AC(K, xy):
    K2 = K * 2
    w = [
        [0] * (K2 + 1)
        for _ in range(K2 + 1)
    ]

    for x, y in xy:
        x = x % K2
        y = y % K2
        for (x1, y1), (x2, y2) in boundary(x, y, K):
            w[y1][x1] += 1
            w[y1][x2] -= 1
            w[y2][x1] -= 1
            w[y2][x2] += 1

    ans = max_cumsum(w)
    print(ans)


def max_cumsum(w):
    # error in atcoder pypy3
    #import numpy as np
    #return np.array(w).cumsum(axis=1).cumsum(axis=0).max()

    import copy
    w = copy.deepcopy(w)
    l = len(w)
    for i in range(1, l):
        for j in range(l):
            w[j][i] += w[j][i-1]

    for i in range(l):
        for j in range(1, l):
            w[j][i] += w[j-1][i]

    return max(map(max, w))


def TLE(K, xy):
    ans = 0
    for i in range(2 * K):
        for j in range(2 * K):
            tmp_ans = 0
            for x, y in xy:
                x = (x + i) % (2 * K)
                y = (y + j) % (2 * K)

                w1 = x < K and y < K
                w2 = x >= K and y >= K
                if w1 or w2:
                    tmp_ans += 1

            ans = max(ans, tmp_ans)

    print(ans)

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

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

from itertools import accumulate

if N-min(A) <= K:
    print(*[N]*N)
    exit()
    
ans=[0]*(N+1)
for _ in range(K):
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    ans=[0]*(N+1)
    if all(i == N for i in A):
        break
print(*A)

### FIXED CODE ###

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

from itertools import accumulate

if N-min(A) <= K:
    print(*[N]*N)
    exit()
    
ans=[0]*(N+1)
for _ in range(K):
    for i,a in enumerate(A):
        ans[max(0,i-a)]+=1
        ans[min(i+a+1,N)]-=1
    A = list(accumulate(ans))[:-1]
    ans=[0]*(N+1)
    if all(i == N for i in A):
        break
print(*A)
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ll = []
for aa in a:
    for bb in b:
        for cc in c:
            ll.append(aa+bb+cc)
ll.sort()
ll = list(reversed(ll))
for i in range(k):
    print(ll[i])

### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ans = []
for i in range(x):
    for j in range(y):
        for l in range(z):
            if (i+1) * (j+1) * (l+1) <= k:
                ans.append(a[i] + b[j] + c[l])
            else:
                break

ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  s = list(input())
  # N: 処理する区間の長さ
  N0 = 2**(N-1).bit_length()
  id_ele = set()
  data = [id_ele]*(2*N0)
  # a_k の値を x に更新
  def segfunc(x,y):
      return x|y

  def update(k, x):
      k += N0-1
      data[k] = x
      while k >= 0:
          k = (k - 1) // 2
          data[k] = segfunc(data[2*k+1], data[2*k+2])
  # 区間[l, r)の最小値
  def query(l, r):
      L = l + N0; R = r + N0
      s = id_ele
      while L < R:
          if R & 1:
              R -= 1
              s = segfunc(s, data[R-1])

          if L & 1:
              s = segfunc(s, data[L-1])
              L += 1
          L >>= 1; R >>= 1
      return s

  for i in range(N):
    update(i,set(s[i]))
  q = int(input())
  for _ in range(q):
    p,a,b = input().split()
    if p == "1":
      update(int(a)-1,set(b))
    if p == "2":
      print(len(query(int(a)-1,int(b))))
main()
    

### FIXED CODE ###

def main():
  import sys
  input = sys.stdin.readline
  n = int(input())
  s = list(input())

  def segfunc(x,y):
      return x|y

  def init(init_val):
      #set_val
      for i in range(n):
          seg[i+num-1]=init_val[i]    
      #built
      for i in range(num-2,-1,-1) :
          seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
      
  def update(k,x):
      k += num-1
      seg[k] = x
      while k:
          k = (k-1)//2
          seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
      
  def query(p,q):
      if q<=p:
          return ide_ele
      p += num-1
      q += num-2
      res=ide_ele
      while q-p>1:
          if p&1 == 0:
              res = segfunc(res,seg[p])
          if q&1 == 1:
              res = segfunc(res,seg[q])
              q -= 1
          p = p//2
          q = (q-1)//2
      if p == q:
          res = segfunc(res,seg[p])
      else:
          res = segfunc(segfunc(res,seg[p]),seg[q])
      return res

  #####単位元######
  ide_ele = 0

  #num:n以上の最小の2のべき乗
  num =2**(n-1).bit_length()
  seg=[ide_ele]*2*num

  A = []
  for i in range(n):
    A.append(1<<(ord(s[i])-96))
  init(A)
  q = int(input())
  for _ in range(q):
    p,a,b = input().split()
    if p == "1":
      update(int(a)-1,1<<(ord(b)-96))
    if p == "2":
      print(bin(query(int(a)-1,int(b))).count("1"))
main()
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        c_max = l[i] + l[j]
        for k in range(j + 1, n):
            if l[k] < c_max:
                cnt += 1
            else:
                break
print(cnt)

### FIXED CODE ###

import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i - 1, 0, -1):
        c = l[i] - l[j]
        index = bisect.bisect_right(l, c, 0, j)
        cnt += j - index
print(cnt)
### BUGGY CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(N-100,0)
for i in range(minimum,N+1):
  list_ans.append(int(A*i/B)-A*int(i/B))
print(int(max(list_ans)))

### FIXED CODE ###

A,B,N=list(map(int,input().split()))
list_ans=[]
minimum=min(B-1,N)
print(int(A*minimum/B)-A*int(minimum/B))
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0
K = int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    gcd_0 = gcd(i,j)
    for k in range(1,K+1):
      sum += gcd(gcd_0,k)

print(sum)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0
K = int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    gcd_0 = gcd(i,j)
    for k in range(1,K+1):
      sum += gcd(gcd_0,k)

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

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


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if i in a:
            dp[i] = 0
        elif i not in a:
            dp[i] = 1
    else:
        if i in a:
            dp[i] = 0
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)

### FIXED CODE ###

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


dp = [0] * (N+1)

for i in range(N+1):
    if i == 0:
        dp[i] = 1
    elif i == 1:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = 1
        else:
            dp[i] = 1
    else:
        if len(a) !=0:
            if i == a[0]:
                dp[i] = 0
                a.pop(0)

            else:
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] = dp[i] % 1000000007
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] = dp[i] % 1000000007

ans = dp[N]
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
B = list(map(int, input().split()))


for i, b in enumerate(B, start=1):
  if b > i:
    print(-1)
    exit()


bnn = collections.defaultdict(
  lambda: collections.defaultdict(dict)
)
def inv_sousa(B, N, now=tuple()):
  if N == 0:
    yield now
  elif now not in bnn[B][N]:
    for i in range(1, N + 1):
      idx = i - 1
      if B[idx] <= i:
        yield from inv_sousa(B[:idx] + B[i:], N - 1, now=now + (B[idx],))
    bnn[B][N][now] = False


for x in inv_sousa(tuple(B), N):
  if x:
    for i in x[::-1]:
      print(i)
    break
else:
  print(-1)

### FIXED CODE ###

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


inv_output = list()
for i in range(N, 0, -1):
  for j in range(i, 0, -1):
    if B[j - 1] == j:
      inv_output.append(B.pop(j - 1))
      break
  else:
    print(-1)
    break
else:
  for i in inv_output[::-1]:
    print(i)
### BUGGY CODE ###

from collections import Counter
n = int(input())
V = list(map(int, input().split()))

Odd, Evn = [], []
for i in range(n):
    Evn.append(V[i]) if i%2 == 0 else Odd.append(V[i])
Evn = sorted( dict(Counter(Evn)).items(), key = lambda x:x[1])
Odd = sorted( dict(Counter(Odd)).items(), key = lambda x:x[1])

cnt = -1
for evn in Evn:
    for odd in Odd:
        if evn[0] != odd[0]:
            cnt = max(cnt, evn[1]+odd[1])
print(n-cnt) if cnt > 0 else print(n//2)

### FIXED CODE ###

from collections import Counter
n = int(input())
V = list(map(int, input().split()))

Odd, Evn = [], []
for i in range(n):
    Evn.append(V[i]) if i%2 == 0 else Odd.append(V[i])
Evn = sorted( dict(Counter(Evn)).items(), key = lambda x:x[1], reverse=True)
Odd = sorted( dict(Counter(Odd)).items(), key = lambda x:x[1], reverse=True)

cnt = -1
for evn in Evn[0:2]:
    for odd in Odd[0:2]:
        if evn[0] != odd[0]:
            cnt = max(cnt, evn[1]+odd[1])
print(n-cnt) if cnt > 0 else print(n//2)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
seq = []

for i in range(1,n+1):
    ans = a.count(i)
    print(ans)

### FIXED CODE ###

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

import bisect

n = int(input())
A = []
count = 0
for _ in range(n):
    a = int(input())
    if len(A) == 0:
        A.append(a)
        count += 1
        continue
    i = bisect.bisect_left(A, a)
    if i == 0:
        A = [a] + A
        count += 1
    else:
        A[i-1] = a

ans = count
print(ans)

### FIXED CODE ###

import bisect
from collections import deque

n = int(input())
A = []
dq_A = deque(A)
count = 0
for _ in range(n):
    a = int(input())
    if len(dq_A) == 0:
        dq_A.appendleft(a)
        count += 1
        continue
    i = bisect.bisect_left(dq_A, a)
    if i == 0:
        dq_A.appendleft(a)
        count += 1
    else:
        dq_A[i-1] = a

ans = count
print(ans)
### BUGGY CODE ###

def main():
    N, *P = map(int, open(0).read().split())

    dp = [0] + [min(i, j, N - 1 - i, N - 1 - j) for i in range(N) for j in range(N)]
    memo = [1] * (N * N + 1)

    def move(fr, to):
        if dp[to] > dp[fr] + memo[fr]:
            dp[to] = dp[fr] + memo[fr]
            S.append(to)

    ans = 0
    for p in P:
        ans += dp[p]
        memo[p] = 0

        S = [p]
        while S:
            v = S.pop()

            q, r = divmod(v - 1, N)
            if r != 0:
                move(v, v - 1)
            if r != N - 1:
                move(v, v + 1)
            if q < N - 1:
                move(v, v + N)
            if q >= 1:
                move(v, v - N)

    print(ans)

main()

### FIXED CODE ###

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

dp = [0] + [min(i, j, N - 1 - i, N - 1 - j) for i in range(N) for j in range(N)]
memo = [1] * (N * N + 1)

def move(fr, to):
    if dp[to] > dp[fr] + memo[fr]:
        dp[to] = dp[fr] + memo[fr]
        S.append(to)

ans = 0
for p in P:
    ans += dp[p]
    memo[p] = 0

    S = [p]
    while S:
        v = S.pop()

        q, r = divmod(v - 1, N)
        if r != 0:
            move(v, v - 1)
        if r != N - 1:
            move(v, v + 1)
        if q < N - 1:
            move(v, v + N)
        if q >= 1:
            move(v, v - N)

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

# abc 154
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, K = map(int, readline().split())
P = list(map(int, readline().split()))

def cal_expected(p):
    expected = 0
    for i in range(1, p+1):
        expected += i / p
    return expected

# 対象特定
dices = []
dices_sum = 0
for start in range(0, N-K+1):
    tmp_dices = P[start:start+K]
    tmp_sum = sum(tmp_dices)
    if tmp_sum > dices_sum:
        dices = tmp_dices
        dices_sum = tmp_sum

# 期待値計算
answer = sum(map(cal_expected, dices))
print(answer)


### FIXED CODE ###

# abc 154
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N, K = map(int, readline().split())
P = list(map(int, readline().split()))

def cal_expected(p):
    expected = 0
    for i in range(1, p+1):
        expected += i / p
    return expected

# 期待値一覧の作成
expected_dict = {k:cal_expected(k) for k in set(P)}

import copy
from collections import deque
# 対象特定
ans_start = 0
dices_sum = 0
tmp_dices = None
for start in range(0, N-K+1):
    if tmp_dices == None:
        tmp_dices = deque(P[start:start+K])
        tmp_sum = sum(tmp_dices)
    else:
        removed = tmp_dices.popleft()
        tmp_dices.append(P[start+K-1])
        tmp_sum = tmp_sum - removed + P[start+K-1]
    if tmp_sum > dices_sum:
        ans_start = start
        dices_sum = tmp_sum

# 期待値計算
# answer = sum(map(cal_expected, dices))
answer = 0
dices = P[ans_start:ans_start+K]
for dice in dices:
    answer += expected_dict[dice]
print(answer)
### BUGGY CODE ###

N = int(input()) 
A=list(map(int,input().split())) 
i=0 
s=[]
sumall=0
for i in range(N-1):
    s.append(A.count(i+1))
    sumall=sumall+s[i]
    print(s[i])
    if sumall>=N-1:
        i=i+1
        break
for _ in range(i,N):
    print(0)

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

import fractions
N = int(input())
A = [int(i) for i in input().split()]
ans = 1
cur_lcm = A[0]
mod = 10**9 +7
for i in range(N):
    if i == 0:
        continue
    else:
        temp_lcm = cur_lcm*A[i]//fractions.gcd(cur_lcm,A[i])
        if temp_lcm == cur_lcm:
            ans +=  temp_lcm//A[i]
        else:
            ans *= temp_lcm//cur_lcm
            ans += temp_lcm//A[i]
            cur_lcm = temp_lcm
        ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = [int(i) for i in input().split()]
mod = 10**9 +7
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
cur_prime = {}
for i in range(N):
    S = factorization(A[i])
    for j in range(len(S)):
        if S[j][0] not in cur_prime:
            cur_prime[S[j][0]] = S[j][1]
        else:
            cur_prime[S[j][0]] = max(S[j][1],cur_prime[S[j][0]])
A_lcm = 1
key = list(cur_prime.keys())
value = list(cur_prime.values())
for i in range(len(key)):
    for j in range(value[i]):
        A_lcm *= key[i]
        A_lcm %= mod
ans = 0
for i in range(N):
    ans += A_lcm*pow(A[i],mod-2,mod)
    ans %= mod
print(ans)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
H = list(map(int, input().split()))


d = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  A, B = list(map(int, input().split()))
  d[A][B] = 1
  d[B][A] = 1


ans = 0
for i in range(1, N + 1):
  cnt = 0
  for j in range(1, N + 1):
    if d[i][j] == 1 and H[j - 1] >= H[i - 1]:
      cnt +=1
      break
  if cnt == 0:
    ans += 1
print(ans)

### FIXED CODE ###

N, M = list(map(int, input().split()))
H = list(map(int, input().split()))

d = {}
for i in range(1, N + 1):
  d[i] = []
for i in range(M):
  A, B = list(map(int, input().split()))
  d[A].append(B)
  d[B].append(A)

#print(d)
ans = 0
for i in range(1, N + 1):
  cnt = 0
  for j in d[i]:
    if H[j - 1] >= H[i - 1]:
      cnt +=1
      break
  if cnt ==0:
    ans +=1
print(ans)
### BUGGY CODE ###

from sys import stdin
input = stdin.readline
N = int(input())
S = input().rstrip()
R = []
G = []
B = []
ans=0
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    else:
        B.append(i+1)

for r in R:
    for g in G:
        for b in B:
            if g-r!=b-g and b-r!=g-b and r-g!=b-r and b-g!=r-b and r-b!=g-r and g-b!=r-g:
                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 x in range(N):
    for a in range(N):
        y = x+a
        z = y+a
        if z >= N:
            continue
        if S[x] == S[y]:
            continue
        if S[y] == S[z]:
            continue
        if S[x] == S[z]:
            continue
        ans = ans-1
print(ans)
### BUGGY CODE ###

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [0]*n
for i in range(n):
    shift[i] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:
            start = shift[i]-1
            head += max(1,shift[i])
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = shift[i]-1
        head += max(1,shift[i])


for k,x in ans:
    print(k,x)

### FIXED CODE ###

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

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [1]*(n+1)
for i in range(n):
    shift[i+1] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:     
            start = max(0,i - shift[i])
            head += shift[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i+1 - shift[i+1]
        head += shift[i+1]


for k,x in ans:
    print(k,x)
### BUGGY CODE ###

from collections import deque
N = int(input())
S = str(input())

l = []
li = deque([])
for i in range(1, N-1):
  if S[N-i] not in l:
    l.append(S[N-i])
    li.appendleft(N-i)
    
lis = []
ans = 0
for i in range(N-2):
  for j in range(i+1, N-1):
    s = S[i] + S[j]
    if s not in lis:
      lis.append(s)
      for k in range(len(li)):
        if j < li[k]:
          ans += len(li)-k
          break

print(ans)

### FIXED CODE ###

N = int(input())
S = str(input())
R = S[::-1]

ans = 0
for i in range(1000):
  z = str(i).zfill(3)
  right = -1
  left = -1
  if z[2] in R:
    r = R.index(z[2]) + 1
    right = N-r
  else:
    continue
  if z[0] in S:
    left = S.index(z[0]) + 1
  else:
    continue
  if z[1] in S[left:right]:
    ans += 1
print(ans)
### BUGGY CODE ###

s = input()
n = len(s)
slist = [int(i)for i in s]
q = True
ans = 0
while q:
  q = False
  kesu = 0
  for i in range(1,len(slist)):
    if slist[i] != slist[i-1]:
      kesu = i
      ans += 2
      q = True
      break
  if kesu != 0:
    del slist[kesu-1:kesu+1]
print(ans)

### FIXED CODE ###

s = input()
cnt1 = s.count('1')
cnt0 = s.count('0')
print(len(s)-abs(cnt1-cnt0))
### BUGGY CODE ###

import sys
from pprint import pprint

def solve(n, k, p):
    E = [(1.0 + p_i)/2 for p_i in p]
    # pprint(E)
    
    ans = 0
    for i in range(n - k + 1):
        ans = max(ans, sum(E[i:i+k]))
    print(ans)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    p = list(map(int, sys.stdin.readline().strip().split(" ")))
    solve(n, k, p)

### FIXED CODE ###

import sys
from pprint import pprint

def solve(n, k, p):
    acum_E = [0]
    sum_E = 0
    for i, p_i in enumerate(p):
        sum_E += (1.0 + p_i)/2 
        acum_E.append(sum_E)
    # pprint(acum_E)
    
    ans = 0
    for i in range(n - k + 1):
        # print(i+k, i)
        ans = max(ans, acum_E[i + k] - acum_E[i])
    print(ans)

if __name__ == '__main__':
    n, k = map(int, sys.stdin.readline().strip().split(" "))
    p = list(map(int, sys.stdin.readline().strip().split(" ")))
    solve(n, k, p)
### BUGGY CODE ###

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

buff = []
_a = []
ans = 0
b = 0


for i in range(N):
    a, b = list(map(int, input().split()))
    _a.append([a, b])

_a.sort()
for i in range(N):
    buff += [_a[i][0]] * _a[i][1]

print(buff[K-1])



### FIXED CODE ###

amax = 100000
cnt = [0 for i in range(amax+1)]


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

for i in range(N):
    a, b = list(map(int, input().split()))
    cnt[a] += b


for ans in range(1, amax+1):
    if K <= cnt[ans]:
        print(ans)
        break
    K -= cnt[ans]
### BUGGY CODE ###

from fractions import gcd
N, X = map(int, input().split())
city = list(map(int, input().split()))
a = []

for i in range(N):
	a.append(abs(city[i] - X))
	a = sorted(a, reverse = True)
	
s = a.pop(0)

while a:
	s = gcd(s, a.pop(0))
	if s == 1:
		break
print(s)

### FIXED CODE ###

from fractions import gcd

N, X = (int(i) for i in input().split())

x = [abs(int(i) - X) for i in input().split()]  
for i in range(1,N):
	x[i] = gcd(x[i-1], x[i])

print(x[-1])