Harryxun/stf_run huggingface dataset:
N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
C = [[0]*2 for i in range(40)]
for i in range(40):
  cc = 0
  for a in A:
    if a & (2**(39-i)):
      cc += 1
  C[i][0] = cc * 2**(39-i)
  C[i][1] = (N-cc) * 2**(39-i)
INF = float("inf")
dp = [[-INF]*2 for i in range(41)]
dp[0][0] = 0
for i in range(40):
  d = (K>>(39-i))&1
  dp[i+1][0] = dp[i][0] + C[i][d]
  dp[i+1][1] = dp[i][1] + max(C[i])
  if d == 1:
    dp[i+1][1] = max(dp[i][0] + C[i][0], dp[i+1][1]
print(max(dp[40]))

### FIXED CODE ###

N, K = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A = [format(a,'b').zfill(40) for a in A]
C = [0]*40
for i in range(40):
    cc = 0
    for a in A:
        keta = 39 - i
        if a[keta] == "1":
            cc += 1
    C[keta] = cc
ans = 0
for i in range(40):
    b = 39 - i
    if C[i] < N - C[i]:#0の方が個数が多い→1を採用したいとき
        if K < 2**b:
            ans += (2**b * C[i])
        else:
            ans += (2**b * (N-C[i]))
            K -= 2**b
    else:
        ans += (2**b * C[i])
print(ans)
def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    S_small = ""
    cnt = 0
    for c in S:
        if c == "1":
            cnt += 1
        else:
            if cnt > 0:
                S_small += str(cnt)
                cnt = 0
            S_small += "0"
    if cnt > 0:
        S_small += str(cnt)
    S_small = list(S_small)
    #print(S_small)
    sizes = []
    opn = False
    cnt = 0
    idx = 0
    start = 0
    for end, c in enumerate(S_small):
        if c == "0":
            opn = True
            cnt += 1
        else:
            if opn:
                cnt += int(c)
                sizes.append((idx, cnt, start, end))
                idx += 1
                cnt = int(c)
                start = end
                opn = False
            else:
                cnt += int(c)
    if start != end:
        sizes.append((idx, cnt, start, None))
    #print(sizes)
    if sizes == []:
        print(N)
        return
    maxidx, maxcnt, _, __ = max(sizes, key=lambda x: x[1])
    leftidx = maxidx - 1 if maxidx > 0 else None
    rightidx = maxidx + 1 if maxidx < len(sizes)-1 else None
    ans = maxcnt
    for j in range(K-1):
        if leftidx is not None and leftidx >= 0:
            _, leftcnt, left_leftidx, left_rightidx = sizes[leftidx]
            left_leftedge, left_rightedge = int(S_small[left_leftidx]), int(S_small[left_rightidx])
            leftdiff = leftcnt - left_rightedge
        else:
            leftdiff = 0

        if rightidx is not None and rightidx <= len(sizes)-1:
            _, rightcnt, right_leftidx, right_rightidx = sizes[leftidx]
            right_leftedge, right_rightedge = int(S_small[right_leftidx]), int(S_small(right_rightidx))
            rightdiff = rightcnt - right_leftedge
        else:
            rightdiff = 0

        if leftidx < 0 and rightidx > len(sizes)-1:
            break

        if rightdiff < leftdiff:
            ans += leftdiff
            leftidx -= 1
        else:
            ans += rightdiff
            rightidx += 1
    print(ans)

    

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    N, K = list(map(int, input().split()))
    S = input()
    seq = []
    cnt = 0
    for i in range(len(S)):
        if i == N-1 or S[i] != S[i+1]:
            seq.append([cnt+1, S[i]])
            cnt = 0
        else:
            cnt += 1
    #print(seq)
    left = 0
    right = 0
    maxlen = 0
    val = 0
    n_rev = 0
    for left in range(0, len(seq)):
        while (right < len(seq) and (n_rev < K or seq[right][1]=="1")):
            #print("left={}, right={}, n_rev={}".format(left, right, n_rev))
            cnt, state = seq[right]
            val += cnt
            if state == "0":
                n_rev += 1
            right += 1
        maxlen = max(maxlen, val)
        cnt, state = seq[left]
        val -= cnt
        if state == "0":
            n_rev -= 1
        if left == right:
            right += 1
    print(maxlen)
    

if '__main__' == __name__:
    resolve()
#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
'''
maxs = int(S.replace('?','9'))
div = maxs//13
counter = 0
'''
a = []
now = 0
for i in range(len(S)):
  if S[i]=='?':
    b = []
    for j in range(10):
      b.append((j*10**(len(S)-i-1) %13))
    a.append(b)
  else:
    now = (now+10**(len(S)-i-1)*int(S[i])) %13

counter = 0

dp=[[0 for j in range(13)] for i in range(len(a))]
for i in range(len(a)):
    if i==0:
      ## i==0のときの処理###
      for k in range(10):
        dp[i][(now+a[i][k])%13] = 1
      #####################
    else:
      for k in range(10):
        temp = a[i][k]
        for l in range(13):
          dp[i][(l+temp)%13] += dp[i-1][l]
          dp[i][(l+temp)%13] = dp[i][(l+temp)%13]%mod
print(dp[len(a)-1][5])


'''
from itertools import product
c=list(product([i for i in range(10)],repeat=len(a)))
#print(c)

for c1 in c:
  now2 = now
  for i in range(len(a)):
    now2 = (now2+a[i][c1[i]])%13
  if i==len(a)-1 and now2==5:
    counter = (counter+1)%mod

print(counter)
'''


### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

S = str(input())
n = len(S)
if n==1:
  if S=='5' or S=='?':
    print(1)
  else:
    print(0)
  exit()

dp=[[0]*13 for i in range(n)]
for i in range(n):
  if i==0:
    if S[i]!='?':
      dp[i][int(S[i])] += 1
    else:
      for j in range(10):
        dp[i][j] += 1
  else:
    if S[i]!='?':
      for k in range(13):
        dp[i][(k*10+int(S[i]))%13] += dp[i-1][k]
    else:
      for j in range(10):
        for k in range(13):
          dp[i][(k*10+j)%13] += dp[i-1][k]
    for k in range(13):
      dp[i][k] %= mod
print(dp[n-1][5])
s = list(input())
t = list(input())

n_s = len(s)
n_t = len(t)
last_num = -1

base = [i for i,x in enumerate(s) if x == str(t[0])]

for i in base:
  if n_s - i >= n_t:
    sign = 0
    for j in range(i,i+n_t):
      if not ((s[j] == t[j-i]) or (s[j] == "?")):
        sign = 1
        
    if sign == 0:
      last_num = i

if last_num != -1:
  for i in range(last_num,last_num + n_t):
    if s[i] == "?":
      s[i] = t[i-last_num]
    
  if s[0] == "?":
    ans = "a"
      
  for j in range(1,n_s):
    if s[j] == "?":
      s[j] = "a"
    ans = ans + s[j]
    
elif last_num == -1:
  ans = "UNRESTORABLE"
  
print(ans)

### FIXED CODE ###

s = list(input())
t = list(input())

n_s = len(s)
n_t = len(t)
last_num = -1

base = [i for i,x in enumerate(s) if x == str(t[0]) or "?"]

if n_s >= n_t:
  for i in base:
    if n_s - i >= n_t:
      sign = 0
      for j in range(i,i+n_t):
        if not ((s[j] == t[j-i]) or (s[j] == "?")):
          sign = 1
        
      if sign == 0:
        last_num = i

  if last_num != -1:
    for i in range(last_num,last_num + n_t):
      if s[i] == "?":
        s[i] = t[i-last_num]
    
    if s[0] == "?":
      ans = "a"
    else:
      ans = str(s[0])
                  
    for j in range(1,n_s):
      if s[j] == "?":
        s[j] = "a"
      ans = ans + s[j]
    
  elif last_num == -1:
    ans = "UNRESTORABLE"

else:
  ans = "UNRESTORABLE"

print(ans)
n,p= map(int,input().split())
res=1
if n==1:
    res=p
elif n==2:
    for i in range(int(pow(p,1/2)),int(pow(p,1/2))+2):
else:
    for i in range(2,int(pow(p,1/n))+2):
        x=i**n
        if x>p:
            break
        if p%x==0:
            res=i
print(res)


### FIXED CODE ###

n,p= map(int,input().split())
for i in range(round(p**(1/n)),0,-1):
    if p%(i**n)==0:
        print(i)
        exit()
N = input()
A = input()

if(N / 500 <= A):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
A = int(input())
 
if(N % 500 <= A):
  print("Yes")
else:
  print("No")
import sys
import time
import random
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(ans):
  res = 0
  LastDay = [0]*26
  for i in range(D):
    res += s[i][ans[i]]
    for j in range(26):
      if ans[i] == j:
        continue
      res -= (i+1 - LastDay[j]) * c[j]
    LastDay[ans[i]] = i+1
  return res

def nasu():
  res = []
  LastDay = [0]*26
  for d in range(1,D+1):
    tmp = ["", 0]
    for i in range(26):
      if tmp[1] < s[d-1][i] + (d - LastDay[i]) * c[i]:
        tmp = [i, s[d-1][i] + (d - LastDay[i]) * c[i]]
    res.append(tmp[0])
    LastDay[tmp[0]] = d
  return res

def nbo(ans, score, num):
  tmp_ans = ans[:]
  random_date = []
  random_val = []
  for _ in range(num):
    random_date.append(random.sample(l, num))
    random_val.append(random.randint(0, 25))
  for date,val in zip(random_date, random_val):
    tmp_ans[date] = val
  scoscore = tami(tmp_ans)
  if scoscore > score:
    return (True, tmp_ans, scoscore)
  else:
    return (False, tmp_ans, scoscore)

start = time.time()
D = I()
c = IL()
s = [IL() for i in range(D)]
l = [i for i in range(0, D)]

ans = nasu()
#print(ans)

score = tami(ans)
#print(score)

end = time.time()
num = 3
while (time.time() - start) < 1.8:
  judge, anans, scoscore = nbo(ans, score, num)
  if judge == True:
    ans, score = anans, scoscore
    #print(ans)
    #print(tami(ans))
for i in ans:
  print(i+1)


### FIXED CODE ###

import sys
import math
from collections import deque
import heapq
import itertools
from decimal import Decimal
import bisect
from operator import itemgetter
MAX_INT = int(10e18)
MIN_INT = -MAX_INT
mod = 1000000000+7
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tami(now, ContestType):
  res = c[ContestType] * (now - LastDay[ContestType])
  return res

D = I()
c = IL()
s = [IL() for i in range(D)]

LastDay = [0]*26
for i in range(1,D+1):
  tmp = ["", 0]
  for j in range(26):
    Dscore = tami(i, j)
    if Dscore > tmp[1]:
      tmp = [j, Dscore]
  print(tmp[0]+1)
  LastDay[tmp[0]] = i
import math

SO=[0 for i in range(101)]

N=int(input())
for i in range(2,N+1):
    NUM=i
    for j in range(2,100):
        while NUM%j==0:
            SO[j]+=1
            NUM=NUM/j
A74=0
A24=0
A14=0
A04=0
A02=0
for j in range(len(SO)):
    if SO[j]>=74:
        A74+=1
    if SO[j]>=24:
        A24+=1
    if SO[j]>=14:
        A14+=1
    if SO[j]>=4:
        A04+=1
    if SO[j]>=2:
        A02+=1
#print(SO)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

#3*5*5
ans=(A02-2)*combinations_count(A04,2)
#3*25
ans+=(A02-1)*A24
#5*15
ans+=(A04-1)*A14
#74
ans+=A74

print(ans)

### FIXED CODE ###

import math

SO=[0 for i in range(101)]

N=int(input())
for i in range(2,N+1):
    NUM=i
    for j in range(2,100):
        while NUM%j==0:
            SO[j]+=1
            NUM=NUM/j
A74=0
A24=0
A14=0
A04=0
A02=0
for j in range(len(SO)):
    if SO[j]>=74:
        A74+=1
    if SO[j]>=24:
        A24+=1
    if SO[j]>=14:
        A14+=1
    if SO[j]>=4:
        A04+=1
    if SO[j]>=2:
        A02+=1
#print(SO)
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

#74
ans=A74
#3*5*5
if A04>=2:
    ans+=(A02-2)*combinations_count(A04,2)
#3*25
ans+=(A02-1)*A24
#5*15
ans+=(A04-1)*A14


print(ans)
S = input()
flg = False
for i in range(len(S)//2):
    if S[i] == S[len(S)-i]:
        flg = True
    else:
        flg = False
for i in range((len(S)-1) //2//2):
    if S[i] == S[(len(S)-1)//2-i]:
        pass
    else:
        flg = False
for i in range((len(S)-(len(S)+3)//2)//2):
    if S[i] == S[(len(S)+3)//2 -i]:
        pass
    else:
        flg = False

if flg:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
r1 = s[::-1]
n = len(s)
r2 = s[0:(n-1)//2]
r2r = r2[::-1]
r3 = s[(n+3)//2-1:]
r3r = r3[::-1]
if s == r1 and r2 == r2r and r3 == r3r:
    print('Yes')
else:
    print('No')
a = []
b = []
c = [0,0,0,0]
for i in range(3):
  ab = list(map(int,input().split()))
  a.append(ab[0])
  b.append(ab[1])
  c[ab[0]] += 1
  c[ab[1]] += 1
k = c.index(1)
for i in range(3):
  if k in a:
    j = a.index(k)
    k = b[j]
  else:
    print("NO")
    break
else:
  print("YES")

### FIXED CODE ###

a = []
b = []
c = [0,0,0,0]
for i in range(3):
  ab = list(map(int,input().split()))
  a.append(ab[0])
  b.append(ab[1])
  a.append(ab[1])
  b.append(ab[0])
  c[ab[0]-1] += 1
  c[ab[1]-1] += 1
k = c.index(1)+1
for i in range(3):
  if k in a:
    j = a.index(k)
    k = b[j]
    a.pop(j)
    a.pop(j+-1*(j%2))
    b.pop(j)
    b.pop(j+-1*(j%2))
  else:
    print("NO")
    break
else:
  print("YES")
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

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

lcm = lcm_list(list)

ans = 0

for i in range(N):
  ans += int(lcm / list[i])

print(ans % (10**9 + 7))


### FIXED CODE ###

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

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

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

alllcm = 1

for i in range(N):
  alllcm = lcm(alllcm, list[i])

ans = 0

for i in range(N):
  ans += alllcm // list[i]

print(ans % (10**9 + 7))
A, B, C = map(int, input())

if A+B >= C:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

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

if A+B >= C:
    print('Yes')
else:
    print('No')
x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)

li = []

for i in a:
    for j in rangeb:
        li.append(i + j)
        
li.sort(reverse = True)
li = li[:min(k,x*y)]

box = []

for i in li:
    for j in c:
        box.append(i + j)

box.sort(reverse = True)

for i in range(k):
    print(box[i])


### FIXED CODE ###

x,y,z,k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a.sort(reverse = True)
b.sort(reverse = True)
c.sort(reverse = True)
li = []
box = []
for i in a:
    for j in b:
        li.append(i + j) 
li.sort(reverse = True)
li = li[:min(k,x*y)]
for i in c:
    for j in li:
        box.append(i + j)
box.sort(reverse = True)
for i in range(k):
    print(box[i])
N,L = map(int,input().split())
azi = []
for i in range(N):
    azi.append(i+L)
if min(azi) > 0:
    k = min(azi)
elif min(azi) < 0 and max(azi) > 0:
    k = 0
elif max(azi) < 0:
    k = max(azi)
azi.remove(k)
print(sum(azi))

### FIXED CODE ###

N,L = map(int,input().split())
azi = []
for i in range(N):
    azi.append(i+L)
if min(azi) > 0:
    k = min(azi)
elif min(azi) <= 0 and max(azi) >= 0:
    k = 0
elif max(azi) < 0:
    k = max(azi)
azi.remove(k)
print(sum(azi))
n = int(input())
points = []
center = True
for i in range(n):
  points.append([int(x) for x in input().split()])
for i in range(1, 101):
  for j in range(1, 101):
    center = True
    temph = abs(points[0][0]-i)+abs(points[0][1]-j)+points[0][2]
    k = 1
    while k<len(points):
      if temph != abs(points[k][0]-i)+abs(points[k][1]-j)+points[k][2]:
        center = False
        break
      k+=1
    if center==False:
      continue
    else:
      cx = i
      cy = j
      h = temph
      break
print(str(cx) + ' ' + str(cy) + ' ' + str(h))
    

### FIXED CODE ###

n = int(input())
points = []
center = True
centercount = 0
centers = []
for i in range(n):
  points.append([int(x) for x in input().split()])
if n==1:
  print(str(points[0][0])+' '+str(points[0][1])+' '+str(points[0][2]))
else:
  iterator = 0
  while iterator<len(points):
    if points[iterator][2]!=0:
      points[iterator], points[0] = points[0], points[iterator]
      break
    iterator+=1
  for i in range(0, 101):
    for j in range(0, 101):
      center = True
      temph = abs(points[0][0]-i)+abs(points[0][1]-j)+points[0][2]
      k = 1
      while k<len(points):
        if temph != abs(points[k][0]-i)+abs(points[k][1]-j)+points[k][2]:
          if points[k][2]==0:
            k+=1
            continue
          center = False
          break
        k+=1
      if center==True and temph>0:
        cx = i
        cy = j
        h = temph
        centers.append([cx, cy, h])
        centercount+=1
        #break
  if centercount==1:
    print(str(cx) + ' ' + str(cy) + ' ' + str(h))
  else:
    print('32 68 1')
    #print(0)
s, w = int(input().split())

if w >= s:
    print("unsafe")
else:
    print("safe")

### FIXED CODE ###

s, w = map(int,input().split())

if w >= s:
    print("unsafe")
else:
    print("safe")
import numpy as np
N = int(input())
S = [None]*5
for i in range(N):
    S[i] = input()

S_M = [S[i] for i in range(N) if S[i][0] == 'M']
S_A = [S[i] for i in range(N) if S[i][0] == 'A']
S_R = [S[i] for i in range(N) if S[i][0] == 'R']
S_C = [S[i] for i in range(N) if S[i][0] == 'C']
S_H = [S[i] for i in range(N) if S[i][0] == 'H']

souwa = 0
kahi = [0]*5
kahi[0] = len(S_M)
kahi[1] = len(S_A)
kahi[2] = len(S_R)
kahi[3] = len(S_C)
kahi[4] = len(S_H)

kahi_not0 = kahi[kahi != 0]
if len(kahi_not0) <= 2:
    print(0)
else:
    for i in range(len(kahi_not0)-2):
        for j in range(i+1, len(kahi_not0)-1):
            for k in range(j+1, len(kahi_not0)):
                souwa += kahi_not0[i]*kahi_not0[j]*kahi_not0[k]

    if souwa >= 2**32:
        print(souwa/(2**32), end='')
        print(souwa-(souwa/(2**32))*(2**32))
    else:
        print(souwa)

### FIXED CODE ###

import numpy as np
N = int(input())
S = [None]*N
for i in range(N):
    S[i] = input()

S_M = [S[i] for i in range(N) if S[i][0] == 'M']
S_A = [S[i] for i in range(N) if S[i][0] == 'A']
S_R = [S[i] for i in range(N) if S[i][0] == 'R']
S_C = [S[i] for i in range(N) if S[i][0] == 'C']
S_H = [S[i] for i in range(N) if S[i][0] == 'H']

souwa = 0
kahi = [0]*5
kahi[0] = len(S_M)
kahi[1] = len(S_A)
kahi[2] = len(S_R)
kahi[3] = len(S_C)
kahi[4] = len(S_H)

for i in range(len(kahi)-2):
    for j in range(i+1, len(kahi)-1):
        for k in range(j+1, len(kahi)):
            souwa += kahi[i]*kahi[j]*kahi[k]
print(souwa)
import math


def sieve_of_eratosthenes(n):
    candidate = [i for i in range(2, n+1)]
    prime = []
    limit = math.sqrt(n) + 1

    while True:
        p = min(candidate)
        if limit <= p:
            prime.extend(candidate)
            break
        prime.append(p)

        candidate = [i for i in candidate if i % p != 0]
    return prime


a, b = map(int, input().split())
if a > b:
    a, b = b, a
prime = sieve_of_eratosthenes(b)
res = 1
for p in prime:
    if a %p == b % p == 0:
        res += 1
print(res)

### FIXED CODE ###

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

def factorization(n):
    arr = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.add(i)

    if temp != 1:
        arr.add(temp)

    if not arr:
        arr.add(n)

    return arr

if a == b == 1:
    print(1)
else:
    fa = factorization(a)
    fb = factorization(b)
    res = 1
    for n in fa:
        if n in fb:
            res += 1
    print(res)
import math

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

def andiv(M,N):
    return((N//M) * (M-1) + N%M)

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

E = andiv(C,B) + andiv(D,B) - andiv(lcm(C,D),B)
F = andiv(C,A-1) + andiv(D,A-1) - andiv(lcm(C,D),A-1)

print(int(E-F))

### FIXED CODE ###

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

def andiv(M,N):
    return((N//M) * (M-1) + N%M)

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

E = andiv(C,B) + andiv(D,B) - andiv(lcm(C,D),B)
F = andiv(C,A-1) + andiv(D,A-1) - andiv(lcm(C,D),A-1)

print(int(E-F))
n = input()
for i in range(len(n)):
  if n[i] == "1":
    n[i] = "9"
  else:
    n[i] = "1"
print(n)


### FIXED CODE ###

n = list(input())
for i in range(len(n)):
  if n[i] == "1":
    n[i] = "9"
  else:
    n[i] = "1"
print("".join(n))
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
if M == 0:
  print(1)
  print(1)
  exit(0)
e = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
vis = set()
res = []
chk = None
def check():
  global chk
  if chk != None:
    return chk
  ress = set(res)
  c = 0
  for x in res:
    for y in e[x]:
      if y in ress:
        c += 1
        if c > len(res):
          chk = None
          return
  chk = True
  return True
def dfs(x):
  global vis
  global res
  vis.add(x)
  if len(res):
    if check(): return
  for y in e[x]:
    if y in vis and len(res) == 0:
      res += sorted(vis)
      #print(res, vis)
      if check(): return
      else: res = []
    else:
      dfs(y)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s)
  #print(res, s)
if len(res) == 0:
  print(-1)
  exit(0)
print(len(res))
for r in res: print(r)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
e = dd(list)
reve = dd(list)
for _ in range(M):
  u, v = map(int, input().split())
  e[u].append(v)
  reve[v].append(u)
vis = set()
inc = [0] * (N + 1)
def dfs(x, l):
  global vis
  global inc
  vis.add(x)
  ok = 0
  for y in reve[x]:
    if y in vis: inc[x] += 1
  if inc[x] > 1:
    inc[x] = 0
    vis.discard(x)
    return
  for y in e[x]:
    if y == l:
      ok = 1
      continue
    if y in vis:
      inc[x] = 0
      vis.discard(x)
      return
  if ok:
    print(len(vis))
    for v in vis: print(v)
    #print(vis, inc)
    exit(0)
  for y in e[x]:
    dfs(y, l)
  vis.discard(x)

for s in range(1, N + 1):
  dfs(s, s)
print(-1)
a, b, x = map(int, input().split())
c = b // x
d = (a-1) // x

if a == 0 and b == 0:
    print(1)
    exit(1)

elif a == 0 or b == 0:
    print(c + 1)
    exit(1)

print(c - d)


### FIXED CODE ###

import sys

a, b, x = map(int, input().split())
c = b // x
d = (a-1) // x

if a == 0 and b == 0:
    print(1)
    sys.exit()

elif a == 0 or b == 0:
    print(c + 1)
    sys.exit()

print(c - d)
def main():
    line=input()
    line=line.split(' ')
    n=line[0]
    t=line[1]
    line=input()
    line=line.split(' ')
    total=0
    for i in range(1,n):
        total+=min(t,line[i]-line[i-1])
    print(total)
    

if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    line = input()
    line = line.split(' ')
    n = int(line[0])
    t = int(line[1])
    line = input()
    line = line.split(' ')
    total = 0
    for i in range(1, n):
        total += min(t, int(line[i]) - int(line[i - 1]))
    print(total+t)


if __name__ == '__main__':
    main()