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

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
while d:
    py, px = d.popleft()
    #bfs
    if py-1 >= 0 and s[py-1][px] == "." and meiro[py-1][px] > meiro[py][px]:
        d.append([py-1, px])
        meiro[py-1][px] = meiro[py][px]

    if py+1 < h and s[py+1][px] == "." and meiro[py+1][px]>meiro[py][px]:
        d.append([py+1, px])
        meiro[py+1][px] = meiro[py][px]

    if px+1 < w and s[py][px+1] == "." and meiro[py][px+1]>meiro[py][px]:
        d.append([py, px+1])
        meiro[py][px+1] = meiro[py][px]

    if px-1 >= 0 and s[py][px-1] == "." and meiro[py][px-1]>meiro[py][px]:
        d.append([py, px-1])
        meiro[py][px-1] = meiro[py][px]

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])

ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*M
C=[0]*M
D=[]
for i in range(M):
    B[i],C[i]=map(int,input().split())
    D+=[C[i]]*B[i]
D.sort()
D.reverse()
A.sort()

for i in range(len(D)):
    if A[i] < D[i]:
        A[i]=D[i]
    else:
        break
    if i==N-1:
        break
print(sum(A))      




### FIXED CODE ###

#!/usr/bin/env python3
import bisect
import numpy as np

N, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))
bc_list = []

for i in range(M):
    b, c = list(map(int, input().split()))
    bc_list.append((b, c))

bc_list = sorted(bc_list, key=lambda x: x[1], reverse=True)
a_list = sorted(a_list)

fix_list = []
s = 0
b, c = bc_list[0]
bc_index = 0
count_b = 0

for a in a_list:
    if count_b >= b:
        bc_index += 1
        if bc_index >= len(bc_list):
            s += a
            continue
        count_b = 0
        b, c = bc_list[bc_index]

    if a < c:
        s += c
    else:
        s += a
    count_b += 1

ans = s
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

    pow2 = [0] * (N + 1)
    pow2[0] = 1
    for i in range(N):
        pow2[i + 1] = pow2[i] * 2

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


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


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

MOD = 10**9+7

