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

import math
import numpy as np
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = np.asarray(list(range(num + 1)))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        min_factor_list[i: num+1: i] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)

### FIXED CODE ###

import math
(_,), a  = [list(map(int, s.split())) for s in open(0)]

def fast_factorize(num):
    min_factor_list = list(range(num + 1))
    for i in range(int(math.sqrt(num) + 1), 1, -1):
        for j in range(i, num+1, i):
            min_factor_list[j] = i
    return min_factor_list

min_factor_list = fast_factorize(max(a))

prime_factor_sets = []
for x in a:
    prime_factor_set = set()
    while min_factor_list[x] != 1:
        prime_factor_set.add(min_factor_list[x])
        x //= min_factor_list[x]
    prime_factor_sets.append(prime_factor_set)

g = prime_factor_sets[0].copy()
l = prime_factor_sets[0].copy()
s = 0
for x in prime_factor_sets:
    g &= x
    l |= x
    s += len(x)

if len(g) != 0:
    ans = 'not coprime'
elif len(l) != s:
    ans = 'setwise coprime'
else:
    ans = 'pairwise coprime'
print(ans)
### BUGGY CODE ###

n,m,q=map(int,input().split())
line=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  for j in range(0,l):
    for k in range(r-1,n):
      line[j][k]+=1
for _ in range(q):
  x,y=map(int,input().split())
  print(line[x-1][y-1])

### FIXED CODE ###

n,m,q=map(int,input().split())
line=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  line[l][r]+=1
for i in range(n+1):
  for j in range(n):
    line[i][j+1]+=line[i][j]
for i in range(n+1):
  for j in range(n):
    line[j+1][i]+=line[j][i]
for i in range(q):
  x,y=map(int,input().split())
  print(line[y][y]-line[x-1][y]-line[y][x-1]+line[x-1][x-1])
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))

