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

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=i1()
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i-=1
    i>>=1
    j=i+0
    j<<=1
    t[i]=max(t[j+1],t[j+2]) 
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         L = max(L, t[a])
      if b&1==0:
         b-=1
         R = max(t[b], R)
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append(i2())
d=sorted(d)
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 j=bisect.bisect_left(dx,dx[i]+dd[i])
 tt=qr(i,j)
 ud(i,max(j-1,tt))
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])

### FIXED CODE ###

def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import bisect
mod=998244353
n=int(input())
d=[]
N=1<<(n.bit_length())
t=[-1 for i in range(2*N-1)]

def ud(i,x):
  i+=N-1
  t[i]=x
  while i:
    i=(i-1)>>1
    if t[i*2+1]>t[i*2+2]:t[i]=t[i*2+1]
    else:t[i]=t[i*2+2]
     

def qr(a,b):
    a+=N-1
    b+=N-1
    L = -1
    R = -1
    while a < b:
      if a&1==0:
         if L<t[a]:L = t[a]
      if b&1==0:
         b-=1
         if R<t[b]:R = t[b]
      
      a>>=1
      b>>=1
      
         
    return max(L, R)
 
for i in range(n):
  d.append([int(i) for i in input().split()])
d.sort()
dx=[]
dd=[]
for i,j in d:
  dx.append(i)
  dd.append(j)
for i in range(n)[::-1]:
 tx=dx[i]+dd[i]
 j=bisect.bisect_left(dx,tx)
 tt=qr(i,j)
 if j-1>tt:ud(i,j-1)
 else:ud(i,tt)
dp=[0 for i in range(n+1)]
dp[-1]=1
for i in range(n)[::-1]:
  dp[i]+=dp[i+1]
  dp[i]%=mod
  dp[i]+=dp[t[i+N-1]+1]
  dp[i]%=mod
print(dp[0])
### BUGGY CODE ###

N = int(input())

d = {}
x = [0] * N
y = [0] * N
from collections import defaultdict
for i in range(N):
    x[i], y[i] = map(int, input().split())

pqs = []
for i in range(N):
    for j in range(N):
        if i == j:
            continue

        dx = x[i] - x[j]
        dy = y[i] - y[j]
        pqs.append((dx, dy))

ans = N
for pq in pqs:
    p, q = pq
    count = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            dx = x[i] - x[j]
            dy = y[i] - y[j]
            if dx == p and dy == q:
                count += 1
    ans = min(ans, N - count)

print(ans)

### FIXED CODE ###

N = int(input())

d = {}
x = [0] * N
y = [0] * N
from collections import defaultdict
for i in range(N):
    x[i], y[i] = map(int, input().split())

d = defaultdict(int)
for i in range(N):
    for j in range(N):
        dx = x[i] - x[j]
        dy = y[i] - y[j]
        if i == j:
            continue
        d[(dx, dy)] += 1
        
if N == 1:
    print(1)
else:
    print(N - max(d.values()))
### BUGGY CODE ###

n,x,y = list(map(int,input().split()));

knum = [0]*(n-1);
d = [[0]*(n) for i in range(n)];

for i in range(n) :
    for j in range(i+1,n) :
        d[i][j] = j - i;
        d[j][i] = j - i;

d[x-1][y-1] = 1;
d[y-1][x-1] = 1;

for i in range(n) :
    for j in range(i+1,n) :
        mind = min(d[i][j],d[i][x-1]+1+d[y-1][j],d[i][y-1]+1+d[x-1][j]);
        d[i][j] = mind;
        d[j][i] = mind;

for i in range(n) :
    for j in range(i+1,n) :
        knum[d[i][j]-1] += 1;

for i in range(n-1) :
    print(knum[i]);

### FIXED CODE ###

n,x,y = list(map(int,input().split()));

knum = [0]*(n-1);
d = [[0]*(n) for i in range(n)];

for i in range(n) :
    for j in range(i+1,n) :
        d[i][j] = j - i;
        d[j][i] = j - i;

d[x-1][y-1] = 1;
d[y-1][x-1] = 1;

for i in range(n) :
    for j in range(i+1,n) :
        mind = min(d[i][j],d[i][x-1]+1+d[y-1][j],d[i][y-1]+1+d[x-1][j]);
        d[i][j] = mind;
        d[j][i] = mind;

for i in range(n) :
    for j in range(i+1,n) :
        knum[d[i][j]-1] += 1;

for i in range(n-1) :
    print(knum[i]);
### BUGGY CODE ###