def main():
    s = input()
    dp = [[0 for _ in range(4)] for _ in range(len(s)+1)]
    dp[0][0] = 1
    for i, c in enumerate(s):
        for j in range(4):
            dp[i+1][j] = dp[i][j] % MOD
        if c == 'A' or c == '?':
            dp[i+1][1] += dp[i][0]
        if c == 'B' or c == '?':
            dp[i+1][2] += dp[i][1]
        if c == 'C' or c == '?':
            dp[i+1][3] += dp[i][2]
        if c == '?':
            for j in range(4):
                dp[i+1][j] += 2*dp[i][j]

    print(dp[len(s)][3]%MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

MOD = 10**9+7

def main():
    s = input()
    dp = [[0 for _ in range(4)] for _ in range(len(s)+1)]
    dp[0][0] = 1
    for i, c in enumerate(s):
        if c == '?':
            for j in range(4):
                dp[i+1][j] = 3*dp[i][j]
        else:
            for j in range(4):
                dp[i+1][j] = dp[i][j]
        if c == 'A' or c == '?':
            dp[i+1][1] += dp[i][0]
        if c == 'B' or c == '?':
            dp[i+1][2] += dp[i][1]
        if c == 'C' or c == '?':
            dp[i+1][3] += dp[i][2]
        if i & 1:
            for j in range(4):
                dp[i+1][j] %= MOD

    print(dp[len(s)][3]%MOD)


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

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    X = readInts()

    import statistics

    for i in range(n):
        A = (X[:i] + X[i+1:] if i+1 < n else X[:i])
        print(statistics.median(A))




if __name__ == '__main__':
  main()


### FIXED CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    X = readInts()

    A = sorted(X)[n//2-1:n//2+1] # 中央値のどちらか
    #print(A)
    for x in X:
        #print(x <= A[0]) # False 0 True 1
        print(A[x <= A[0]]) # 1




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

N, C = map(int, input().split())
D = [0] * C
for i in range(C):
    D[i] = list(map(int, input().split()))
grid = [0] * N
for i in range(N):
    grid[i] = list(map(int, input().split()))

ans_min = float('inf')
for i in range(C):
    j_list = list(range(C))
    j_list.remove(i)
    for j in j_list:
        k_list = list(range(C))
        k_list.remove(i)
        k_list.remove(j)
        for k in k_list:
            ans = 0
            for h in range(N):
                for w in range(N):
                    new_color = [i,j,k][(h+w) % 3]
                    ans += D[grid[h][w] - 1][new_color]
            if ans < ans_min:
                ans_min = ans
print(ans_min)

### FIXED CODE ###

N, C = map(int, input().split())
D = [0] * C
for i in range(C):
    D[i] = list(map(int, input().split()))
grid = [0] * N
for i in range(N):
    grid[i] = list(map(int, input().split()))

cost0 = [0] * C
cost1 = [0] * C
cost2 = [0] * C
for color in range(C):
    for h in range(N):
        for w in range(N):
            mod = (h + w) % 3
            if mod == 0:
                cost0[color] += D[grid[h][w] - 1][color]
            elif mod == 1:
                cost1[color] += D[grid[h][w] - 1][color]
            else:
                cost2[color] += D[grid[h][w] - 1][color]

ans = float('inf')
for i in range(C):
    j_list = list(range(C))
    j_list.remove(i)
    for j in j_list:
        k_list = list(range(C))
        k_list.remove(i)
        k_list.remove(j)
        for k in k_list:
            ans = min(ans, cost0[i] + cost1[j] + cost2[k])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

s = str(input())
obj_x, obj_y = list(map(int, input().split()))


x = []
y = []
flag = 0
num = 0
for i in range(len(s)):
    if s[i] == "T":
        if flag % 2 == 0:
            x.append(num)
        else:
            y.append(num)
        flag += 1
        num = 0
    else:
        num += 1

if num > 0:
    if flag % 2 == 0:
        x.append(num)
    else:
        y.append(num)


if x == []:
    x = [0]
if y == []:
    y = [0]

# print(x)
# print(y)
max_ = 8000*2+1
dp_x = [[0]*((len(x)+1)) for i in range(8000*2+1)]
dp_y = [[0]*((len(y)+1)) for i in range(8000*2+1)]

dp_x[8000][0] = 1
dp_y[8000][0] = 1

for i in range(0, len(x)):
    num = x[i]
    for j in range(0, len(dp_x)):

        if j+num < max_:
            dp_x[j+num][i+1] = max(dp_x[j+num][i+1], dp_x[j][i]*1)
        if j-num > 0:
            dp_x[j-num][i+1] = max(dp_x[j-num][i+1], dp_x[j][i]*1)
        # if dp_x[j][i] == 1:
            # print(j+num, j-num)
for i in range(0, len(y)):
    num = y[i]
    for j in range(0, len(dp_y)):

        if j+num < max_:
            dp_y[j+num][i+1] = max(dp_y[j+num][i+1], dp_y[j][i]*1)
        if j-num > 0:
            dp_y[j-num][i+1] = max(dp_y[j-num][i+1], dp_y[j][i]*1)
        # if dp_y[j][i] == 1:
            # print(j+num, j-num)


ans_x = dp_x[8000+obj_x][-1]
ans_y = dp_y[8000+obj_y][-1]

if ans_x*ans_y == 1:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)

s = str(input())
obj_x, obj_y = list(map(int, input().split()))


x = []
y = []
flag = 0
num = 0
for i in range(len(s)):
    if s[i] == "T":
        if flag % 2 == 0:
            x.append(num)
        else:
            y.append(num)
        flag += 1
        num = 0
    else:
        num += 1

if num > 0:
    if flag % 2 == 0:
        x.append(num)
    else:
        y.append(num)


if x == []:
    x = [0]
if y == []:
    y = [0]


num_x = sum(x)
num_y = sum(y)

max_x = num_x*2+1
max_y = num_y*2+1

dp_x = [[0]*((len(x)+1)) for i in range(max_x)]
dp_y = [[0]*((len(y)+1)) for i in range(max_y)]

dp_x[num_x][0] = 1
dp_y[num_y][0] = 1

# print(x)
dp_x[num_x+x[0]][1]=1

# print(dp_x)

for i in range(1, len(x)):
    num = x[i]
    for j in range(0, len(dp_x)):
        if j+num < max_x:
            dp_x[j+num][i+1] = max(dp_x[j+num][i+1], dp_x[j][i]*1)
        if j-num >= 0:
            dp_x[j-num][i+1] = max(dp_x[j-num][i+1], dp_x[j][i]*1)
        # if dp_x[j][i] == 1:
        #     print(j+num, j-num)
for i in range(0, len(y)):
    num = y[i]
    for j in range(0, len(dp_y)):
        if j+num < max_y:
            dp_y[j+num][i+1] = max(dp_y[j+num][i+1], dp_y[j][i]*1)
        if j-num >= 0:
            dp_y[j-num][i+1] = max(dp_y[j-num][i+1], dp_y[j][i]*1)
        # if dp_y[j][i] == 1:
        #     print(j+num, j-num)


if (num_x+obj_x)<len(dp_x) and (num_x+obj_x)>=0:
    ans_x = dp_x[num_x+obj_x][-1]
else:
    print("No")
    exit()
if (num_y+obj_y)<len(dp_y) and (num_y+obj_y)>=0:
    ans_y = dp_y[num_y+obj_y][-1]
else:
    print("No")
    exit()

# print(dp_x)
if ans_x*ans_y == 1:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
table = []
for i in range(n):
    s = input()
    if s not in table:
        table.append(s)
print(len(table))

### FIXED CODE ###

table = []
n = int(input())
for i in range (n):
    s = input()
    table.append(s)
print(len(list(set(table))))
### BUGGY CODE ###

N=int(input())
K=[]
z=0
for x in range(N):
    k=input()
    K.append(k)
for y in range(N):
    m=max(K)
    K.remove(m)
    if m in K:
        pass
    else:
        z+=1
print(z)
        
        
    
    


### FIXED CODE ###

N=int(input())
K=[]
z=0
for x in range(N):
    k=input()
    K.append(k)
T=set(K)
y=len(T)
print(y)
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    n, k = map(int, input().split())
    x_list = list(map(int, input().split()))

    ans = float('inf')
    for i in range(n - k + 1):
        arry = x_list[i:i+k]
        if arry[0] >= 0 and arry[-1] >= 0:
            ans = min(ans, arry[-1])
        elif arry[0] < 0 and arry[-1] < 0:
            ans = min(ans, -arry[0])
        else:
            ans = min(ans, -arry[0] * 2 + arry[-1])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

def main():
    n, k = map(int, input().split())
    x_list = list(map(int, input().split()))
    ans = float('inf')

    for i in range(n - k + 1):
        if x_list[i] >= 0 and x_list[i+k-1] >= 0:
            ans = min(ans, x_list[i+k-1])
        elif x_list[i] <= 0 and x_list[i+k-1] <= 0:
            ans = min(ans, -x_list[i])
        else:
            ans = min(ans, min(-x_list[i] * 2 + x_list[i+k-1] , -x_list[i] + x_list[i+k-1] * 2))
    print(ans)

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

n = int(input())
a = list(map(int, input().split()))
 
num_cnt = [0]*n
sum_cnt = 0
 
for num in range(n):
    cnt = a.count(num+1)
    if cnt > 0:
        num_cnt[num] = cnt
        sum_cnt += cnt*(cnt-1)//2

res = []
for x in a:
    cnt = num_cnt[x-1]
    res.append(str( sum_cnt - (cnt-1) ))

print('\n'.join(res))

### FIXED CODE ###

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

import collections
cnt = collections.Counter(a)

sum_cnt = 0
for v in cnt.values():
    sum_cnt += v*(v-1)//2

res = []
for value in a:
    res.append(str( sum_cnt - (cnt[value]-1) ))
print('\n'.join(res))
### BUGGY CODE ###

N=int(input())
S=input()
R=[]
G=[]
B=[]
ans=0
x=0
a=0
b=0
c=0
for i in S:
    if i=="R":
        R.append(x)
    if i=="G":
        G.append(x)
    if i=="B":
        B.append(x)
    x+=1
for j in R:
    for k in G:
        if 2*k-j in B:
            B.pop(B.index(2*k-j))
            a+=1
        if 2*j-k in B:
            B.pop(B.index(2*j-k))   
            b+=1
        if (j+k)/2 in B:
            B.pop(B.index((j+k)/2))
            c+=1
        ans+=len(B)
        if a!=0:
            B.append(2*k-j)
            a=0
        if b!=0:
            B.append(2*j-k)
            b=0
        if c!=0:
            B.append((j+k)/2)
            c=0
print(ans)

### FIXED CODE ###

N=int(input())
S=list(input())
S.insert(0,0)
R=S.count("R")
G=S.count("G")
B=S.count("B")
ans=R*G*B
for i in range(1,N-1):
    for j in range(i+1,N):
        k=2*j-i
        if k<N+1 and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

#あっとのTECH LOG、ここからDFS
N, M, K = map(int, input().split())
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)