m = []
for i in range(n):
    m.insert(bisect_left(m, a[i]), a[i])
    b = [a[i]]
    c = 1
    for r in range(i + 1, n):
        b.insert(bisect_left(b, a[r]), a[r])
        c += 1
        temp = b[c // 2]
        m.insert(bisect_left(m, temp), temp)

print(m[((n + 1) * n) // 4])

### FIXED CODE ###

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

if n == 1:
    print(a[0])
    exit()

b = list(sorted(set(a)))

def count_inversion(ans):
    s = [0 for _ in range(2 * n + 2) ]

    def bit_add(i):
        x = i
        while x < 2 * n:
            s[x] += 1
            x += x & -x

    def bit_sum(i):
        x = i
        ret = 0
        while x > 0:
            ret += s[x]
            x -= x & -x
        return ret

    temp = [n for _ in range(n + 1)]
    temp[0] = n + 1
    for i in range(n):
        if a[i] >= b[ans]:
            temp[i + 1] = temp[i] + 1
        else:
            temp[i + 1] = temp[i] - 1
    res = 0
    for i in range(n + 1):
        x = temp[i]
        res += bit_sum(x)
        bit_add(x)
    return res

m = n * (n + 1) // 2

ans = 0

l = 0
r = len(b)
while 1:
    ans = (l + r) // 2
    if count_inversion(ans) * 2 >= m:
        l = ans
    else:
        r = ans
    if r - l <= 1:
        ans = l
        break

print(b[ans])
### BUGGY CODE ###

N,M=map(int, input().split())
H = list(map(int, input().split()))
AB=[list(map(int,list(input().split()))) for i in range(M)]

good = list(range(1,N+1))

for j in range(len(AB)):
  x = AB[j]
  a = x[0]
  b = x[1]
  #print(a,b)
  if H[a-1]>H[b-1] and b in good:
    good.remove(b)
  elif H[a-1]<H[b-1] and a in good:
    good.remove(a)
  elif H[a-1]==H[b-1]:
    if a in good:
      good.remove(a)
    if b in good:
      good.remove(b)
  #print(good)
  
print(len(good))

### FIXED CODE ###

N,M=map(int, input().split())
H = list(map(int, input().split()))
#AB=[list(map(int,list(input().split()))) for i in range(M)]

good = list(range(1,N+1))
good = [1]*N

for j in range(M):
  a,b=map(int, input().split())
  #print(a,b)
  if H[a-1]>H[b-1]:
    #good.remove(b)
    good[b-1] = 0
  elif H[a-1]<H[b-1]:
    #good.remove(a)
    good[a-1] = 0
  elif H[a-1]==H[b-1]:
    good[a-1] = 0
    good[b-1] = 0
  #print(good)
  
print(sum(good))
### BUGGY CODE ###

N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    edges[i] = [a - 1, b - 1]
    deg[a - 1] += 1
    deg[b - 1] += 1
deg_max = max(deg)

def add(arg):  return 1 + arg % deg_max

ans = [0 for _ in range(N - 1)]
usd = [[0 for _ in range(deg_max + 3)] for _ in range(N)]
temp = 0
for i in range(N - 1):
    temp = add(temp)
    a = edges[i][0]
    b = edges[i][1]
    while(usd[a][temp] == 0 and usd[b][temp] == 0):  add(temp)
    ans[i] = temp
    usd[a][temp] = 1
    usd[b][temp] = 1
print(deg_max)
for i in range(N - 1):  print(ans[i])

### FIXED CODE ###

N = int(input())
deg = [0 for _ in range(N)]
edges = [[] for _ in range(N - 1)]
a = []
for i in range(N - 1):
    in1, in2 = map(int, input().split())
    a.append([in1, in2, i])
a = sorted(a, key = lambda x: x[0])
for i in range(N - 1):
    edges[i] = [a[i][0] - 1, a[i][1] - 1, a[i][2]]
    deg[a[i][0] - 1] += 1
    deg[a[i][1] - 1] += 1
deg_max = max(deg)
print(deg_max)

co = [0 for _ in range(N)]
ans = [0 for _ in range(N - 1)]
for i in range(N - 1):
    a = edges[i][0]
    b = edges[i][1]
    temp = 1 + (co[a] % deg_max)
    co[a] = temp
    co[b] = temp
    ans[edges[i][2]] = temp
for i in range(N - 1):  print(ans[i])
### BUGGY CODE ###

from heapq import heapify, heappop, heappush
from collections import defaultdict

X, Y, Z, K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

t = a[0] + b[0] + c[0]
t *= -1
d = defaultdict(list)
d[t] = [(0, 0, 0)]

q = list()
heapify(q)
heappush(q, t)

a_j = (1, 0, 0)
b_j = (0, 1, 0)
c_j = (0, 0, 1)

st = set()
for i in range(K):
    t = heappop(q)
    print(-t)
    for v in d[t]:
        a_i, b_i, c_i = v
        for j in range(3):
            na_i = a_i + a_j[j]
            if na_i >= X: continue
            nb_i = b_i + b_j[j]
            if nb_i >= Y: continue
            nc_i = c_i + c_j[j]
            if nc_i >= Z: continue

            nt = a[na_i] + b[nb_i] + c[nc_i]
            nt *= -1
            nv = (na_i, nb_i, nc_i)

            # print(nt, nv)

            if nv in st: continue
            d[nt].append(nv)
            st.add(nv)
            heappush(q, nt)


### FIXED CODE ###

# https://www.kumilog.net/entry/python-speed-comp#input-%E3%81%A8-sysstdinreadline
# https://teratail.com/questions/88396

from heapq import heapify, heappush, heappop
import sys

input = sys.stdin.readline


class Data:
    def __init__(self, value, indices):
        self.value = value
        self.indices = indices

    def __lt__(self, other):
        return self.value < other.value


X, Y, Z, K = map(int, input().split())
a = map(int, input().split())
b = map(int, input().split())
c = map(int, input().split())

a = list(sorted(a, reverse=True))
b = list(sorted(b, reverse=True))
c = list(sorted(c, reverse=True))

hq = []
heapify(hq)

t = a[0] + b[0] + c[0]
t *= -1

d = Data(t, (0, 0, 0))

heappush(hq, d)

dtpls = ((1, 0, 0), (0, 1, 0), (0, 0, 1))

st = set()

cnt = 0
for _ in range(K):
    d = heappop(hq)
    print(-d.value)
    for dtpl in dtpls:
        na = d.indices[0] + dtpl[0]
        if na >= X: continue
        nb = d.indices[1] + dtpl[1]
        if nb >= Y: continue
        nc = d.indices[2] + dtpl[2]
        if nc >= Z: continue

        nt = a[na] + b[nb] + c[nc]
        nt *= - 1

        ntpl = (na, nb, nc)
        if ntpl in st: continue
        heappush(hq, Data(nt, ntpl))
        st.add(ntpl)
### BUGGY CODE ###

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())

n = 1
m = [A[0]]
for i in range(1, N):
  for j in range(n):
    if m[j] < A[i]:
      m[j] = A[i]
      break
  else:
    n += 1
    m.append(A[i])
print(n)


### FIXED CODE ###

import bisect

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())

B = [A[N - 1]]
for i in reversed(range(0, N - 1)):
  if A[i] >= B[-1]:
    B.append(A[i])
  else:
    index = bisect.bisect_right(B, A[i])
    B[index] = A[i]
print(len(B))
### BUGGY CODE ###

R,G,B,N=map(int, input().split())

count=0
for r in range(N+1):
    for g in range(N+1):
        for b in range(N+1):
            if (r*R+g*G+b*B)==N:
                count+=1
print(count)

### FIXED CODE ###

R,G,B,N=map(int, input().split())

count=0
for p1 in range(0,N+1,R):
    for p2 in range(0,N-p1+1,G):
        rR = p1
        gG = p2
        bB = N-p1-p2
        if bB%B==0:
            count+=1
print(count)
### BUGGY CODE ###

def num2bi(x, k):
  return format(x, '0'+str(k)+'b')

def bi2num(b):
  n=len(b)
  i=1
  out=0
  while i<n+1:
    out+=int(b[-i])*pow(2, i-1)
    i+=1
  return out

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
dp[0][0]=0
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      jstr=list(num2bi(j, N))
      for k in range(b):
        if jstr[c[k]-1]=='0':
          jstr[c[k]-1]='1'
          
      tmp=bi2num(''.join(jstr))
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])

