Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()

    t = [[0]*(k+1) for _ in range(n)]
    z = t[-1]
    for i in range(a[-1]+1):
        z[i] = 1

    for i in range(n-2,-1,-1):
        s = 0
        z = t[i]
        y = t[i+1]
        c = a[i] + 1
        for j in range(c):
            s += y[j]
            s %= mod
            z[j] = s

        for j in range(c,k+1):
            s += y[j] - y[j-c]
            s %= mod
            z[j] = s

    return t[0][-1]


print(main())


Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    l = k + 1

    y = [1] * (a[-1]+1) + [0] * (l-a[-1]-1)

    for i in range(n-2,-1,-1):
        z = [None] * l
        s = 0
        c = a[i] + 1
        for j in range(c):
            z[j] = s = (s + y[j]) % mod

        for j in range(c,l):
            z[j] = s = (s + y[j] - y[j-c]) % mod

        y = z

    return (y[-1] + mod) % mod


print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,p = LI()
    if n == 1:
        return p
    r = 1
    i = 2
    while 1:
        t = i**n
        if p < t:
            break
        if p % t == 0:
            r *= i
            p //= t
        elif i == 2:
            i += 1
        else:
            i += 2
    return r


print(main())


Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,p = LI()
    if n == 1:
        return p
    if math.log(p) / math.log(2) < n - 1:
        return 1
    r = 1
    i = 2
    while 1:
        t = i**n
        if p < t:
            break
        if p % t == 0:
            r *= i
            p //= t
        elif i == 2:
            i += 1
        else:
            i += 2
    return r


print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m,q = LI()
    lr = [LI_() for _ in range(m)]
    pq = [LI_() for _ in range(q)]
    ls = [set() for _ in range(n)]
    rs = [set() for _ in range(n)]
    for i in range(m):
        l,r = lr[i]
        ls[l].add(i)
        rs[r].add(i)
    for i in range(n-2,-1,-1):
        ls[i] |= ls[i+1]
    for i in range(1,n):
        rs[i] |= rs[i-1]
    rr = []
    for p,q in pq:
        rr.append(len(ls[p] & rs[q]))

    return '\n'.join(map(str, rr))




print(main())


Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

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

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m,q = LI()
    lr = [LI_() for _ in range(m)]
    pq = [LI_() for _ in range(q)]

    a = [[0]*n for _ in range(n)]

    for l,r in lr:
        a[l][r] += 1

    rui = Ruiwa(a)
    rr = []
    for p,q in pq:
        rr.append(rui.search(p,p,q,q))

    return '\n'.join(map(str, rr))




print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    s1 = s[:n]
    s2 = s[n:][::-1]
    d1 = collections.defaultdict(int)
    d2 = collections.defaultdict(int)
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s1[j]
            else:
                t2 += s1[j]
        d1[t+t2] += 1
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s2[j]
            else:
                t2 += s2[j]
        d2[t+t2] += 1
    r = 0
    for k in d2.keys():
        r += d1[k] * d2[k]


    return r


print(main())


Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    s = S()
    s1 = s[:n]
    s2 = s[n:][::-1]
    d1 = collections.defaultdict(int)
    d2 = collections.defaultdict(int)
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s1[j]
            else:
                t2 += s1[j]
        d1[t+t2] += 1
    for i in range(2**n):
        t = t2 = ','
        for j in range(n):
            if 2**j & i:
                t += s2[j]
            else:
                t2 += s2[j]
        d2[t+t2] += 1
    r = 0
    for k in d2.keys():
        r += d1[k] * d2[k]


    return r


print(main())
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,k,q = LI()
    a = LI()
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(n):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        def f(i):
            ma = sa[i]
            c = 0
            cc = 0
            g = 0
            ss = 1
            for t in a:
                if t < mi:
                    if c > k and c > cc:
                        g += c - max(k, cc)
                    ss = 0
                    c = 0
                    cc = 0
                    continue
                if t >= ma:
                    cc += 1
                c += 1
            if ss == 1 and c > cc:
                g += c - cc
            elif c > k and c > cc:
                g += c - max(k, cc)
            # print(mi, ma, cc, i, g, q)
            return g < q

        l = bs(f, 0, n+1)
        # print(i,l,mi)
        if l > n or l <= i:
            continue
        t = sa[l-1] - mi
        if r > t:
            r = t


    return r




print(main())



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k,q = LI()
    a = LI() + [-1]
    sa = sorted(a)
    r = sa[-1] - sa[0]
    # print(sorted([[a[i],i] for i in range(n)]))
    for i in range(1,n+1):
        if sa[i] == sa[i-1]:
            continue
        mi = sa[i]
        b = []
        c = 0
        for j in range(n+1):
            if a[j] < mi:
                if j - c >= k:
                    b += sorted(a[c:j])[:j-c-k+1]
                c = j + 1
        if len(b) < q:
            continue
        b.sort()
        t = b[q-1] - mi
        if r > t:
            r = t


    return r




