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

from bisect import*
import sys;input=sys.stdin.readline

def doevent(lis):
    global stop
    a,b=lis
    if b>=0:
        if stop=={-1}:
            stop=set()
        stop.add(b)
    else:
        if -b in stop:
            stop.remove(-b)
        if stop==set():
            stop={-1}
    return min(stop)

stop=set([-1])
def main():
    n,q=map(int,input().split())
    event=[]
    
    for i in range(n):
        s,t,x=map(int,input().split())
        event.append((s-x,x))
        event.append((t-x,-x))
    event.sort(key=lambda x:x[0])
    minlist=[doevent(i)for i in event] #時間をindexとしたminlist

    for i in range(q):
        sys.stdout.writelines(str(minlist[bisect_right(event,(int(input()),10**9))-1])+"\n")
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys;input=sys.stdin.readline

n,q=map(int, input().split())
event=[]
for _ in range(n):
    s,t,x=map(int,input().split())
    event.append((s-x-0.5,1,x))
    event.append((t-x-0.5,-1,x))
for i in range(q):
    event.append((int(input()),0,i))
    
event.sort()
is_stop=False
stop=set()
minstop=float('inf')
ans=[-1]*q
for t,e,x in event:
    if e > 0:
        stop.add(x)
        if x<minstop:
            minstop=x
            is_stop=True
    elif e<0:
        stop.remove(x)
        if minstop==x:
            is_stop=False
    elif len(stop)>0:
        if not is_stop:
             minstop=min(stop)
             is_stop=True
        ans[x]=minstop
        
print('\n'.join(map(str, ans)))
### BUGGY CODE ###

import numpy as np
N=int(input())
P=np.array(list(map(int, input().split())))



mini=1
count=1
index_min=P.argmin()
while P[0]>mini:
  P=P[:index_min]
  mini=min(P)
  index_min=P.argmin()
  count+=1
"""
count=1
for i in range(1,N):
  if min(P[:i+1])==P[i]:
    count+=1
"""
print(count)



### FIXED CODE ###

n=int(input())
p=list(map(int, input().split()))
ans=1
l=[p[0]]
buf=p[0]
for i in range(1,n):
    l.append(p[i])
    if p[i]<=buf:
        ans+=1
        buf=p[i]
print(ans)
### BUGGY CODE ###

from itertools import permutations
N = int(input())
s = [tuple(input()) for _ in range(N)]
dp = [False]*N
ans = 0
for i in range(N):
    for j in range(i+1, N):
        if s[j] in permutations(s[i]):
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
d = defaultdict(int)
for _ in range(N):
    d[tuple(sorted(input()))] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n, ww = map(int, input().split())
dp = np.zeros([n, ww+1], dtype='int64')
w, v = map(int, input().split())
dp[0] = np.array([v if i >= w else 0 for i in range(ww+1)])
def knapsack(n, ww):
  for i in range(1, n):
    w, v = map(int, input().split())
    for j in range(1,ww+1):
      if j+w <= ww:
        dp[i][j+w] = np.maximum(dp[i-1][j+w], dp[i-1][j]+v)
      dp[i][j] = np.maximum(dp[i-1][j],dp[i][j])
  return dp[-1][-1]

print(knapsack(n, ww))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def knapsack(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for wk in range(W, w-1, -1):
            tv = dp[wk - w] + v
            if tv > dp[wk]:
                dp[wk] = tv
    return dp[-1]
print(knapsack(N, W))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
total = 0
for i in range(1, N):
  total += i

print(total)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
total = sum(range(1, N))
  
print(total)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
S = []
S.append(1)
S.append(A[0])
while True:
    idx = S[-1]
    loc = A[idx-1]
    if loc not in S:
        S.append(loc)
    else:
        start = S.index(loc)
        end = len(S)
        span = end - start
        break

if K <= end:
    print(S[K])
else:
    n = (K-start)%span
    print(S[start:][n])

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
idx = 1
S = [idx]
ed = set([idx])

for i in range(1, K+1):
    idx = A[idx-1]
    if idx in ed:
        start = S.index(idx)
        end = len(S)
        n = start + (K - start) % (end - start)
        print(S[n])
        break
    else:
        S.append(idx)
        ed.add(idx)
        continue
else:
    print(idx)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

from collections import deque

def bfs(u):
    d = [-1] * n
    queue = deque([u])
    d[u] = 0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] < 0:
                d[i] = d[v] + 1
                queue.append(i)
    return d