### FIXED CODE ###

#import sys
#def input():
#  return sys.stdin.readline()[:-1]

N, M=map(int, input().split())
NN=2**N

dp=[[0]+[-1]*(NN-1) for i in range(M+1)]
for i in range(1, M+1):
  a, b=map(int, input().split())
  c=list(map(int, input().split()))
  csum=sum([2**(c[s]-1) for s in range(b)])
  
  for j in range(NN):
    if dp[i-1][j]>-1:
      if dp[i][j]==-1 or dp[i][j]>dp[i-1][j]:
        dp[i][j]=dp[i-1][j]
      
      tmp=csum|j
      if dp[i][tmp]==-1 or dp[i][tmp]>dp[i][j]+a:
        dp[i][tmp]=dp[i][j]+a
        
print(dp[-1][-1])
### BUGGY CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""
q=int(input())
lr_ary = []
for _ in range(q):
  lr_ary.append(list(map(int, input().split())))

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False

for l,r in lr_ary:
    ret=0
    for x in range(l,r+1,2):
        if prime[x] and prime[int((x+1)/2)]:
            ret += 1
    print(ret)

### FIXED CODE ###

from pprint import pprint as pp
from functools import lru_cache
import math
"""
問題文
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1≦i≦Q) では奇数 li,ri が与えられるので、li≦x≦ri かつ 2017に似た数 となる奇数 x の個数を求めてください。
制約
    1≦Q≦105
    1≦li≦ri≦105
    li,ri は奇数
    入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
Q
l1 r1
:
lQ rQ
出力
i 行目 (1≦i≦Q) に、クエリ i の答えが x 個のとき、x を出力せよ。
"""

prime = [True] * 100000
prime[0] = False
prime[1] = False
for i in range(2,len(prime)):
    if prime[i]:
        for j in range(i*2, len(prime), i):
            prime[j] = False
prime2017 = [0] * 100000
prime2017[0] = 0
prime2017[1] = 0
prime2017[2] = 0
ruiseki=0
for x in range(3,len(prime)):
    if prime[x] and prime[int((x+1)/2)]:
        ruiseki+=1
    prime2017[x] = ruiseki
q=int(input())
lr_ary = []
for _ in range(q):
    l,r=list(map(int, input().split()))
    print(prime2017[r]-prime2017[l-1])
### BUGGY CODE ###

from sys import stdin,setrecursionlimit
setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for _ in range(2 * (10 ** 5))]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for _ in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v = -1):
    global d
    for p in T[u]:
        if p == v:
            continue
        d[p] += d[u]
        dfs(p, u)

dfs(0)

for v in d:
    print(v)


### FIXED CODE ###

from sys import stdin,setrecursionlimit
input = stdin.readline
setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for _ in range(2 * (10 ** 5))]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

for _ in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v):
    global d
    for p in T[u]:
        if p == v:
            continue
        d[p] += d[u]
        dfs(p, u)

dfs(0, -1)

for v in d:
    print(v)
### BUGGY CODE ###

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [[v, T[K][v], K] for v in T[K].keys()]
for _ in range(N-1):
    v, c, p = iter(queue.pop(0))
    shortest_path[v] = c
    queue += [[u, T[v][u] + c, v] for u in T[v].keys() if u != p]

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])
### BUGGY CODE ###

import re
s=input()
N=len(s)
while True:
    n = len(s)
    s = s.replace("10", "")
    s = s.replace("01", "")
    if n == len(s):
        print(N-n)
        break