D = {}
parent = [-1] * N
visited = [False] * N
for root in range(N):
    if visited[root]:
        continue

    D[root] = set([root])
    stack = [root]
    while stack:
        n = stack.pop()
        visited[n] = True
        parent[n] = root

        for to in F[n]:
            if visited[to]:
                continue
            D[root].add(to)
            stack.append(to)

ans = [0] * N
for iam in range(N):
    group = D[parent[iam]]
    tmp_ans = len(group) - len(F[iam]) - 1
    for block in B[iam]:
        if block in group:
            tmp_ans -= 1
    ans[iam] = tmp_ans

print(*ans, sep=' ')

### FIXED CODE ###

class UnionFind():
 def __init__(self,n):
   self.n=n
   self.root=[-1]*(n+1)
   self.rank=[0]*(n+1)
 def FindRoot(self,x):
   if self.root[x]<0:
     return x
   else:
     self.root[x]=self.FindRoot(self.root[x])
     return self.root[x]
 def Unite(self,x,y):
   x=self.FindRoot(x)
   y=self.FindRoot(y)
   if x==y:
     return
   else:
     if self.rank[x]>self.rank[y]:
       self.root[x]+=self.root[y]
       self.root[y]=x
     elif self.rank[x]<=self.rank[y]:
       self.root[y]+=self.root[x]
       self.root[x]=y
       if self.rank[x]==self.rank[y]:
         self.rank[y]+=1
 def isSameGroup(self,x,y):
   return self.FindRoot(x)==self.FindRoot(y)
 def Count(self,x):
   return -self.root[self.FindRoot(x)]
 