g = [[] for _ in range(n)]

for _ in range(m):
    x, y = [int(x) for x in input().split()]
    g[x - 1].append(y - 1)
    g[y - 1].append(x - 1)

ans = 0

for i, j in enumerate(p):
    # print(i, j)
    d = bfs(i)
    # print(d)
    if d[j - 1] >= 0:
        ans += 1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1]*n

###具体例###
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    unite(a - 1, b - 1)

ans = 0

for i, j in enumerate(p):
    if same(i, j - 1):
        ans += 1

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

# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(input())
queries = []
MAX = 0
for _ in range(q):
    l, r = map(int, input().split())
    queries.append((l, r))
    MAX = max([MAX, l, r])

def is_prime(x):
    sqrt = x ** 0.5
    i = 2
    while i <= sqrt:
        if x % i == 0:
            return False
        i += 1
    return True

def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 2
    while i <= sqrt:
        for j in range(i * 2, x + 1, i):
            dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp
primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print(right - left)

### FIXED CODE ###

# https://atcoder.jp/contests/abc084/tasks/abc084_d
from bisect import bisect_left, bisect_right
q = int(input())
queries = []
MAX = 0
for _ in range(q):
    l, r = map(int, input().split())
    queries.append((l, r))
    MAX = max([MAX, l, r])
from datetime import datetime
s = datetime.now()
def eratos(x):
    dp = [True] * (x + 1)
    dp[0] = dp[1] = False
    i = 2
    sqrt = x ** 0.5
    while i <= sqrt:
        if dp[i]:
            for j in range(i ** 2, x + 1, i):
                dp[j] = False
        i += 1
    primes = []
    for i in range(len(dp)):
        if dp[i]:
            primes.append(i)
    return primes, dp

primes, dp = eratos(MAX)
sub_prims = []
for p in primes:
    x = (p + 1) // 2
    if dp[x]:
        sub_prims.append(p)

for l, r in queries:
    left = bisect_left(sub_prims, l)
    right = bisect_left(sub_prims, r + 1)
    print(right - left)
### BUGGY CODE ###

def func(L):
    return sum([L[i+1] - L[i] for i in range(len(L)-1)])


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

H = []

for n in range(N):
    H.append(int(input()))

H.sort()

R = [func(H[i:i+K]) for i in range(N+1-K)]

print(min(R))


### FIXED CODE ###

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

H = [int(input()) for n in range(N)]

H.sort()

R = [H[i+K-1] - H[i] for i in range(N+1-K)]

print(min(R))
### BUGGY CODE ###

N,M=map(int,input().split())
c1=[]
c2=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        c1.append(b)
    if b==N:
        c2.append(a)
for i in c1:
    if i in c2:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')

### FIXED CODE ###

N,M=map(int,input().split())
c1=[]
c2=[]
for i in range(M):
    a,b=map(int,input().split())
    if a==1:
        c1.append(b)
    if b==N:
        c2.append(a)
c1=set(c1)
c2=set(c2)
if c1&c2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math
import fractions


def comb(n,r):
    if n >= r:
        numer = math.factorial(n) % mod
        denom_inv = pow(((math.factorial(r) % mod) * (math.factorial(n-r) % mod)) % mod, mod-2, mod)
        return (numer * denom_inv) % mod
    else:
        return 0


N, A, B, C = map(int, input().split())
mod = 10 ** 9 + 7

G = fractions.gcd(A, B)
A = int(A / G)
B = int(B / G)