### FIXED CODE ###

s=input()

stack=[]
for si in s:
    stack.append(si)
    if len(stack) >= 2 and stack[-1] != stack[-2]:
        del stack[-1]
        del stack[-1]
print(len(s)-len(stack))
### BUGGY CODE ###

def search_root(l, n):
    i = n
    while l[i] != 0:
        i = l[i]
    return i

def func(n):
    return (n * (n - 1)) // 2


node_size, input_size = [int(i) for i in input().split()]

br = []
for _ in range(input_size):
    br.append([int(i) for i in input().split()])

cnt_list = [func(node_size)]
size_list = [0 for _ in range(node_size + 1)]
node_list = [i for i in range(node_size + 1)]

for i in range(1, input_size + 1):
    node1, node2 = br[-i]

    if node_list[node1] == node1 and node_list[node2] == node2:
        node_list[node1] = 0
        node_list[node2] = node1
        new_size = cnt_list[0] - 1
        size_list[node1] = 2
    elif node_list[node1] == node1:
        tmp_root = search_root(node_list, node2)
        if node_list[node2]:
            node_list[node2] = tmp_root
        node_list[node1] = tmp_root
        new_size = cnt_list[0] - size_list[tmp_root]
        size_list[tmp_root] += 1
    elif node_list[node2] == node2:
        tmp_root = search_root(node_list, node1)
        if node_list[node1]:
            node_list[node1] = tmp_root
        node_list[node2] = tmp_root
        new_size = cnt_list[0] - size_list[tmp_root]
        size_list[tmp_root] += 1
    else:
        tmp_root1 = search_root(node_list, node1)
        tmp_root2 = search_root(node_list, node2)
        if tmp_root1 == tmp_root2:
            tmp = cnt_list[0]
        else:
            if node_list[node1]:
                node_list[node1] = tmp_root1
            node_list[node2] = tmp_root1
            node_list[tmp_root2] = tmp_root1
            new_size = cnt_list[0] - (size_list[tmp_root1] * size_list[tmp_root2])
            size_list[tmp_root1] += size_list[tmp_root2]

    if new_size is 0:
        for _ in range(input_size - i):
            print(0)
        break
    cnt_list.insert(0, new_size)

for i in cnt_list:
    print(i)

### FIXED CODE ###

def search_root(l, n):
    i = n
    while l[i] != i:
        i = l[i]
    return i


def set_root(l, root_index, start_index):
    i = start_index
    while l[i] != root_index:
        tmp = i
        i = l[i]
        l[tmp] = root_index


def func(n):
    return (n * (n - 1)) // 2


node_size, input_size = [int(i) for i in input().split()]

br = []
for _ in range(input_size):
    br.append([int(i) for i in input().split()])

cnt_list = [0]
size_list = [1 for _ in range(node_size + 1)]
node_list = [i for i in range(node_size + 1)]

for i in range(1, input_size + 1):
    node1, node2 = br[-i]

    root1, root2 = search_root(node_list, node1), search_root(node_list, node2)

    if root1 == root2:
        cnt_list.append(cnt_list[-1])
    else:
        cnt_list.append(cnt_list[-1] + (size_list[root1] * size_list[root2]))
        if size_list[root1] < size_list[root2]:
            node_list[root1] = root2
            size_list[root2] += size_list[root1]
        else:
            node_list[root2] = root1
            size_list[root1] += size_list[root2]

val = func(node_size)
for i in cnt_list[::-1][1:]:
    print(val - i)
### BUGGY CODE ###

from collections import Counter

def solver():
    H, W, M = map(int, input().split())

    retu = Counter()
    gyo = Counter()

    ipt = [[] for _ in range(H)]

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

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())


### FIXED CODE ###

from collections import Counter

def solver():
    H, W, M = map(int, input().split())

    retu = Counter()
    gyo = Counter()

    ipt = [set() for _ in range(H)]

    for _ in range(M):
        a, b = map(int, input().split())
        retu[a-1] += 1
        gyo[b-1] += 1
        ipt[a-1].add(b-1)

    rm = retu.most_common()
    rmm = rm[0][1]
    gm = gyo.most_common()
    gmm = gm[0][1]

    for r in rm:
        if r[1] < rmm:
            break
        for g in gm:
            if g[1] < gmm:
                break

            if g[0] not in ipt[r[0]]:
                return rmm+gmm
    
    return rmm+gmm-1

print(solver())
### BUGGY CODE ###

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

if N == 0 or K == 1:
    N = 0
elif N == K:
    N = 0
elif N % K == 0:
    N = 0