n,m,k=map(int,input().split())
t=UnionFind(n+1)
cnt=[0]*(n+1) #各iについて、iと同一の連結成分に属する友達関係の人、ブロック関係の人の数を数える
for _ in range(m):
 a,b=map(int,input().split())
 cnt[a]+=1 #各iについて、iと同一の連結成分に属する友達関係の人の数を数える
 cnt[b]+=1
 t.Unite(a,b)
for _ in range(k):
 a,b=map(int,input().split())
 if t.isSameGroup(a,b)==True:
   cnt[a]+=1 #各iについて、iと同一の連結成分に属するブロック関係の人の数を数える
   cnt[b]+=1
ans=[0]*(n+1)
for i in range(1,n+1):
 ans[i]=(t.Count(i)-1)-cnt[i] #答えは(各iが属する連結成分のサイズ)-1-((iと同一の連結成分に含まれているiと友達関係にある人の数)+(iと同一の連結成分に含まれているiとブロック関係にある人の数)となる
print(*ans[1:])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for i in range(N):
    ans = ans * A[i]
    
if ans > 10**18:
    ans = -1
    
print(ans)
    
    
    

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1


if 0 in A:
    ans = 0
else:
    for i in range(N):
        ans = ans * A[i]
        if ans > 10**18:
            ans = -1
            break

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

