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

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        primes = merge_dict(primes, prime_factorization(A[i]))

    set_gcd = A[0]
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])
        if is_pair_gcd:
            p = prime_factorization(A[i])
            for k, v in p.items():
                if k == 1:
                    continue
                if primes[k] != v:
                    is_pair_gcd = False
                    break
    if is_pair_gcd:
        print("pairwise coprime")
    elif not is_pair_gcd and set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
# sys.setrecursionlimit(100000)
from collections import defaultdict
from functools import lru_cache


@lru_cache(None)
def gcd(x: int, y: int) -> int:
    if x < y:
        x, y = y, x
    while y > 0:
        r = x % y
        x, y = y, r
    return x


def merge_dict(d1, d2):
    for k, v in d2.items():
        d1[k] += v
    return d1


def input():
    return sys.stdin.readline().strip()


def prime_factorization(N: int) -> dict:
    primes = defaultdict(int)
    primes[1] = 1
    if N < 2:
        return primes
    i = 2
    while i * i <= N:
        while N % i == 0:
            primes[i] += 1
            N = N // i
        i += 1
    if N != 1:
        primes[N] = 1
    return primes


def main():
    n = int(input())
    A = [int(i) for i in input().split()]
    primes = defaultdict(int)
    is_pair_gcd = True
    # pre-process
    for i in range(n):
        p = prime_factorization(A[i])
        for k, v in p.items():
            if k == 1:
                continue
            if k in primes.keys():
                is_pair_gcd = False
                break
            else:
                primes[k] += v
        else:
            continue
        break

    if is_pair_gcd:
        print("pairwise coprime")
        return

    set_gcd = A[0]
    for i in range(1, n):
        set_gcd = gcd(set_gcd, A[i])

    if set_gcd == 1:
        print("setwise coprime")
    else:
        print("not coprime")

    return


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

n=int(input())
import  functools
import operator
prod=functools.partial(functools.reduce, operator.mul)

a=list(map(int,input().split()))
ans=prod(a)

if ans>10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

n=int(input())
import  functools
import operator
prod=functools.partial(functools.reduce, operator.mul)
a=list(map(int,input().split()))
a.sort(reverse=True)
if a[0]*a[1]>10**18 and a[-1]!=0:
    print(-1)
    exit()
if a[-1]==0:
    print(0)
    exit()
    
ans=prod(a)

if ans>10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = 1
for i in a:
    ans *= i
    if ans == 0:
        print('0')
        exit()
if ans > 10 ** 18:
    print('-1')
else:
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
if a[0] == 0:
    print('0')
    exit()
ans = 1
for i in range(1, n + 1):
    ans *= a[-i]
    if ans > 10 ** 18:
        print('-1')
        exit()
print(ans)
### BUGGY CODE ###

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7

sum_list =[p[i]*p[t] for i in range(a) for t in range(a) if i<=t and not i ==t]
num = sum(sum_list)%mod
print(num)

### FIXED CODE ###

import itertools as itr

a = int(input())
p = list(map(int,input().split()))
mod = 10**9 + 7
ans =0
sum_list = list(itr.accumulate(p))
for i in range(len(p)-1):
    o = p[i+1]
    w =sum_list[i]
    ans = (ans+o*w%mod)%mod
print(ans)
### BUGGY CODE ###

def Dijkstra(N, edges, s):
    from heapq import heappush, heappop, heapify
    dist = [10**20 for _ in range(N)]
    dist[s], h = 0, [[0, s]]
    while (len(h)):
        p = heappop(h)
        d, v = p[0], p[1]
        if d > dist[v]:
            continue
        for i in range(len(edges[v])):
            u = edges[v][i]
            if d + 1 < dist[u]:
                dist[u] = d + 1
                heappush(h, [dist[u], u])
    return dist

N, M = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    es[a].append(b)
    es[b].append(a)
