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

import re
import sys
from collections import (
    Counter,
    defaultdict as ddict,
    deque,
    namedtuple as ntuple,
)
from functools import lru_cache
from heapq import *
from itertools import *
from pprint import pprint
from statistics import *
from string import (
    ascii_letters as letters,
    ascii_lowercase as ucletters,
    ascii_uppercase as lcletters,
    digits,
)

cache=lru_cache(None)

hexdigits=digits+'ABCDEFabcdef'

inf=float('inf')
int8_min=-128
int16_min=-32768
int32_min=-2147483648
int64_min=-9223372036854775808
int8_max=127
int16_max=32767
int32_max=2147483647
int64_max=9223372036854775807
uint8_max=255
uint16_max=65535
uint32_max=4294967295
uint64_max=18446744073709551615
ansmod=1000000007

rfs=lambda:rl().split()
ri=lambda:int(rl())
ris=lambda:list(map(int,rfs()))
rl=lambda:next(sys.stdin)
rrs=lambda:list(map(str.strip,sys.stdin))
rs=lambda:rl().strip()
rt=lambda:sys.stdin.read()
rg=lambda:list(map(list,rrs()))
rig=lambda:[[*map(int,x.split())] for x in rls()]

def nbs4(i,j):
    return [
                (i-1,j),
        (i,j-1),        (i,j+1),
                (i+1,j),
    ]

def nbs8(i,j):
    return [
        (i-1,j-1),(i-1,j),(i-1,j+1),
        (  i,j-1),        (  i,j+1),
        (i+1,j-1),(i+1,j),(i+1,j+1),
    ]

inb=lambda i,j,m,n:0<=i<m and 0<=j<n

sys.setrecursionlimit(int32_max)

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

H,W=ris()
S=rg()

xs=[[0]*W for _ in range(H)]
ys=[[0]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]!='#':
            if j==0:
                xs[i][j]=1
            else:
                xs[i][j]+=1+xs[i][j-1]
            if i==0:
                ys[i][j]=1
            else:
                ys[i][j]+=1+ys[i-1][j]

#pprint(xs, width=60)
#pprint(ys, width=60)

ans=0
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if S[i][j]=='#':
            continue
        if j+1<W:
            xs[i][j]=max(xs[i][j],xs[i][j+1])
        if i+1<H:
            ys[i][j]=max(ys[i][j],ys[i+1][j])
        x=xs[i][j]
        y=ys[i][j]
        ans=max(ans,x+y-1)


print(ans)


### FIXED CODE ###

import sys

H,W=map(int,next(sys.stdin).split())

xs=[[0]*(W+2) for _ in range(H+2)]
ys=[[0]*(W+2) for _ in range(H+2)]
for i in range(1,H+1):
    row=next(sys.stdin)
    for j in range(1,W+1):
        if row[j-1]!='.': continue
        xs[i][j]=1+xs[i][j-1]
        ys[i][j]=1+ys[i-1][j]

ans=0
for i in range(H,0,-1):
    for j in range(W,0,-1):
        if xs[i][j]==0: continue
        x=xs[i][j]=max(xs[i][j],xs[i][j+1])
        y=ys[i][j]=max(ys[i][j],ys[i+1][j])
        ans=max(ans,x+y-1)

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

n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

x_i = int(x, 2)
x_orig = popcount(x_i)
solve = 0
for i in range(n):
    x_count = x_orig
    if x[i] == "0":
        solve = x_i+2**(n-i-1)
        x_count += 1
    else:
        solve = x_i-2**(n-i-1)
        x_count -= 1
    count = 0

    if solve != 0 :
        solve = solve % x_count
        count+=1

    while solve > 0:
        solve = solve % popcount(solve)
        count+=1

    print(count)

### FIXED CODE ###


n = int(input())
x = input()

def popcount(ni):
    n_b = str(bin(ni))
    return n_b.count("1")