print(main())
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a,b,c,d = I()
    if abs(a-c) <= d or (abs(a-b) <= d and abs(b-c) <= d):
        return 'Yes'

    return 'No'



print(main())



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    a,b,c,d = LI()
    if abs(a-c) <= d or (abs(a-b) <= d and abs(b-c) <= d):
        return 'Yes'

    return 'No'



print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [[c for c in S()] for _ in range(n)]
    r = 0
    for i in range(n):
        b = [[a[ii][(j+i)%n] for j in range(n)] for ii in range(n)]
        f = True
        for ii in range(n):
            for jj in range(ii+1,n):
                if b[ii][jj] != b[jj][ii]:
                    f = False
                    break
            if not f:
                break
        if f:
            r += 1

    return r * n




print(main())



Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = [[c for c in S()] for _ in range(n)]
    r = 0
    for i in range(n):
        b = [[a[ii][(j+i)%n] for j in range(n)] for ii in range(n)]
        f = True
        for ii in range(n):
            for jj in range(ii+1,n):
                if b[ii][jj] != b[jj][ii]:
                    f = False
                    break
            if not f:
                break
        if f:
            r += 1

    return r * n




print(main())
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a,b = I()
    if min(a % 3, b%3, (a+b)%3) == 0:
        return 'Possible'

    return 'Impossible'


print(main())





Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    a,b = LI()
    if min(a % 3, b%3, (a+b)%3) == 0:
        return 'Possible'

    return 'Impossible'


print(main())
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    H,W,h,w = LI()
    f = False
    if H % h == 0 and W % w == 0:
        return 'No'
    if W % w == 0:
        H,W,h,w = W,H,w,h
        f = True

    p = 10**6*(w-1) - 1
    m = -(10**6)
    a = []
    for i in range(W):
        if i % w == 0:
            a.append(p)
        else:
            a.append(m)
    aa = [a] * H
    r = aa
    if f:
        r = [[aa[i][j] for i in W] for j in H]

    return 'Yes\n' + '\n'.join(' '.join(map(str,t)) for t in r)


print(main())


Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    H,W,h,w = LI()
    f = False
    if H % h == 0 and W % w == 0:
        return 'No'
    if W % w == 0:
        H,W,h,w = W,H,w,h
        f = True

    p = 10**6*(w-1) - 1
    m = -(10**6)
    a = []
    for i in range(W):
        if i % w == 0:
            a.append(p)
        else:
            a.append(m)
    aa = [a] * H
    r = aa
    if f:
        r = [[aa[i][j] for i in range(H)] for j in range(W)]

    return 'Yes\n' + '\n'.join(' '.join(map(str,t)) for t in r)


print(main())
Buggy python submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
 
def main():
    n = I()
    a = sorted([sorted(LI()) + [_] for _ in range(n)])
    b = sorted(a, key=lambda x: x[1])
    r = (a[-1][0]-a[0][0]) * (b[-1][1]-b[0][1])
 
 
    bm = b[-1][1] - a[0][0]
    bmi = b[0][2]
    am = a[-1][1]
    at = 0
    k = [[inf,0]]
    for i in range(n-1):
        kk = []
        kk.append(min(k[-1][0], b[i][0], b[i+1][1]))
        kk.append(max(k[-1][1], b[i][0]))
        if kk[0] == k[-1][0]:
            k[-1][1] = kk[1]
        else:
            k.append(kk)
 
    k = k[1:]
    kl = len(k)
 
    am = b[-1][1] - a[0][0]
    ami = a[0][2]
    bm = 0
    mtm = 0
    bt = b[0][1]
 
    for i in range(n-1,0,-1):
        tm = b[i][0]
        if mtm < tm:
            mtm = tm
        if ami == b[i][2]:
            break
        if tm < bt:
            bt = tm
        if tm < b[i-1][1]:
            tm = b[i-1][1]
        bm = mtm
        if tm > bm:
            bm = tm
 
        tr = am * (bm-bt)
        if r > tr:
            r = tr
 
        for j in range(kl):
            ki,km = k[j]
            if km > bm:
                break
            tr = am * (bm-min(ki,bt))
            if r > tr:
                r = tr
 
    return r
 
 
print(main())

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n,t = LI()
    a = LI()
    s = 0
    c = 0
    r = 0
    for b in a:
        if c < b:
            r += c - s
            s = b
            c = b+t
        else:
            c = b+t
    r += c-s

    return r


print(main())