P = 0
A_N = pow(A, N, mod)
B_N = pow(B, N, mod)
for i in range(N):
    P = (P + ((N + i) * ((((A_N * pow(B, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod
                        + (((B_N * pow(A, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod)) % mod) % mod
P = (P * 100) % mod
Q = (pow(A+B, 2*N-1, mod) * (100 - C)) % mod
print((P * pow(Q, mod-2, mod)) % mod)


### FIXED CODE ###

import math
import fractions
mod = 10 ** 9 + 7

nmax = 2 * 10 ** 5 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    fac[i] = fac[i - 1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    finv[i] = finv[i - 1] * inv[i] % mod


def comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


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


G = fractions.gcd(A, B)
A = int(A / G)
B = int(B / G)

P = 0
A_N = pow(A, N, mod)
B_N = pow(B, N, mod)
for i in range(N):
    P = (P + ((N + i) * ((((A_N * pow(B, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod
                        + (((B_N * pow(A, i, mod)) % mod) * ((pow(A+B, N-1-i, mod) * comb(N + i - 1, i)) % mod)) % mod)) % mod) % mod
P = (P * 100) % mod
Q = (pow(A+B, 2*N-1, mod) * (100 - C)) % mod
print((P * pow(Q, mod-2, mod)) % mod)
### BUGGY CODE ###

import sys

line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

divide = 1

if x > y:
    x, y = y, x

while(x > 2) :
    for i in range(2, x + 1):
        if  x % i == 0 and y % i == 0:
            divide = divide * i
            x = x / i
            y = y / i
            break

print divide

### FIXED CODE ###

import sys

def div(x, y):
    if x % y == 0:
        print y
    else:
        div(y, x%y)


line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

if x < y:
    x, y = y, x

if x == y:
    print x

else:
    div(x, y)
### BUGGY CODE ###

import bisect
from collections import deque
 
N, M = map(int,input().split())
 
work = [list(map(int,input().split())) for _ in range(N)]
 
wq = deque(sorted(work))
 
paytree = []
 
ans = 0
 
for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        bisect.insort_left(paytree,wq.popleft()[1])
    if len(paytree) > 0:
        ans += paytree.pop(len(paytree) - 1)
 
print(ans)

### FIXED CODE ###

import heapq
from collections import deque

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

work = [list(map(int,input().split())) for _ in range(N)]

wq = deque(sorted(work))

paytree = []

ans = 0

for day in range(M + 1):
    while len(wq) > 0 and wq[0][0] <= day:
        heapq.heappush(paytree, wq.popleft()[1] * (-1))
    if len(paytree) > 0:
        ans -= heapq.heappop(paytree)

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

#!/usr/bin/env python3
#ABC98 D

import sys
input = sys.stdin.readline
def d():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    bit = [[] for _ in range(n)]
    for i in range(n):
        for j in range(20):
            if (a[i] >> j) & 1:
                bit[i].append(j)
    for r in range(n):
        for l in range(r+1):
            b = [item for i in range(l,r+1) for item in bit[i]]
            t = list(set(b))
            if len(b) == len(t):
                ans += 1
    print(ans)

if __name__ == '__main__':
    d()


### FIXED CODE ###

#!/usr/bin/env python3
#ABC98 D

import sys
input = sys.stdin.readline
def d():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    l = 0
    r = 0
    s = 0
    while l < n and r < n:
        while s&a[r] == 0:
            s += a[r]
            r += 1
            ans += r-l
            if r == n:
                break
        if l==r:
            s += a[r]
            r += 1
        s -= a[l]
        l += 1
    print(ans)

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

n = int(input())
a = [int(stdins) for stdins in input().split()]

a.sort()

ans = n
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        elif a[i] < a[j]:
            break
        elif a[i] % a[j] == 0:
            ans -= 1
            break

print(ans)


### FIXED CODE ###

# ABC170

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

a.sort()
a_max = max(a)
dp = [True for _ in range(a_max+1)]

ans = 0
for i in range(n):
    if dp[a[i]]:
        for j in range(0, a_max+1, a[i]):
            dp[j] = False
        if i > 0:
            if a[i] == a[i-1]:
                continue
        if i < n-1:
            if a[i] == a[i+1]:
                continue
        ans += 1

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


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

a.sort(reverse=True)

from heapq import *

ans = 0
q = []
cc = 10**12
c = 10**6

heappush(q,(-2*a[0]*cc))


num = 0
while num < m:
    v = heappop(q)
    v = -v
    v,i,j = v//cc, (v%cc)//c, v%c

    ans += v
    num += 1
    if i != j:
        if num < m:
            num += 1
            ans += v
        else:
            break
        
    #print(v,i,j,num)
    if j == 0 and i < n-1:
        
        heappush(q,-(a[i+1]+a[j])*cc-(i+1)*c-j)
    if i > j:
        heappush(q,-(a[i]+a[j+1])*cc-i*c-(j+1))

print(ans)



### FIXED CODE ###


# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline


n,m = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]

#a.sort(reverse=True)

a.sort()



def check(mid):
    num = 0
    p = 0
    for i in range(n-1,-1,-1):
        c = 0
        while p<n and a[p]+a[i] < mid:
            p += 1
        num += n-p
    #print(mid,num,"mn")
    return num


ok = a[0]*2-1
ng = a[-1]*2+1

while ng - ok > 1:
    mid = (ng+ok)//2
    c = check(mid)
    if c<m:
        ng = mid
    else:
        ok = mid
    
    #print(ok,ng)
    
#print(ok)
    



ans = 0
p = n-1
num = 0

res = [0]*n
for i in range(n):
    c = 0
    while p>=0 and a[p]+a[i] >= ng:
        p -= 1
    res[i] = n-1-p
    num += n-1-p

for i in range(n):
    ans += res[i]*a[i]
ans *= 2
#print(ans,num)
print(ans+ok*(m-num))
### BUGGY CODE ###

import math

def combination(n,k):
    return (math.factorial(n)//math.factorial(k))//math.factorial(n-k)

R = 10**9 + 7

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)

### FIXED CODE ###

import math

R = 10**9 + 7

def combination(n,k):
    if 2*k > n:
        k = n - k

    r = 1
    for i in range(n-k+1,n+1):
        r = (r*i)

    r = (r//math.factorial(k))

    return r

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

decomposition = []
i = 2
while i * i <= M:
    if M % i == 0:
        decomposition.append(0)
        while M % i ==0:
            decomposition[-1] = decomposition[-1] + 1
            M = M//i
    i = i + 1
if M > 1:
    decomposition.append(1)

H = [ combination(N+k-1,k) % R for k in decomposition]
r = 1
for h in H:
    r = (r*h) % R

print(r)
### BUGGY CODE ###

def int2str(i):
  t=str(i)
  if i <10:
    a="0"
    b="0"
    c=t[-1]
  elif i <100:
    a="0"
    b=t[-2]
    c=t[-1]
  else:
    a=t[-3]
    b=t[-2]
    c=t[-1]
  return a,b,c

N=int(input())
S=input()
ans=0
for i in range(1000):
  S1=[]
  S2=[]
  a,b,c=int2str(i)
  flag=0
  for j in  range(len(S)):
    if S[j] ==a:
      S1=S[j+1:]
      break
  if S1==[]:
    continue
  for j in  range(len(S1)):
    if S1[j] ==b:
      S2=S1[j+1:]
      break
  if S2==[]:
    continue
  for j in  range(len(S2)):
    if S2[j] ==c:
      ans+=1
      break
print(ans)
  
  

### FIXED CODE ###

def int2str(i):
  t=str(i)
  if i <10:
    a="0"
    b="0"
    c=t[-1]
  elif i <100:
    a="0"
    b=t[-2]
    c=t[-1]
  else:
    a=t[-3]
    b=t[-2]
    c=t[-1]
  return a,b,c

N=int(input())
S=input()
ans=0
for i in range(1000):
  S1=[]
  S2=[]
  a,b,c=int2str(i)
  flag=0
  i1 = S.find(a)
  if i1 !=-1:
    S1=S[i1+1:]
    i2=S1.find(b)
    if i2 !=-1:
      S2=S1[i2+1:]
      i3=S2.find(c)
      if i3 !=-1:
        ans+=1
print(ans)
### BUGGY CODE ###



n = int(input())
Dn = list(map(int, input().split()))#ダム


memo = 0 # M_n = M_0
for i in range(n):
    memo += Dn[i]*(-1 if i%2==0 else 1)

memo *= -1

#print(memo)



M0_max = min(Dn[0], Dn[-1])*2 
Mn0 = 0

for i in range(0, M0_max+1, 2):
    
    valid = i == memo 
    
#    print(i, memo, valid)
#    print(Dn)
#    print()

    if valid:
        Mn0 = i
        break

Mn = [0]*n
Mn[0] = Mn0
for i in range(1,n):
    Mn[i] = 2*Dn[i-1]-Mn[i-1]

print(*Mn)




### FIXED CODE ###



n = int(input())
Dn = list(map(int, input().split()))#ダム


memo = 0 # M_n = M_0
for i in range(n):
    memo += Dn[i]*(-1 if i%2==0 else 1)

memo *= -1

#print(memo)



M0_max = min(Dn[0], Dn[-1])*2 
Mn0 = 0

def set_Mn0():

    for i in range(0, M0_max+1, 2):
    
        valid = i == memo 
#    print(i, memo, valid)
#    print(Dn)
#    print()

        if valid:
            Mn0 = i
            break


m0_l = 0
m0_h = M0_max
mid = m0_l + m0_h
mid = mid//2 + mid%2

while mid != memo:
    if memo < mid :
        m0_h = mid
    else:
        m0_l = mid
    
    mid = m0_l + m0_h
    mid = mid // 2 + mid%2
    
    #print(mid)

Mn0 = mid


Mn = [0]*n
Mn[0] = Mn0
for i in range(1,n):
    Mn[i] = 2*Dn[i-1]-Mn[i-1]

print(*Mn)
### BUGGY CODE ###

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

for i in range(0, min(A[0], A[-1]) * 2 + 1, 2):
    M = [i]
    for j in range(N):
        v = 2 * A[j] - M[-1]
        M.append(v)
        if v < 0:
            break
    else:
        if M[0] == M[-1]:
            M = M[:-1]
            # print('M', M)
            print(*M, sep=' ')
            exit()

# 一番小さいi値を 0, 2, 4, .... 2 * M[i]まで総当たりでやってみる


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
# print(f'{A=}, {A[1::2]=}')

M = [0] * N
M[0] = A.sum() - 2 * A[1::2].sum()

for i in range(N - 1):
    M[i + 1] = 2 * A[i] - M[i]

print(*M, sep=' ')
# A1 + A2 + ... + AN = X1 + X2 + ... + XN = S
# XN+1 = N1とすると
# (Xi + Xi+1) / 2 = Ai
# Xi + Xi+1 = 2 * Ai
# X1 = S - (X2 + ... + XN) = S - 2(A2 + A4 + ... + AN-1)
# Xi+1 = 2Ai - Xi
### BUGGY CODE ###

n = int(input())
S = list(input())

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

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

init(S)

Q = int(input())
for _ in range(Q):
    x,y,z = map(str,input().split())
    x = int(x); y = int(y)
    if x == 1:
        update(y-1, z)
    else:
        z = int(z)
        print(query(y-1,z))

### FIXED CODE ###

from collections import defaultdict

alpha = defaultdict(int)
num = 0
for i in sorted(map(chr,range(97,123))):
    alpha[i] = 1 << num
    num += 1

n = int(input())
S = tuple(alpha[i] for i in input())

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] = 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] = seg[k*2+1] | seg[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res=0
    while q-p>1:
        if p&1 == 0:
            res |= seg[p]
        if q&1 == 1:
            res |= seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res |= seg[p]
    else:
        res |= (seg[p] | seg[q])
    cnt = 0
    i = 0
    while res:
        cnt += res & 1
        i += 1
        res >>= 1
    return cnt
#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[0 for _ in range(2*num)]

init(S)

Q = int(input())
for _ in range(Q):
    x,y,z = map(str,input().split())
    x = int(x); y = int(y)
    if x == 1:
        update(y-1, alpha[z])
    else:
        z = int(z)
        print(query(y-1,z))
### BUGGY CODE ###


def resolve():
    n, k = list(map(int, input().split()))
    xxx = list(map(int, input().split()))
    ans = float("inf")
    for i in range(n-k+1):
        lll = xxx[i:i+k]
        max_l = lll[-1]
        min_l = lll[0]
        if not min_l <= 0 <= max_l:
            ans = min(ans, max(abs(min_l), abs(max_l)))
        else:
            ans = min(ans, min(abs(min_l), abs(max_l))+abs(max_l-min_l))
    print(ans)
resolve()

### FIXED CODE ###


def resolve():
    n, k = list(map(int, input().split()))
    xxx = list(map(int, input().split()))
    ans = float("inf")
    for i in range(n-k+1):
        max_l = xxx[i+k-1]
        min_l = xxx[i]
        if not min_l <= 0 <= max_l:
            ans = min(ans, max(abs(min_l), abs(max_l)))
        else:
            ans = min(ans, min(abs(min_l), abs(max_l))+abs(max_l-min_l))
    print(ans)
resolve()
### BUGGY CODE ###

S = input()

N = len(S)
dp = [[0 for i in range(13)] for j in range(N + 1)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(13):
        if S[i] != "?":
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
        else:
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])


### FIXED CODE ###

S = input()

N = len(S)
dp = [[0 for i in range(13)] for j in range(N + 1)]
mod = 10**9 + 7

dp[0][0] = 1
for i in range(N):
    for j in range(13):
        if S[i] != "?":
            dp[i + 1][(j * 10 + int(S[i])) % 13] += dp[i][j]
        else:
            for k in range(10):
                dp[i + 1][(j * 10 + k) % 13] += dp[i][j]
    for j in range(13):
        dp[i + 1][j] %= mod

print(dp[N][5])