def ans(n,x):
    x_i = int(x, 2)
    x_orig = popcount(x_i)
    x_i_t = x_i % (x_orig+1)
    if x_orig != 1:
        x_i_b = x_i % (x_orig-1)
    else:
        x_i_b = x_i
    solve = 0
    for i in range(n):
        x_count = x_orig
        if x[i] == "0":
            x_count += 1
            solve = x_i_t + pow(2,n-1-i,x_count)
        else:
            x_count -= 1
            if x_count != 0:
                solve = x_i_b - pow(2,n-1-i,x_count)
            else:
                print(0)
                continue
        count = 0

        if x_count != 0 :
            solve = solve % x_count
            count+=1

        while solve > 0:
            solve = solve % popcount(solve)
            count+=1

        print(count)

    
ans(n,x)
### BUGGY CODE ###

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

target_number=1
i=0

while len(numbers)>i+1:
  if(target_number in numbers):
    del numbers[i:numbers.index(target_number)]
    i+=1
    target_number+=1
  else:
    del numbers[i:]
  
if(len(numbers)>1):
  print(N-len(numbers))
  
elif(len(numbers)==1):
  if(numbers[0]==1):
    print(N-1)
  elif(numbers[0]!=1):
    print(-1)
    
elif(len(numbers)==0):
  print(-1)

### FIXED CODE ###

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

target_number=1

for i in range(N):
  if(numbers[i]==target_number):
    target_number+=1
  
if(target_number>1):
  print(N-target_number+1)
  
elif(target_number==1):
  if(1 in numbers):
    print(N-1)
  else:
    print(-1)
### BUGGY CODE ###

n,m = map(int,input().split())
py_list = [list(map(int,input().split())) for nesya in range(m)]
py_sort = sorted(py_list,key=lambda x: x[1])
ho = [0]*(n+1)
for py1 in py_sort:
  ho[py1[0]] += 1
  py1.append(ho[py1[0]])
for py in py_list:
  for i in range(m):
    if py[1] == py_sort[i][1]:
      print(str(py[0]).zfill(6)+str(py_sort[i][2]).zfill(6))
      break

### FIXED CODE ###

n,m = map(int,input().split())
pyl = [list(map(int,input().split())) for nesya in range(m)]
predic = dict()
ydic = dict()
spyl = sorted(pyl,key = lambda x:x[1])
for py in spyl:
  p = py[0]
  y = py[1]
  if p in predic:
    predic[p] += 1
  else:
    predic[p] = 1
  ydic[y] = (str(p).zfill(6))+(str(predic[p]).zfill(6))
for hoge in pyl:
  print(ydic[hoge[1]])
### BUGGY CODE ###

import math

K = int(input())
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):

            ans += math.gcd(math.gcd(a, b), c)

print(ans)

### FIXED CODE ###

import math

K = int(input())
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):

            ans += math.gcd(math.gcd(a, b), c)

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

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]

    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    while True:
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import time
def main():
    N = int(input())
    a = [list(map(int, input().split())) for i in range(N)]
    start = time.time()
    now = [0] * N
    day = 0
    gamed_day = [-1] * N
    finished = 0
    while True:
        if time.time() - start > 1.6:
            print((N*(N-1))//2)
            break
        had_game = False
        all_finish = True
        for i in range(N-1, -1, -1):
            if now[i] < N-1 and gamed_day[i] != day:
                all_finish = False
                want = a[i][now[i]] - 1
                if gamed_day[want] != day:# 今日試合していない
                    if a[want][now[want]] - 1 == i:# 相手の試合相手が自分
                        now[want] += 1
                        now[i] += 1
                        if now[want] >= N-1:
                            finished += 1
                        if now[i] >= N-1:
                            finished += 1
                        gamed_day[i] = day
                        gamed_day[want] = day
                        had_game = True
                        # print(day+1, i+1, want+1)
        if all_finish or finished == N:
            if had_game:
                print(day+1)
            else:
                print(day)
            break
        if not had_game:
            print(-1)
            break
        day += 1
    # print(now)

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

from collections import deque

H, W = map(int, input().split())
G = []
for i in range(H):
    s = list(input())
    G.append(s)
# print(G)


dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]