s=list(input())
t=list(input())
dp=[[0 for i in range(len(t)+1)] for j in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        dp[i][j+1]=max(dp[i][j],dp[i][j+1])
        dp[i+1][j]=max(dp[i][j],dp[i+1][j])
ans=[]
i=len(s)
j=len(t)
while(i>0 and j>0):
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1
print("".join(ans[::-1]))

### FIXED CODE ###

s=list(input())
t=list(input())
n = len(s)
m = len(t)
dp=[[0 for i in range(m+1)] for j in range(n+1)]
for i in range(n+1):
    for j in range(m+1):
        if i<n and j<m and s[i]==t[j]:
            dp[i+1][j+1]=max(dp[i][j]+1,dp[i+1][j+1])
        if j<m:
            dp[i][j+1]=max(dp[i][j],dp[i][j+1])
        if i<n:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
ans=[]
while(n>0 and m>0):
    if dp[n][m]==dp[n-1][m]:
        n-=1
        continue
    if dp[n][m]==dp[n][m-1]:
        m-=1
        continue
    ans.append(s[n-1])
    n-=1
    m-=1
print("".join(ans[::-1]))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K=map(int,input().split())
l=list(map(int,input().split()))

if max(l)<K:
    print("IMPOSSIBLE")
    exit()

temp=[]
prev_l=[-1]
while prev_l!=l: #temp <=> l <=> prev_l
    temp.clear()
    prev_l.clear()
    prev_l=prev_l+l
    for i in range(len(l)-1):
        for j in range(i+1,len(l)):
            temp.append(abs(l[i]-l[j]))
    l=l+temp
    if K in l:
        print("POSSIBLE")
        exit()
    l=list((set(l)))
    #print(l)
    
print("IMPOSSIBLE")

### FIXED CODE ###

# coding: utf-8
# Your code here!
from fractions import gcd
from functools import reduce

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

if max(l)<K:
    print("IMPOSSIBLE")
else:
    if K%reduce(gcd, l)==0:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")
### BUGGY CODE ###


K = int(input())
n = 0
LunList = [0]
cnt = 0
tmp = 0
while cnt < K:
    n = n + 1
    LunList.append(0)
    nDigit = []
    nDiv   = []
    flg = True
    digits = len(str(n))
    tmpN = n
    for i in range(0,digits) :
        nDigit.append(tmpN // (10 ** (digits-i-1)))
        nDiv.append(tmpN)
        tmpN = tmpN % (10 ** (digits-i-1))
    if len(nDigit) == 1 :
        cnt = cnt + 1
        LunList[n] = LunList[tmp] + 1
        tmp = n
    else :
        for i in range(0,len(nDigit)-1) :
            if abs(nDigit[i] - nDigit[i+1]) > 1 :
                flg = False
        if flg == True :
            cnt = cnt + 1
            LunList[n] = LunList[tmp] + 1
            tmp = n
print(n)


### FIXED CODE ###

k = int(input())

i = 1
q = []
while i <= k :
    if(i < 10) :
        q.append(i)
    else :
        x = q.pop(0)
        tmp = 10 * x + (x % 10)
        if x % 10 != 0 :
            q.append(tmp-1)
            i+=1
        q.append(tmp)
        if x % 10 != 9 :
            q.append(tmp+1)
            i+=1
    i+=1
print(q.pop(k-i))
### BUGGY CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    if c in channells.keys():
        channells[c] += [s,g]
    else:
        channells[c] = [s,g]

count = [0 for i in range(max_end)]
tv_times = []
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    for i in range(len(remove_list)):
        time.remove(remove_list[i])
        time.remove(remove_list[i])

    for i in range(len(time)//2):
        # print(time,remove_list)
        for j in range(max(time[2*i]-1,0),time[2*i+1]):
            count[j] += 1

print(max(count))


### FIXED CODE ###

N,C = map(int,input().split())
tv_times = [[int(j) for j in input().split()] for i in range(N)]

channells = {}
for i in range(C+1):
    channells[i] = []
max_end = -1

for i in range(N):
    s,g,c = tv_times[i]
    max_end = max(max_end,g)
    channells[c] += [s,g]

tv_times = []
f = [0 for i in range(max_end+1)]
for cha in channells.keys():
    remove_list = []
    time = channells[cha]
    time.sort()
    for i in range(1,len(time)-1):
        if time[i] == time[i+1]:
            remove_list.append(time[i])
    time = list(set(time)-set(remove_list))
    time.sort()
    for i in range(len(time)//2):
        f[max(time[2*i]-1,0)] += 1
        f[time[2*i+1]] -= 1
ans = -1
for i in range(1,max_end+1):
    f[i] += f[i-1]
    if ans < f[i]:
        ans = f[i]

print(ans)