dist = Dijkstra(N, es, 0)
if dist[N - 1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline

def Dijkstra(N, edges, s):
    from heapq import heappush, heappop, heapify
    dist = [10**18 for _ in range(N)]
    dist[s], h = 0, [[0, s]]
    while (len(h)):
        p = heappop(h)
        d, v = p[0], p[1]
        if d > dist[v]:
            continue
        for i in range(len(edges[v])):
            u = edges[v][i]
            if d + 1 < dist[u]:
                dist[u] = d + 1
                heappush(h, [dist[u], u])
    return dist

N, M = map(int, input().split())
es = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    es[a].append(b)
    es[b].append(a)
dist = Dijkstra(N, es, 0)
if dist[N - 1] == 2:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import math
r,g,b,n = map(int,input().split())
 
ans = 0
for i in range(math.ceil(n/r)+1):
  for j in range(math.ceil((n-r*i)/g)+1):
    if (n - r*i - g*j)%b == 0 and n - r*i - g*j >= 0:
      ans += 1
print(ans)

### FIXED CODE ###

import math
r,g,b,n = map(int,input().split())
 
ans = 0
for i in range(math.ceil(n/r)+1):
  for j in range(math.ceil((n-r*i)/g)+1):
    if (n - r*i - g*j)%b == 0 and n - r*i - g*j >= 0:
      ans += 1
print(ans)
### BUGGY CODE ###

# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n = I()
ans = 0
for i in range(1, n):
    cnt = 0
    for j in range(1, int(i**0.5)+1):
        if i % j == 0:
            cnt += 1
            if j != i // j:
                cnt += 1
    ans += cnt

print(ans)


### FIXED CODE ###

# coding=utf-8
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heappushpop, heapify
import copy
import sys
INF = float('inf')
mod = 10**9+7
sys.setrecursionlimit(10 ** 6)


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


n = I()
ans = 0
for a in range(1, n):
    ans += (n-1)//a

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

A, B, K = 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 = map(int, input().split())

if A >= K:
  print(A - K, B)
elif A + B >= K:
  print(0, A + B - K)
else:
  print(0, 0)
### BUGGY CODE ###

import itertools

n = int(input())

s = input()

numlist = [0] * 1000

for i in range(1000):
    top = i // 100
    mid = (i - top * 100) // 10
    bot = (i - top * 100 - mid * 10)


    found = False
    for j in range(n):
        if s[j] == str(top):
            for k in range(j+1, n):
                if s[k] == str(mid):
                    for l in range(k+1, n):
                        if s[l] == str(bot):
                            numlist[i] += 1
                            found = True
                            break 
                if found:
                    break
        if found:
            break

ans = numlist.count(1)

print(ans)

### FIXED CODE ###

 
n = int(input())
s = input()
ans = 0
 
pin = [str(i).zfill(3) for i in range(1000)]
 
for i in pin:
    idx = -1
    for j in i:
        idx = s.find(j,idx+1)
        if idx < 0:
            break
    else:
        ans += 1
 
print(ans)
### BUGGY CODE ###

from collections import deque

H,W = map(int,input().split())
c_h, c_w = map(int,input().split())
d_h, d_w = map(int,input().split())

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1

s = [list(input()) for _ in range(H)]

# print(s)

q = deque()
q.append((c_h,c_w))

INF = 1e9
# マス目に入る数字を入れる配列
# 最初はINFで初期化
dist = [[INF for _ in range(W)] for __ in range(H)]

dist[c_h][c_w] = 0
# (右、上、左、下)
dh = (0,1,0,-1)
dw = (1,0,-1,0)

while(len(q) > 0):
    # dequeの一番左を取り出す。
    now = q.popleft()
    now_h,now_w = now

    d = dist[now_h][now_w]

    # 今のマスの上下左右で動けるか確認する
    for di in range(4):
        next_h = now_h + dh[di]
        next_w = now_w + dw[di]

        if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
        if (s[next_h][next_w] == '#'): continue
        if dist[next_h][next_w] <= d: continue

        # 隣り合う動けるマスには同じ数字を記入
        dist[next_h][next_w] = d

        # dequeに前から入れる
        q.appendleft((next_h,next_w))

    # 魔法を使う場合
    for ew in range(-2,3):
        for eh in range(-2,3):
            next_h = eh + now_h
            next_w = ew + now_w

            if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
            if (s[next_h][next_w] == '#'): continue
            if dist[next_h][next_w] <= d+1: continue

            dist[next_h][next_w] = d+1
            q.append((next_h,next_w))

if (dist[d_h][d_w] == INF):
    print(-1)
else:
    print(dist[d_h][d_w])

# print(dist)


### FIXED CODE ###

from collections import deque

H,W = map(int,input().split())
c_h, c_w = map(int,input().split())
d_h, d_w = map(int,input().split())

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1

s = [list(input()) for _ in range(H)]

# print(s)

q = deque()
q.append((c_h,c_w))

INF = 1e9
# マス目に入る数字を入れる配列
# 最初はINFで初期化
dist = [[INF for _ in range(W)] for __ in range(H)]

dist[c_h][c_w] = 0
# (右、上、左、下)
dh = (0,1,0,-1)
dw = (1,0,-1,0)

while(len(q) > 0):
    # dequeの一番左を取り出す。
    now = q.popleft()
    now_h,now_w = now

    d = dist[now_h][now_w]

    # 今のマスの上下左右で動けるか確認する
    for di in range(4):
        next_h = now_h + dh[di]
        next_w = now_w + dw[di]

        if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
        if (s[next_h][next_w] == '#'): continue
        if dist[next_h][next_w] <= d: continue

        # 隣り合う動けるマスには同じ数字を記入
        dist[next_h][next_w] = d

        # dequeに前から入れる
        q.appendleft((next_h,next_w))

    # 魔法を使う場合
    for ew in range(-2,3):
        for eh in range(-2,3):
            next_h = eh + now_h
            next_w = ew + now_w

            if (next_h<0 or next_h>=H or next_w<0 or next_w>=W): continue
            if (s[next_h][next_w] == '#'): continue
            if dist[next_h][next_w] <= d+1: continue

            dist[next_h][next_w] = d+1
            q.append((next_h,next_w))

if (dist[d_h][d_w] == INF):
    print(-1)
else:
    print(dist[d_h][d_w])

# print(dist)
### BUGGY CODE ###

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

ab = []
for i in range(N-1):
    a, b = map(int, input().split())
    ab.append((a, b))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

P = [0 for _ in range(N)]  # 0-indexed
for i in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x

for i in range(N-1):
    a, b = ab[i]
    P[b-1] += P[a-1]

print(*P)


### FIXED CODE ###

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

ab = []
for i in range(N-1):
    a, b = map(int, input().split())
    ab.append((a, b))
ab = sorted(ab, key=lambda x: x[0])

P = [0 for _ in range(N)]  # 0-indexed
for i in range(Q):
    p, x = map(int, input().split())
    P[p-1] += x

for i in range(N-1):
    a, b = ab[i]
    P[b-1] += P[a-1]

print(*P)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
graph = [[] for i in range(N)]
for i in range(M):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  graph[u].append(v)

S, T = map(int, input().split())
S -= 1; T -= 1

memo = {}
def search(node, k):
  global memo
  s = set()
  if k == 0:
    return set([node])
  if (node, k) in memo:
    return memo[(node, k)]
  children = graph[node]
  for child in children:
    s |= search(child, k-1)
  memo[(node, k)] = s
  return s


# 距離が3のノード間にだけ辺を張り直す
g = [[] for i in range(N)]
for i in range(N):
  g[i] = search(i, 3)

dist = [-1] * N
dist[S] = 0
d = deque([[S, -1]])
while d:
  node, par = d.popleft()
  children = g[node]
  for child in children:
    if dist[child] < 0:
      dist[child] = dist[node] + 1
      d.append([child, node])

if dist[T] > 0:
  print(dist[T])
else:
  print(-1)

### FIXED CODE ###

from collections import deque

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

graph = [[] for i in range(3*N)]
for i in range(M):
  u, v = map(int, input().split())
  u, v = 3*(u - 1), 3*(v - 1)
  graph[u].append(v+1)
  graph[u+1].append(v+2)
  graph[u+2].append(v)

s, t = map(int, input().split())
s, t = 3*(s - 1), 3*(t - 1)


dist = [10**9] * 3*N
dist[s] = 0
d = deque([s])
while d:
  node = d.popleft()
  children = graph[node]
  for child in children:
    if dist[child] > dist[node] + 1:
      d.append(child)
      dist[child] = dist[node] + 1

if dist[t] < 10**9:
  print(dist[t]//3)
else:
  print(-1)
### BUGGY CODE ###

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

start = end = 0
MAX = 0
for i in range(n):
    dices = p[i:i+k]
    expec = 0
    for d in dices:
        expec += (((1 + d) * d) / 2) / d
    MAX = max(MAX, expec)

print(MAX)

### FIXED CODE ###

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

expectations = [(((1 + i) * i) / 2) / i for i in p] # O(n)
i = 0
MAX = e = sum(expectations[i:i + k])
while i + k < n: # O(n)
    i += 1
    t = e - expectations[i - 1] + expectations[i + k - 1]
    MAX = max(MAX, t)
    e = t

print(MAX)
### BUGGY CODE ###

from sys import stdin

a = int(stdin.readline())
A=stdin.readline().split()

product=1
K=0

for k in range(0,a):
    if int(A[k])==0:
        product=0
        K=1
        break
if K==0:
   for b in range(0,a) :
       product=product*int(A[b])
   if product > 10 ** 18:
       product = -1



print(product)

### FIXED CODE ###

from sys import stdin

a = int(stdin.readline())
A=stdin.readline().split()

product=1
K=0

for k in range(0,a):
    if int(A[k])==0:
        product=0
        K=1
        break
        
if K==0:
   for b in range(0,a) :
       product=product*int(A[b])
       if product > 10 ** 18:
          product = -1
          break



print(product)
### BUGGY CODE ###

N = int(input())
S = input()

rList = []
gList = []
bList = []

for indx in range(N):
    if S[indx] == 'R':
        rList.append(indx)
    elif S[indx] == 'G':
        gList.append(indx)
    elif S[indx] == 'B':
        bList.append(indx)

NoSum = 0
fList = rList
sList = gList
remain = 'B'

for fItem in fList:
    for sItem in sList:
        if ((2 * max(fItem, sItem) - min(fItem, sItem)) <= N-1):
#            if (S[(2 * max(fItem, sItem) - min(fItem, sItem))] == remain):
            if ((2 * max(fItem, sItem) - min(fItem, sItem)) in bList):
                NoSum += 1
        
        if ((max(fItem, sItem) - min(fItem, sItem)) % 2 == 0):
#            if (S[int((max(fItem, sItem) + min(fItem, sItem))/2)] == remain):
            if (int((max(fItem, sItem) + min(fItem, sItem))/2) in bList):
                NoSum += 1
        
        if ((2 * min(fItem, sItem) - max(fItem, sItem)) >= 0):
#            if  (S[(2 * min(fItem, sItem) - max(fItem, sItem))] == remain):
            if  ((2 * min(fItem, sItem) - max(fItem, sItem)) in bList):
                NoSum += 1

print(len(rList) * len(gList) * len(bList) - NoSum)

### FIXED CODE ###

N = int(input())
S = input()

rList = []
gList = []
bList = []

for indx in range(N):
    if S[indx] == 'R':
        rList.append(indx)
    elif S[indx] == 'G':
        gList.append(indx)
    elif S[indx] == 'B':
        bList.append(indx)

NoSum = 0
fList = rList
sList = gList
remain = 'B'

for fItem in fList:
    for sItem in sList:
        prsMax = max(fItem, sItem)
        prsMin = min(fItem, sItem)
        if ((2 * prsMax - prsMin) <= N-1):
            if (S[(2 * prsMax - prsMin)] == remain):
                NoSum += 1
        
        if ((prsMax - prsMin) % 2 == 0):
            if (S[int((prsMax + prsMin)/2)] == remain):
                NoSum += 1
        
        if ((2 * prsMin - prsMax) >= 0):
            if  (S[(2 * prsMin - prsMax)] == remain):
                NoSum += 1

print(len(rList) * len(gList) * len(bList) - NoSum)
### BUGGY CODE ###

x=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
for a in A:
    ans*=a
if ans<=x:
    print(ans)
else:
    print(-1)

### FIXED CODE ###

x=10**18
n=int(input())
A=list(map(int,input().split()))
ans=1
if 0 in A:
    ans=0
else:
    for a in A:
        ans*=a
        if ans>x:
            ans=-1
            break
print(ans)
### BUGGY CODE ###

n = int(input())
from functools import reduce
from fractions import gcd
import numpy as np
arr = np.array(list(set(map(int, input().split()))))

from collections import deque
q = deque([arr])
ans = arr.min()
mi = reduce(gcd, arr)
while len(q) > 0:
    ar = q.popleft()
    ans = min(ar.min(), ans)
    if ans <= mi:
        break
    if ans <= reduce(gcd, ar):
        continue
    for mon in ar:
        tmp = (ar - 1) % mon + 1
        if np.any(ar != tmp):
            q.append(np.unique(tmp))

print(ans)


### FIXED CODE ###

n = int(input())
from functools import reduce
from fractions import gcd
ans = reduce(gcd, (map(int, input().split())))

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

from fractions import gcd
from functools import reduce
N = int(input())
a_list = list(map(int, input().split()))

max_gcd_list = []
for i in range(N):
    new_list = a_list[:i] + (a_list[(i+1):] if i < N-1 else [])
    max_gcd = reduce(gcd, new_list[1:], new_list[0])
    max_gcd_list.append(max_gcd)
print(max(max_gcd_list))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
N = int(input())
A = list(map(int, input().split()))

L = [0] * (N+1)
R = [0] * (N+1)
for i in range(N):
    L[i+1] = gcd(L[i], A[i])
    R[N-i-1] = gcd(R[N-i], A[N-i-1])

max_m = 0
for i in range(N):
    m = gcd(L[i], R[i+1])
    if max_m < m:
        max_m = m
print(max_m)
### BUGGY CODE ###

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sumi(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, M = inpl()
H = defaultdict(lambda: [])
for _ in range(N):
    l, r = inpl()
    H[r-l+1].append(l)
Q = BIT(M+1)
ctr = N
for i in range(1,M+1):
    ctr -= len(H[i]) 
    for j in H[i]:
        Q.add(j, 1)
        Q.add(j+i, -1)
    ans = 0
    for k in range(i,M+1,i):
        ans += Q.sumi(k)
    print(ctr + ans)

### FIXED CODE ###

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sumi(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

N, M = inpl()
H = defaultdict(lambda: [])
for _ in range(N):
    l, r = inpl()
    H[r-l+1].append(l)
Q = BIT(M+1)
ctr = N
for i in range(1,M+1):
    ctr -= len(H[i]) 
    for j in H[i]:
        Q.add(j, 1)
        Q.add(j+i, -1)
    ans = 0
    for k in range(i,M+1,i):
        ans += Q.sumi(k)
    print(ctr + ans)
### BUGGY CODE ###



S = input()
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )



### FIXED CODE ###


import sys

S =  sys.stdin.readline()[:-1]
l = len(S)
# S = S[::-1]
S = list(reversed(S))

dp =[[0 ] * 13 for _ in range(l + 1)]
kurai = 1
MOD = (10 ** 9) + 7
dp[0][0] = 1

for keta in range(len(S)):
    c =S[keta]

    if c == "?":
        for j in range(0,10):
            kurai %= 13
            temp = (j * kurai) % 13
            for i in range(13):
                dp[keta + 1][(temp + i) % 13] += (dp[keta][i] )
                dp[keta + 1][(temp + i) % 13] %= MOD
    else:
        kurai %= 13

        temp = (int(c) * kurai) % 13
        for i in range(13):
            dp[keta + 1][(temp + i) % 13]  += (dp[keta][i] )
            dp[keta + 1][(temp + i) % 13] %= MOD
    kurai *= 10
    keta %= MOD
print(dp[-1][5] )