n = int(input())
a = input().split()
ans = 1
for i in a:
    ans = ans*int(i)
if ans > 1000000000000000000:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n = int(input())
a = input().split()
ans = 1
if '0' in a:
    ans = 0
else:
    for i in a:
        ans = ans*int(i)
        if ans > 1000000000000000000:
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

def muri(k, c, s):
  if k > s.count("o"):
    return True
  for j in range(len(s)):
    if s[j] == "o":
      return muri(k-1, c, s[j+c+1:])
  return False

n, k, c = map(int, input().split())
s = input()
s += "x"*c

for i in range(len(s)):
  if s[i] == "o":
    if muri(k, c, s[:i]+"x"+s[i+1:]):
      print(i+1)

### FIXED CODE ###

n, k, c = map(int, input().split())
s = input()
s2 = s
s += "x"*c
s2 = "x"*c+s2
k2 = k
kans = k
left = []
i = 0
while i < n:
  if s[i] == "o":
    left.append(i+1)
    i += c
  i += 1

right = []
i = len(s2)-1
while i >= c:
  if k2 == 0:
    break
  if s2[i] == "o":
    right.append(i+1-c)
    k2 -= 1
    i -= c
  i -= 1
if len(left) == kans:
  ans = sorted(list(set(left) & set(right)))
  for i in ans:
    print(i)
else:
  exit()
### BUGGY CODE ###

A,B,K=list(map(int,input().split()))
for i in range(K):
  if(A>=1):
    A-=1
  elif(B>=1):
    B-=1
print(A,' ',B)

### FIXED CODE ###

A,B,K=list(map(int,input().split()))
if(A<=K):
  K=K-A
  A=0
  if(B<=K):
    K=K-B
    B=0
  else:
    B=B-K
else:
  A=A-K
print(A,' ',B)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
flag=0
for i in range(N):
  for j in range(i+1,N):
    if A[i]==A[j]:
      flag=1
      break
      
if flag==0:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
if len(A)==len(set(A)):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
ans = 1
cir = 0
a = 0
if k < n:
  for i in range(k+1):
    sub[i] = ans
    ans = A[ans-1]
  print(sub[k])
else:
  for i in range(n):
    sub[i] = ans
    if A[ans-1] in sub:
      a = sub.index(A[ans-1])
      cir = i+1 - a
      break
    else:
      ans = A[ans-1]
  print(sub[a + (k - a) % cir])

### FIXED CODE ###

n,k = map(int,input().split())
A = list(map(int,input().split()))
sub = [0]*n
city = 0
all = []
roop = []
while sub[city] != 2:
  if sub[city] == 0:
    all.append(city+1)
  else:
    roop.append(city+1)
  sub[city] += 1
  city = A[city] -1
if len(all) > k:
  print(all[k])
else:
  print(roop[(k-(len(all)-len(roop)))%len(roop)])
### BUGGY CODE ###

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

ans = a
for i in range(a+1, b+1):
    ans = (ans ^ i)

print(ans)

### FIXED CODE ###

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

def xor_solve(x):
    if x % 4 == 0:
        return x
    elif x % 4 == 1:
        return 1
    elif x % 4 == 2:
        return x+1
    else:
        return 0
        
print(xor_solve(b) ^ xor_solve(a-1))
### BUGGY CODE ###

def ge():
    return map(int,input().split())
def main():
    #a,b,c,d=ge()
    #N=int(input())
    #a=list(map(int,input().split()))
    #a=input()
    N=int(input())
    x=[]
    y=[]
    for _ in range(N):
        X,Y=ge()
        x.append(X)
        y.append(Y)
    x_list=[]
    for i in range(len(x)-1):
        for j in range(i,len(x)):
            x_list.append(abs(x[i]-x[j]))
    y_list=[]
    for i in range(len(y)-1):
        for j in range(i,len(y)):
            y_list.append(abs(y[i]-y[j]))
    ans=0
    for i in range(len(x_list)):
        ans=max(ans,x_list[i]+y_list[i])
    print(ans)



main()

### FIXED CODE ###

def ge():
    return map(int,input().split())
def main():
    #a,b,c,d=ge()
    #N=int(input())
    #a=list(map(int,input().split()))
    #a=input()
    N=int(input())
    f0=[]
    f1=[]
    for _ in range(N):
        X,Y=ge()
        f0.append(X-Y)
        f1.append(X+Y)
    ans=max(max(f0)-min(f0),max(f1)-min(f1))
    print(ans)
main()
### BUGGY CODE ###

s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    mod_cnt[t % 2019] += 1
    d *= 10