INF = 10 ** 18 + 10


def bfs(i, j):
    d = [[INF for k in range(W)] for l in range(H)]
    q = deque()
    q.append((i, j))
    d[i][j] = 0
    cnt = 1
    while q:
        a, b = q.popleft()
        for k in range(4):
            to_w = max(0, min(W - 1, b + dx[k]))
            to_h = max(0, min(H - 1, a + dy[k]))
            if G[to_h][to_w] == "#":
                continue
            if d[to_h][to_w] != INF:
                continue
            if to_w != j and to_h != i:
                continue
            d[to_h][to_w] = d[a][b] + 1
            q.append((to_h, to_w))
            cnt += 1
    # print(i, j, cnt)
    return cnt


res = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            continue
        res = max(res, bfs(h, w))
# bfs(2, 5)
print(res)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().rstrip().split())
    G = []
    for i in range(H):
        s = list(input())
        G.append(s)
    # print(G)
    cnt = [[0 for j in range(W)] for i in range(H)]

    for i in range(H):
        done = [0] * W
        for j in range(W):
            if G[i][j] == "#":
                continue
            if done[j]:
                continue
            length = 0
            while j + length < W:
                if G[i][j+length] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i][j + k] += length
                done[j + k] = 1

    for j in range(W):
        done = [0] * H
        for i in range(H):
            if G[i][j] == "#":
                continue
            if done[i]:
                continue
            length = 0
            while i + length < H:
                if G[i+length][j] == "#":
                    break
                length += 1
            for k in range(length):
                cnt[i + k][j] += length
                done[i + k] = 1
    ans = 0
    for i in range(H):
        ans = max(ans, max(cnt[i]) - 1)
    print(ans)


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

import math

def is_like_2017(num):
  if all([is_prime(num), is_prime(int((num+1)/2))]): return True
  else: return False
  
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  ans = 0
  for i in range(l,r+1):
    if is_like_2017(i): ans += 1
  print(ans)
    

### FIXED CODE ###

import math
import bisect
  
def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