else:
    while N != 0:
        m = abs(N - K)
        if N < m:
            break
        else:
            N = m

print(N)

### FIXED CODE ###

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

if N == 0 or K == 1:
    N = 0
elif N == K:
    N = 0
elif N % K == 0:
    N = 0
else:
    N = N % K
    while N != 0:
        m = abs(N - K)
        if N < m:
            break
        else:
            N = m

print(N)
### BUGGY CODE ###

n,C=map(int,input().split())
N=10**5+1
INF = 2**31-1
 
LV = N.bit_length()
N0 = 2**LV
data = [0]*(2*N0)
lazy = [0]*(2*N0)
 
def gindex(l, r):
    L = l + N0; R = r + N0
    lm = (L // (L & -L)) >> 1
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1; R >>= 1
    while L:
        yield L
        L >>= 1
 
def propagates(*ids):
    for i in reversed(ids):
        v = lazy[i-1]
        if not v:
            continue
        lazy[2*i-1] += v; lazy[2*i] += v
        data[2*i-1] += v; data[2*i] += v
        lazy[i-1] = 0
 
def update(l, r, x):
    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[R-1] += x; data[R-1] += x
        if L & 1:
            lazy[L-1] += x; data[L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in gindex(l, r):
        data[i-1] = min(data[2*i-1], data[2*i]) + lazy[i-1]
 
def query(l, r):
    propagates(*gindex(l, r))
    L = N0 + l; R = N0 + r
 
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

a=[[0 for i in range(N)]for i in range(C)]

for i in range(n):
    s,t,c=map(int,input().split())
    recs,rect=a[c-1][s],a[c-1][t]
    if recs==0 and rect==0:
        update(s-1,t,-1)
    elif recs==0 and rect==1:
        update(s-1,t-1,-1)
    elif recs==1 and rect==0:
        update(s,t,-1)
    elif recs==1 and rect==1 and s<t-1:
        update(s,t-1,-1)
    a[c-1][s],a[c-1][t]=1,1
print(-query(0,N+1))

### FIXED CODE ###

import sys
import math
from itertools import accumulate as acc

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


a=[[0 for i in range(10**5+1)] for i in range(C+1)]

rec=[0 for i in range(10**5+1)]

for i in range(N):
    s,t,c=map(int,input().split())
    recs,rect=a[c][s],a[c][t]
    if recs==0 and rect==0:
        rec[s-1]+=1
        rec[t]-=1
    elif recs==0 and rect==1:
        rec[s-1]+=1
        rec[t-1]-=1
    elif recs==1 and rect==0:
        rec[s]+=1
        rec[t]-=1
    elif recs==1 and rect==1:
        rec[s]+=1
        rec[t-1]-=1

    a[c][s],a[c][t]=1,1

tmp=0
ans=0
for i in range(10**5):
    tmp+=rec[i]
    ans=max(tmp,ans)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left

CHARACTERs = 'abcdefghijklmnopqrstuvwxyz'

As = input()
lenA = len(As)

posChars = dict([(ch, []) for ch in CHARACTERs])
for i, A in enumerate(As):
    posChars[A].append(i)
for ch in CHARACTERs:
    posChars[ch].append(lenA)

dp = [0] * lenA + [1, 0]
for i in reversed(range(lenA)):
    dp[i] = min([dp[posChars[ch][bisect_left(posChars[ch], i)] + 1] for ch in CHARACTERs]) + 1

ans = []
i = 0
for k in reversed(range(dp[0])):
    for ch in CHARACTERs:
        pos = posChars[ch][bisect_left(posChars[ch], i)]
        if dp[pos + 1] == k:
            ans.append(ch)
            i = pos + 1
            break

print(''.join(ans))


### FIXED CODE ###

from collections import deque
from sys import exit

As = input()

As = [ord(A) - ord('a') for A in As]
lenA = len(As)
posChars = [lenA] * 26
posNexts = [[] for _ in range(lenA + 1)]
for i in reversed(range(lenA)):
    posNexts[i + 1] = posChars.copy()
    posChars[As[i]] = i
posNexts[0] = posChars.copy()

prevs = [None] * lenA
Q = deque()
Q.append((0, -1))
while Q:
    lenAns, pos = Q.popleft()
    for ch in range(26):
        posNext = posNexts[pos + 1][ch]
        if posNext == lenA:
            ans = [chr(ord('a') + ch)]
            while pos != -1:
                ans.append(chr(ord('a') + As[pos]))
                pos = prevs[pos]
            print(''.join(reversed(ans)))
            exit()
        if prevs[posNext] is None:
            prevs[posNext] = pos
            Q.append((lenAns + 1, posNext))