print(sum([m * (m - 1) // 2 for m in mod_cnt]))

### FIXED CODE ###

s = input()[::-1]
mod_cnt = [0] * 2019
mod_cnt[0] = 1
t = 0
d = 1
for c in s:
    t += int(c) * d
    t %= 2019
    mod_cnt[t] += 1
    d *= 10
    d %= 2019
print(sum([m * (m - 1) // 2 for m in mod_cnt]))
### BUGGY CODE ###

N, M = map(int,input().split())
ls = []
count_ac = 0
count_wa = 0
ls2 = []
for i in range(M):
    P, S = input().split()
    ls.append((P, S))

for i in ls:
    if i[1] == "AC":
        ls2.append([i[0], i[1]])
    else:
        if [i[0], "AC"] in ls2:
            pass
        else:
            ls2.append([i[0], i[1]])

a = 0
for i in ls2:
    if i[1] == "AC":
        if i[0] == a:
            continue
        else:
            count_ac += 1
            a = i[0]
    else:
        count_wa += 1

print(count_ac, count_wa)

### FIXED CODE ###

N,M = [int(i) for i in input().split()]
a = {str(i):[] for i in range(1,N+1)}
AC,WA = 0,0
for i in range(M):
    P,S = [x for x in input().split()]
    a[P].append(S)
for i in a:
    if 'AC' not in a[i]:
        continue
    for x in a[i]:
        if x == 'AC':
            AC+=1
            break
        WA +=1
print(AC,WA)
### BUGGY CODE ###

n,m = map(int,input().split())
b = []
for _ in range(m):
  b.append(int(input()))
A = [0,1]
for i in range(1,n+1):
  if i in b:
    A.append(0)
  else:
    A.append( (A[-1]+A[-2]) % (10**9+7) )
print(A[-1])

### FIXED CODE ###

n,m = map(int,input().split())
b = [int(input()) for _ in range(m)] + [n+1]
now = 0
A = [0,1]
if b[0] == 0:
  print(0)
else:
  for i in range(1,n+1):
    if b[now] == i:
      A.append(0)
      now += 1
    else:
      A.append( (A[-1]+A[-2]) % (10**9+7) )
  print(A[-1])
### BUGGY CODE ###

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

change = True
while change:
    change = False
    for i in range(N-1):
        if a[i] > a[i+1]:
            a[i], a[i+1] = a[i+1], a[i]
            b[i], b[i+1] = b[i+1], b[i]
            change = True

money=0
for i in range(N):
    money+=a[i]*b[i]
    M-=b[i]
    if M <= 0:
        break
if M == 0:
    print(money)
else:
    print(money + (a[i] * M))

### FIXED CODE ###

N, M = map(int, input().split())
a, b = [0 for _ in range(N)], [0 for _ in range(N)]
for i in range(N):
    a[i], b[i] = (list(map(int, input().split())))
c = []
for i in range(N):
    c.append([a[i],b[i],i])
c = sorted(c, key=lambda x: x[0])
m = 0
cnt = 0
for i in range(N):
    
    cnt += c[i][1]
    m += c[i][0] * c[i][1]
     
    if cnt == M:
        print(m)
        break
    elif cnt > M:
        print(m - c[i][0] * (cnt - M))
        break
    else:
        continue
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    A_temp=[0]*N
    for k in range(K):
        for i,data in enumerate(A):
            for j in range(max(0,i-data),min(N,i+data+1)):
                A_temp[j]+=1
        A=A_temp
        A_temp=[0]*N
    print(*A)
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    for k in range(K):
        A_temp=[0]*(N+1)
        for i in range(N):
            A_temp[max(0,i-A[i])]+=1
            if i+A[i]+1<=N-1:
                A_temp[i+A[i]+1]-=1
            
        A[0]=A_temp[0]
        for j in range(1,N):
            A_temp[j]+=A_temp[j-1]
            A[j]=A_temp[j]
        for ai in A:
            if ai != N:
                break
        else:
            break
                
    print(' '.join([str(a) for a in A]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
import time

#start = time.time()#計測始
s = str(input())
#end = time.time()#計測終
n=len(s)
span=1
mlist=deque([0])
slist=""

while span<n+1:
  slist = s[n-span] + slist
  m = int(slist)%2019
  mlist.append(m)
  span+=1
  

ll=len(mlist)
l=len(set(mlist))
#print(set(mlist))

print(ll-l)

#print(f"{end-start}sec.")#計測出力

### FIXED CODE ###

import time

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

#start = time.time()#計測始
ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
#end = time.time()#計測終
#print(f"{end-start}sec.")#計測出力
### BUGGY CODE ###

from collections import deque
from itertools import combinations_with_replacement as combi

N, M, Q = map(int, input().split())
road = deque([input().split() for i in range(Q)])
l = [i+1 for i in range(M)]
point = 0
for v in combi(l, N):
    tmp = 0
    for j in range(Q):
        a, b, c, d = map(int, road[j])
        if v[b-1] - v[a-1] == c:
            tmp += d
    point = max(point, tmp)

print(point)

### FIXED CODE ###

from itertools import combinations_with_replacement as combi

N, M, Q = map(int, input().split())
a = [0] * Q
b = [0] * Q
c = [0] * Q
d = [0] * Q
l = [i+1 for i in range(M)]
point = 0

for i in range(Q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

for v in combi(l, N):
    tmp = 0
    for j in range(Q):
        if v[b[j]-1] - v[a[j]-1] == c[j]:
            tmp += d[j]
    point = max(point, tmp)

print(point)
### BUGGY CODE ###

N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

def chk(x):
    s = "{0:b}".format(x)
    s = s[-1::-1]
    w = 0
    v = 0
    for i in range(len(s)):
        if s[i] == '1':
            w += oj[i][0]
            v += oj[i][1]
    return w,v

ans = 0
for i in range(0, 2**N):
    w,v = chk(i)
    if w <= W and v > ans:
        ans = v
print(ans)


### FIXED CODE ###

N,W = map(int, input().strip().split(" "))
oj = []
for i in range(N):
    tmp = list(map(int, input().strip().split(" ")))
    oj.append(tmp)

dp = [[0] * (W+1) for i in range(N)]
for i in range(W+1):
    dp[0][i] = oj[0][1] if oj[0][0] <= i else 0

for i in range(1,N):
    for j in range(W+1):
        if j < oj[i][0]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-oj[i][0]] + oj[i][1])
print(max(dp[N-1]))
### BUGGY CODE ###

from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cnt = 0
    for l, r in combinations(range(N+1),2):
        if C[l]<=C[r]:
            cnt += 1
    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)


### FIXED CODE ###

from itertools import combinations
from math import ceil
N = int(input())
A = list(map(int, input().split()))
M = ceil(N*(N+1)/4)

class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret

lo, hi = 0, max(A)+1
while lo < hi-1:
    mid = (lo+hi)//2
    B = [1 if a >= mid else -1 for a in A]
    C = []
    C.append(0)
    for b in B:
        C.append(C[-1]+b)
    cmin = min(C)
    for i in range(N+1):
        C[i] -= cmin  # offset
    cmax = max(C)+1
    fw = FenwickTree(cmax)
    cnt = 0
    for i in range(N+1):
        cnt += fw.sum(C[i])
        fw.add(C[i], 1)

    if cnt >= M:
        lo = mid
    else:
        hi = mid

print(lo)
### BUGGY CODE ###

import collections
import sys
sys.setrecursionlimit(10**5)
N = int(input())
a = list(map(int, input().split()))
A = collections.Counter(a)

L = sum(a) + 1
dp = [[[-1]*(N+1) for i in range(N+1)] for j in range(N+1)]
# for i in range(1, L+1):

dp[0][0][0] = 0


def solve(c1, c2, c3):
    if dp[c1][c2][c3] >= 0:
        return(dp[c1][c2][c3])
    else:
        P = 1
        if c1 > 0:
            P += solve(c1-1, c2, c3) * (c1/N)
        if c2 > 0:
            P += solve(c1+1, c2-1, c3)*(c2/N)
        if c3 > 0:
            P += solve(c1, c2+1, c3-1)*(c3/N)
        P /= (1 - (N-c1-c2-c3)/N)
        dp[c1][c2][c3] = P

        return(P)


print(solve(A[1], A[2], A[3]))


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

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

def comb(n, r):
    return math.factorial(n) // math.factorial(n - r)

maxi = 0
# print(n*99//100)
for i in range(n-1, n*9999//10000-1, -1):
    key = a[i] // 2
    ok = n
    ng = -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if key <= a[mid]: ok = mid
        else: ng = mid
    if ok < i: 
        if comb(a[i], a[ok]) > maxi:
            maxi = comb(a[i], a[ok])
            ans = [a[i], a[ok]]
    if ng >= 0: 
        if comb(a[i], a[ng]) > maxi:
            maxi = comb(a[i], a[ng])
            ans = [a[i], a[ng]]
print("{} {}". format(ans[0], ans[1]))

### FIXED CODE ###

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

def comb(n, r):
    return math.factorial(n) // math.factorial(n - r)

maxi = 0
i = -1
key = a[i] // 2
for j in range(n):
    if a[j] > key:
        break
# print(j, n-1)
# print(j, key, a)
if abs(a[j-1] - key) >= abs(a[j] - key) and j < n-1:
    ans = [a[i], a[j]]
else:
    ans = [a[i], a[j-1]]
# ok = n
# ng = -1
# while abs(ok - ng) > 1:
#     mid = (ok + ng) // 2
#     if key <= a[mid]: ok = mid
#     else: ng = mid
# if ok < i: 
#     if comb(a[i], a[ok]) > maxi:
#         maxi = comb(a[i], a[ok])
#         ans = [a[i], a[ok]]
# if ng >= 0: 
#     if comb(a[i], a[ng]) > maxi:
#         maxi = comb(a[i], a[ng])
#         ans = [a[i], a[ng]]
print("{} {}". format(ans[0], ans[1]))
### BUGGY CODE ###

def solve(n, q, s):
    accm = [0]*n
    for i in range(n-1):
        if s[i:i+2] == 'AC':
            accm[i] = 1
    for j in range(q):
        l, r = map(int, input().split())
        ans = sum(accm[l-1:r])
        print(ans if accm[r-1] != 1 else ans-1)


if __name__ == '__main__':
    n, q = map(int, input().split())
    s = input()
    solve(n, q, s)


### FIXED CODE ###

from itertools import accumulate


def solve(n, q, s):
    m = [0]*n
    for i in range(1, n):
        if s[i-1:i+1] == 'AC':
            m[i] = 1

    accm = list(accumulate(m))

    for j in range(q):
        l, r = map(int, input().split())
        print(accm[r-1]-accm[l-1])


if __name__ == '__main__':
    n, q = map(int, input().split())
    s = input()
    solve(n, q, s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 14:42:43 2018

@author: maezawa
"""

def print_array(g):
    ans = str(g[0])
    if len(g) > 1:
        for i in range(1,len(g)):
            ans += ' '+str(g[i]) 
    print(ans)

name=[]
time=[]
current_time = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    name.append(s[0])
    time.append(int(s[1]))
# =============================================================================
# print(n,q)
# print(name)
# print(time)
# =============================================================================
finished = []
fin_time = []
i=0
remain = n
while True:
    if time[i] == 0:
        i = (i+1)%n
        continue
    if time[i] <= q:
        current_time += time[i]
        finished.append(name[i])
        fin_time.append(current_time)
        time[i] = 0
        remain -= 1
        if remain == 0:
            break
    else:
        time[i] -= q
        current_time += q
        i = (i+1)%n

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))
        
    


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Apr 29 18:04:22 2018
ALDS1_3b_r リングバッファによる実装
@author: maezawa
"""

def fifo_enque(data):
    global tail
    global fifo
    fifo[tail] = data
    tail = (tail+1)%fifo_size
    
def fifo_deque():
    global head
    global fifo
    data = fifo[head]
    head = (head+1)%fifo_size
    return data

fifo_size = 100000
fifo = [0 for _ in range(fifo_size)]
head = 0
tail = 0

n, q = list(map(int, input().split()))
for i in range(n):
    s = input().split()
    data = [s[0], int(s[1])]
    fifo_enque(data)
    
current_time = 0
finished = []
fin_time = []

while True:
    data = fifo_deque()
    if data[1] > q:
        current_time += q
        data[1] -= q
        fifo_enque(data)
    else:
        current_time += data[1]
        finished.append(data[0])
        fin_time.append(current_time)
    if head == tail:
        break

for i in range(n):
    print("{} {}".format(finished[i], fin_time[i]))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False
 
def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    N = len(S)
    S = reversed(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i, es in enumerate(S):
        c = es
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * pow(10, i, 13)) % 13
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])

solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    N = len(S)
    S = reversed(S)
    dp = [[0 for j in range(13)] for i in range(N)]
 
    for i, es in enumerate(S):
        c = es
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[i][j] = 1
            else:
                dp[i][int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp[i][k] = (dp[i][k] + dp[i-1][(k-amari)%13]) % MOD
            else:
                amari = (int(c) * pow(10, i, 13)) % 13
                for k in range(13):
                    dp[i][k] += (dp[i][k] + dp[i - 1][(k-amari) % 13]) % MOD
 
    dprint(dp)
    print(dp[N-1][5])


solve()