def get_like_2017(N):
  nums = set([i for i in range(2,N+1)])
  for i in range(2, int(math.sqrt(N))+1):
    for j in range(2,int(N//i)+1):
      if i*j in nums: nums.remove(i*j)
  
  nums_like_2017 = set([])
  for num in nums:
    if is_prime(int((num+1)/2)) is True:  nums_like_2017.add(num)
  return nums_like_2017

nums_like_2017 = sorted(list(get_like_2017(10**5)))

Q = int(input())
for _ in range(Q):
  l,r = map(int, input().split())
  idx_l = bisect.bisect_left(nums_like_2017, l)
  idx_r = bisect.bisect_right(nums_like_2017, r)
 
  print(idx_r-idx_l)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, *lst = map(int, read().split())
al = lst[:n]
bl = lst[n:]


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


a = convert(al)
b = convert(bl)
alal, aa = al + al, a + a


def p_arr(p):
    n = len(p)
    arr = [0] * n
    arr[0] = -1
    k, j = -1, 0
    while j < n - 1:
        if k == -1 or p[j] == p[k]:
            j += 1
            k += 1
            arr[j] = k
        else:
            k = arr[k]
    return arr


def kmp(s, p):
    slen, plen = len(s), len(p)
    i, j = 0, 0
    arr = p_arr(p)
    lst = []
    while i < slen - 1 and j < plen:
        if j == -1 or s[i] == p[j]:
            i += 1
            j += 1
        else:
            j = arr[j]
        if j == plen:
            lst.append(i - j)
            i -= j
            j = -1
    return lst


K = kmp(aa, b)
X = [al[k] ^ bl[0] for k in K]
print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

A = list(map(int, readline().split()))
B = list(map(int, readline().split()))


def convert(A):
    return [x ^ y for x, y in zip(A, A[1:])] + [A[-1] ^ A[0]]


C = convert(A)
D = convert(B)


def Z_algorithm(S):
    # 共通接頭辞の長さを返す
    N = len(S)
    arr = [0] * N
    arr[0] = N
    i, j = 1, 0
    while i < N:
        while i + j < N and S[j] == S[i + j]:
            j += 1
        arr[i] = j
        if not j:
            i += 1
            continue
        k = 1

        while i + k < N and k + arr[k] < j:
            k += 1
        i += k
        j -= k

    return arr


Z = Z_algorithm(D + [-1] + C + C)[N + 1:N + N + 1]

K = [i for i, x in enumerate(Z) if x == N]
X = [A[k] ^ B[0] for k in K]

print('\n'.join('{} {}'.format(k, x) for k, x in zip(K, X)))
### BUGGY CODE ###

import collections
import math
n = int(input())
s = [0]*n
T = [0]*n
ans = 0
for i in range(n):
	s[i] = input()
	T[i] = sorted(list(s[i]))
for i in range(n-1):
	for j in range(i+1,n):
		if T[i] == T[j]:
			ans += 1
print(ans)

### FIXED CODE ###

import collections
import math
n = int(input())
s = [0]*n
T = [0]*n
L = [0]*n
ans = 0
for i in range(n):
	s[i] = input()
	T[i] = sorted(list(s[i]))
	L[i] = ''.join(T[i])
D = collections.Counter(L)
for i in D.values():
	ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

import itertools
def permutations_with_XOR(iterable, r=None):
    pool = tuple(iterable)
    n = len(pool)
    ff = False
    r = n if r is None else r
    for indices in itertools.product(range(n), repeat=r):
        if len(set(indices)) == r:
            p = tuple(pool[i] for i in indices)
            for i in range(0, n):
                if i == 0:
                    ff = checkXOR(p[n-1],p[i],p[i+1])
                elif i == n-1:
                    ff = checkXOR(p[i-1],p[i],p[0])
                else:
                    ff = checkXOR(p[i-1],p[i],p[i+1])
                if ff:
                    break
    return ff

def checkXOR(a, b, c):
    if bin(b) == bin(a ^ c):
        return False
    else:
        return True
    
n = int(input())
a = list(map(int, input().split()))
    
if permutations_with_XOR(a):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

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

for i in range(n):
  aa = aa ^ a[i]

if aa == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
import collections
N,M = [int(x) for x in input().split()]
idls =[]
for i in range(N):
    idls.append(i+1)
ans =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    iidls = idls[L-1:R]
    ans+=iidls
c= collections.Counter(ans)

a = c.most_common()

count = 0
for i in a:
    if i[1] == M:
        count+= 1
       

print(count)







### FIXED CODE ###

#! /usr/bin/env python3
# -*- coding: utf-8 -*-
N,M = [int(x) for x in input().split()]
Llist =[]
Rlist =[]
for i in range (M):
    L,R = [int(x) for x in input().split()]
    Llist.append(L)
    Rlist.append(R)
 
lmax = max(Llist)
Rmax = min(Rlist)

if lmax > Rmax:
    print(0)
else:
    print(Rmax-lmax+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

def solve(sh,sw,gh,gw):
    if s[sh][sw]=="#" or s[gh][gw]=="#":
        return -1

    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if hi+dh==gh and wi+dw==gw:
                    return r+1
                elif not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))

    return -1

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        for ghi in range(h-1,-1,-1):
            for gwi in range(w-1,-1,-1):
                if shi>=ghi and swi>=gwi:
                    break
                r = solve(shi,swi,ghi,gwi)
                res = max(res, r)

print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

maxr = 0
for hi in range(h):
    for wi in range(w):
        if s[hi][wi]==".":
            maxr += 1

def solve(sh,sw):
    res = -1
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))
                    res = max(res, r+1)

    return res

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        r = solve(shi,swi)
        res = max(res, r)

print(res)
### BUGGY CODE ###

N = int(input())
A = input().split()
A.insert(0,0)
x = [0]*N
for i in range(N):
    A[i]=int(A[i])
for j in range(N):
    print(A.count(j+1))



### FIXED CODE ###

N = int(input())
A = input().split()
x = [0]*N
for i in range(N-1):
    x[int(A[i])-1]+=1
for j in range(N):
    print(x[j])
### BUGGY CODE ###

import sys
import numpy as np

lines = sys.stdin.readlines()
N = int(lines[0])

stdin = list(map(int,lines[1].split(' ')))
lst = np.zeros((3,N), dtype=np.int32)

lst[1] += sum(stdin)
for i, a in enumerate(stdin):
    lst[0,i:] += a
    lst[1,i:] -= a
    lst[2,i] = abs(lst[0,i]-lst[1,i])
    i += 1

print(min(lst[2]))

### FIXED CODE ###

import sys
import numpy as np

lines = sys.stdin.readlines()
N = int(lines[0])

stdin = list(map(int,lines[1].split(' ')))

lst = []
S1, S2 = 0, sum(stdin)
for i, a in enumerate(stdin):
    S1 += a
    S2 -= a
    lst.append(abs(S1-S2))

print(min(lst))
### BUGGY CODE ###

class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        i += 1
        s = self.one
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+100))
j = 0
for i in range(n):
    if last[c[i]] != -1:
        bit.update(last[c[i]], -1)
    bit.update(i, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i) - bit.get(que[j][1][0]-1)
        j += 1
que.sort()
for i in que:
    print(i[-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a):
        self.n = len(a)
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.a[i] + x
            i += i & (-i)

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)
### BUGGY CODE ###

s = input()
s = s[::-1]

dp = [0]*13
dp[0] = 1

for ind, i in enumerate(s):
    m = 10**ind%13
    tmp = [0]*13
    for j in range(10):
        if i!='?' and int(i)!=j:
            continue
        for k in range(13):
            tmp[k] += dp[(k-j*m%13)%13]
    dp = tmp
print(dp[5]%(10**9+7))

### FIXED CODE ###

import numpy as np
s = input()

A = []
for i in range(6):
    m = [-(j*10**i%13)%13 for j in range(10)]
    tmp = []
    for j in m:
        tmp.append([[1 if (k-l)%13==j else 0 for k in range(13)] for l in range(13)])
    tmp.append([[1 if (k-l)%13 in m else 0 for k in range(13)] for l in range(13)])
    A.append(tmp)
A = np.array(A)

dp = np.zeros(13, dtype=int)
dp[0] = 1
m = 1
for ind, i in enumerate(reversed(s)):
    i = int(i) if i!='?' else 10
    tmp = np.dot(A[ind%6, i, :, :], dp)
    dp = tmp%(10**9+7)
print(dp[5])
### BUGGY CODE ###

def main():
    N, C = map(int, input().split())
    stc = [list(map(int, input().split())) for _ in range(N)]
    st = []
    mxt = 0
    mnt = 0
    while len(stc) > 0:
        s, t, c = stc.pop()
        for i, (ss, tt, cc) in enumerate(stc):
            if c == cc:
                if s == tt:
                    stc.pop(i)
                    stc.append((ss, t, c))
                    break
                elif ss == t:
                    stc.pop(i)
                    stc.append((s, tt, c))
                    break
        else:
            mnt = min(mnt, s - 1)
            mxt = max(mxt, t)
            st.append((s - 1, t))
    ans = 0
    for i in range(mnt, mxt + 1):
        ans = max(ans, sum(1 for s, t in st if s < i <= t))
    print(ans)


main()


### FIXED CODE ###

def main():
    N, C = map(int, input().split())
    stc = [[0] * (10 ** 5) for _ in range(C)]
    for _ in range(N):
        s, t, c = map(int, input().split())
        stc[c - 1][s - 1:t] = [1] * (t - s + 1)
    print(max(map(sum, zip(*stc))))


main()