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

import numpy as np
# 二部探索で決めていく。dpですでに見られたかどうかは把握
from bisect import bisect_left
n,q  = map(int, input().split())
events = []
"""
工事 start   0 eve追加
di start     2
工事 finish  1 eve削除
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
for i in range(n):
    s,t,x = map(int, input().split())
    events.append((s-x,1,x))
    events.append((t-x,-1,x))
    
for i in range(q):
    d = int(input())
    events.append((d,2,i))
ans = [-1] * q
events.sort()
works = set()
for t, e, x in events:
    if e == 1:
        works.add(x)
    elif e == -1:
        works.remove(x)
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            ans[x] = min(works)
print(*ans)

    

### FIXED CODE ###


# 二部探索で決めていく。dpですでに見られたかどうかは把握
"""
工事 finish  1 eve削除
工事 start   2 eve追加
di start     3
この時間を混ぜてソート。上から順番に捌く
（区間がxi,xjで重なっていたらsetに入れられないのか。）

同じ時刻だった場合
工事finish -> 工事start -> di通過
の順番
"""
import sys
from operator import itemgetter
input = sys.stdin.readline
n,q  = map(int, input().split())
events = []
E = 10**10
for i in range(n):
    s,t,x = map(int, input().split())
    # st
    events.append((s-x,1,x))
    # gl
    events.append((t-x,0,x))
ds = [(int(input()),2,i) for i in range(q)]
events.extend(ds)
ans = [-1] * q
events.sort()
works = set()
upd = True
mn = 10**10
for t, e, x in events:
    if e == 1:
        works.add(x)
        if mn > x:
            mn = x
            upd = False
    elif e == 0:
        works.remove(x)
        if x == mn:
            upd = True
    else:
        if len(works) == 0:
            ans[x] = -1
        else:
            if upd:
                mn = min(works)
                upd = False
            ans[x] = mn
print(*ans)
### BUGGY CODE ###

n, m, l = map(int, input().split())

INF = 1 << 30
g = [[INF] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

h = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j] <= l:
            h[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            h[i][j] = min(h[i][j], h[i][k] + h[k][j])

q = int(input())
for _ in range(q):
    s, t = map(lambda x: int(x) - 1, input().split())
    if h[s][t] == INF:
        print(-1)
    else:
        print(h[s][t] - 1)


### FIXED CODE ###

n, m, l = map(int, input().split())

INF = 1 << 30
g = [[INF] * n for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    g[a][b] = c
    g[b][a] = c

for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j] = min(g[i][j], g[i][k] + g[k][j])

h = [[INF] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if g[i][j] <= l:
            h[i][j] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            h[i][j] = min(h[i][j], h[i][k] + h[k][j])

q = int(input())
for _ in range(q):
    s, t = map(lambda x: int(x) - 1, input().split())
    if h[s][t] == INF:
        print(-1)
    else:
        print(h[s][t] - 1)
### BUGGY CODE ###

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

for _ in range(N):
    a, b = list(map(int, input().split()))
    big_array += [a]*b

big_array.sort()

print(big_array[K-1])


### FIXED CODE ###

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

for _ in range(N):
    a, b = list(map(int, input().split()))
    val_dict[a] = val_dict.get(a, 0) + b

val_keys = sorted(val_dict.keys())

K_rest = K
for key in val_keys:
    K_rest -= val_dict[key]
    if K_rest <= 0:
        print(key)
        break
### BUGGY CODE ###

import bisect

n = int(input())
ans_head=[-1]
for i in range(n):
  a=int(input())
  if ans_head[0]>=a:
    ans_head=[a]+ans_head
  else:
    insert_index = bisect.bisect_left(ans_head,a)
    ans_head[insert_index-1]=a

  #print(ans_head)
print(len(ans_head))


### FIXED CODE ###

import bisect
n=int(input())
A=[]
for i in range(n):
  A.append(int(input()))
Ans=[A[-1]]
for i in reversed(range(n-1)):
  a=A[i]
  if a>=Ans[-1]:
    Ans.append(a)
  else:

    Ans[bisect.bisect_right(Ans,a)]=a

print(len(Ans))
### BUGGY CODE ###

def main():
	N, M, Q = map(int, input().split())
	LR = [list(map(int, input().split())) for _ in range(M)]
	PQ = [list(map(int, input().split())) for _ in range(Q)]

	lines = [[0] * (N + 1) for _ in range(N + 1)]

	for l, r in LR:
		lines[l][r] += 1

	for p, q in PQ:
		lines_sum = 0
		for y in range(p, q + 1):
			for x in range(p, q + 1):
				lines_sum += lines[y][x]
		print(lines_sum)
main()


### FIXED CODE ###

N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]

table = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

for l, r in LR:
	table[l][r] += 1

#for line in table:
#	print(*line)
#print()

for i in range(1, N + 1):
	for j in range(1, N + 1):
		table[i][j] += table[i][j - 1]
for i in range(1, N + 1):
	for j in range(1, N + 1):
		table[i][j] += table[i - 1][j]

#for line in table:
#	print(*line)
#print()

for p, q in PQ:
	#print(table[q][q], table[p - 1][q], table[q][p - 1], table[p - 1][p - 1])
	print(table[q][q] - table[p - 1][q] - table[q][p - 1] + table[p - 1][p - 1])
### BUGGY CODE ###

def e_balanced_path():
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for j in range(H)]
    B = [[int(i) for i in input().split()] for j in range(H)]

    dp = [[set() for j in range(W)] for i in range(H)]
    diff = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    dp[0][0].add(diff[0][0])
    for row in range(H):
        for col in range(W):
            for dr, dc in ((1, 0), (0, 1)):
                nr, nc = row + dr, col + dc
                if not (0 <= nr < H and 0 <= nc < W):
                    continue
                for k in dp[row][col]:
                    dp[nr][nc].add(k + diff[nr][nc])
                    dp[nr][nc].add(abs(k - diff[nr][nc]))
    return min(dp[H - 1][W - 1])

print(e_balanced_path())

### FIXED CODE ###

def e_balanced_path():
    # 参考: https://atcoder.jp/contests/abc147/submissions/8889160
    H, W = [int(i) for i in input().split()]
    A = [[int(i) for i in input().split()] for j in range(H)]
    B = [[int(i) for i in input().split()] for j in range(H)]

    # ビット列で集合を表現する場合、負の数をうまく扱えないので、バイアスをかける
    MAX_DIFF = (H + W) * 80  # 全マスで偏りが80変化するかもしれない

    diff = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

    # dp[i][j]: マス (i, j) で取りうる偏りの集合をビット列で持つ
    # ただし、ビット列の基準は MAX_DIFF 桁目である
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    # 左上のマスの更に上に、偏り0のマスがあることにする
    # (下から MAX_DIFF 桁目を1にする)
    dp[0][1] = 1 << MAX_DIFF

    for row in range(1, H + 1):
        for col in range(1, W + 1):
            k = diff[row - 1][col - 1]
            # マス (i, j) に対して左のマスで取りうる偏りに ±k したものが
            # マス (i, j) で取りうる偏り
            dp[row][col] |= dp[row][col - 1] << k
            dp[row][col] |= dp[row][col - 1] >> k
            # 上のマスについて同じことを行う
            dp[row][col] |= dp[row - 1][col] << k
            dp[row][col] |= dp[row - 1][col] >> k

    ans = MAX_DIFF
    # 右下のマスで取りうる偏りを抽出し、絶対値が0に最も近いもの
    # (1が立っているビットのうち、最も MAX_DIFF 桁目に近いもの) が解
    for k in range(2 * MAX_DIFF + 1):
        if (dp[H][W] >> k) & 1:
            # 下から k ビット目が1なら、|k - MAX_DIFF| の偏りを取りうる
            ans = min(ans, abs(k - MAX_DIFF))
    return ans

print(e_balanced_path())
### BUGGY CODE ###

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

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)

### FIXED CODE ###

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

MOD = 998244353

N = int(input())
XY = [[int(x) for x in input().split()] for _ in range(N)]
XY.sort() # X ascending
X,Y = zip(*XY)
Y_rank = {x:i for i,x in enumerate(sorted(Y),1)}

def BIT_update(tree,x):
    while x <= N:
        tree[x] += 1
        x += x & (-x)

def BIT_sum(tree,x):
    ret = 0
    while x:
        ret += tree[x]
        x -= x & (-x)
    return ret

pow2 = [1]
for _ in range(N):
    pow2.append(pow2[-1] * 2 % MOD)

answer = 0
tree = [0] * (N+1)
for L,(x,y) in enumerate(XY):
    y = Y_rank[y]
    R = N - 1 - L
    D = y - 1
    U = N - 1 - D
    LD = BIT_sum(tree,y)
    BIT_update(tree,y)
    LU = L - LD
    RD = D - LD
    RU = R - RD
    # bounding box が自分自身を含むような集合を数える
    # 全体から引く
    cnt = pow2[N]
    cnt -= pow2[L]
    cnt -= pow2[R]
    cnt -= pow2[D]
    cnt -= pow2[U]
    cnt += pow2[LD]
    cnt += pow2[LU]
    cnt += pow2[RD]
    cnt += pow2[RU]
    cnt -= 1
    answer += cnt

answer %= MOD

print(answer)
### BUGGY CODE ###

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

ball_n = [0, 0]

while sum(ball_n) != n:
    for _ in range(a):
        ball_n[0] += 1
        if sum(ball_n) == n:
            break
    
    if sum(ball_n) == n:
        break
    
    for _ in range(b):
        ball_n[1] += 1
        if sum(ball_n) == n:
            break

print(ball_n[0])

### FIXED CODE ###

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

ans = n // (a+b) * a
r = n % (a+b)

ans += min(a, r)

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

import numpy as	np
N,K=map(int,input().replace('\n','').split())
P=list(map(int,input().replace('\n','').split()))

m=-1.0
for i in range(N-K+1):
  if np.sum(P[i:i+K])>=m:
    m=np.sum(P[i:i+K])
    ml=P[i:i+K]

print((m+K)/2)

### FIXED CODE ###

import numpy as	np
N,K=map(int,input().replace('\n','').split())
P=list(map(int,input().replace('\n','').split()))

s=np.sum(P[0:K])
m=s
for i in range(1,N-K+1):
  s=s-P[i-1]+P[i+K-1]
  if s>=m:
    m=s
	
print((m+K)/2)
### BUGGY CODE ###

n = int(input())
X = []
L = []
for _ in range(n):
    x, l = map(int, input().split())
    X.append(x)
    L.append(l)
X = sorted(set(X), key=X.index)

areas = [(x - l, x + l)for x, l in zip(X, L)]
for i, (m0, M0) in enumerate(areas):
    for m, M in (areas[:i] + areas[i+1:]):
        if (m0 <= m) and (M <= M0):
            areas.pop(i)
# print(areas)

areas = sorted(areas, key=lambda x:x[0])
areas2 = []

for area in areas:
    if not areas2:
        areas2.append(area)
    elif areas2[-1][-1] <= area[0]:
        areas2.append(area)

# print(areas)
# print(areas2)

print(len(areas2))

### FIXED CODE ###

# https://atcoder.jp/contests/keyence2020/tasks/keyence2020_b

n = int(input())
X = []
L = []
for _ in range(n):
    x, l = map(int, input().split())
    X.append(x)
    L.append(l)

areas = [(x - l, x + l) for x, l in zip(X, L)]
areas = sorted(areas, key=lambda x:x[-1])

# print(areas)

ok = [areas[0]]
for area in areas[1:]:
    if ok[-1][-1] <= area[0]:
        ok.append(area)

# print(ok)
print(len(ok))
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

N = int(input())
a = [int(i) for i in input().split()]

sum_a = sum(a)

ans = 10**10
for i in range(1,N):
    x = sum(a[:i])
    ans = min(ans,abs(sum_a-2*x))

print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math

N = int(input())
a = [int(i) for i in input().split()]

sum_a = sum(a)

ans = 10**10
x = 0
for i in range(N-1):
    x += a[i]
    ans = min(ans,abs(sum_a-2*x))

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

class RollingHashSingle:
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        self.hash = [0]
        self.power = [1]
        for c in s:
            self.hash.append((self.hash[-1] * base + ord(c)) % mod)
            self.power.append(self.power[-1] * base % mod)

    def get(self, left, right):
        h = self.hash[right] - self.hash[left] * self.power[right - left]
        return (h + self.mod) % self.mod


class RollingHash:
    def __init__(self,
                 s,
                 base=(10**4 + 7, 10**4 + 9),
                 mod=(10**9 + 7, 10**9 + 9)):
        if isinstance(base, int):
            assert isinstance(mod, int)
            self.base = (base, )
            self.mod = (mod, )
        elif isinstance(base, tuple):
            assert isinstance(mod, tuple)
            assert len(base) == len(mod)
            self.base = base
            self.mod = mod
        else:
            raise ValueError()

        self._rh = [
            RollingHashSingle(s, base, mod)
            for base, mod in zip(self.base, self.mod)
        ]

    def get(self, left, right):
        return tuple(rh.get(left, right) for rh in self._rh)


n = int(input())
s = input().rstrip()
rh = RollingHash(s, base=10**4 + 7, mod=2**61 - 1)


def check(diff):
    d = {}
    for i in range(n - diff + 1):
        h = rh.get(i, i + diff)
        if h in d.keys():
            if abs(d[h] - i) >= diff:
                return True
        else:
            d[h] = i
    return False


lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
print(lo)

### FIXED CODE ###

def create_z_array(s):
    n = len(s)
    z_array = [0] * n
    left = 0
    right = 0
    for i in range(1, n):
        if i > right:
            left, right = i, i
            while right < n and s[right - left] == s[right]:
                right += 1
            z_array[i] = right - left
            right -= 1
        else:
            k = i - left
            if z_array[k] < right - i + 1:
                z_array[i] = z_array[k]
            else:
                left = i
                while right < n and s[right - left] == s[right]:
                    right += 1
                z_array[i] = right - left
                right -= 1
    return z_array


n = int(input())
s = input().rstrip()
res = 0
for i in range(n):
    z_array = create_z_array(s[i:])
    for j in range(1, len(z_array)):
        res = max(res, min(j, z_array[j]))
print(res)
### BUGGY CODE ###

def ok(k):
    # 長さkの連続部分列で重ならずに2回以上現れるものがある
    for i in range(n-2*k+1):
        X = S[i:i+k]
        for j in range(i+k, n-k+1):
            Y = S[j:j+k]
            if X == Y:
                return True
    return False


n = int(input())
S = list(input())
# 二分探索でTrueになる最大のkを求める
l, r = 0, n+1
while r-l > 1:
    c = (l+r)//2
    if ok(c):
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

def zalgo(S):
    # SとS[i:n]のlcpの長さを記録した配列を返す
    n = len(S)
    A = [0] * n
    j = 0
    for i in range(1, n):
        if i+A[i-j] < j+A[j]:
            A[i] = A[i-j]
        else:
            k = max(0, A[j]-i+j)
            while i+k < n and S[k] == S[i+k]:
                k += 1
            A[i] = k
            j = i
    A[0] = n
    return A


n = int(input())
S = input()
l = 0
for i in range(n):
    A = zalgo(S[i:])
    B = [min(j, a) for j, a in enumerate(A)]
    l = max(l, max(B))
print(l)
### BUGGY CODE ###

n,k,q=map(int,input().split())
point=[k for i in range(n)]
for i in range(q):
    point=[i-1 for i in point]
    point[int(input())-1]+=1        
for i in point:
    if(i>0):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[0 for i in range(n)]
for i in range(q):
    a[int(input())-1]+=1
for i in a:
    if k-q+i>0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

S.sort(reverse = True)
L = []

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i - 1]:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
L.append(cnt)

if L[0] != 1:
  print("No")
  exit()

DP = [[0] * N for _ in range(len(L))]
S = [0] * len(L)

for i in range(N):
  DP[0][i]= 1

for i in range(1, len(L)):
  for j in range(N):
    DP[i][j] = DP[i - 1][j]
  
  t = L[i]
  k = 0
  P = [0] * N
  for j in range(N):
    P[j] = k
    if DP[i][j] > t:
      DP[i][j] -= t
      k += t
      t = 0
    else:
      t -= DP[i][j]
      k += DP[i][j]
      DP[i][j] = 0
  if t != 0:
    print("No")
    exit()
  for j in range(N):
    DP[i][j] += P[j]

print("Yes")

### FIXED CODE ###

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

S.sort(reverse = True)
L = []

cnt = 1
for i in range(1, len(S)):
  if S[i] == S[i - 1]:
    cnt += 1
  else:
    L.append(cnt)
    cnt = 1
L.append(cnt)

if L[0] != 1:
  print("No")
  exit()

DP = [[0] * N for _ in range(len(L))]
S = [0] * len(L)

for i in range(N):
  DP[0][i]= 1

for i in range(1, len(L)):
  for j in range(N):
    DP[i][j] = DP[i - 1][j]
  
  t = L[i]
  k = 0
  P = [0] * N
  for j in range(N):
    P[j] = k
    if DP[i][j] > t:
      DP[i][j] -= t
      k += t
      t = 0
    else:
      t -= DP[i][j]
      k += DP[i][j]
      DP[i][j] = 0
  if t != 0:
    print("No")
    exit()
  for j in range(N):
    DP[i][j] += P[j]

print("Yes")
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]


for i in range(n):
    ret = a[:]
    ret.pop(i)
    print(max(ret))


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

a_s = sorted(a, reverse=True)
for i in range(n):
    if a[i] == a_s[0]:
        print(a_s[1])
    else:
        print(a_s[0])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

MOD = 10**9+7

step = [0] * (n+1)
step[0] = 1
step[1] = 1

for i in range(n+1):
    if i == 0 or i == 1:
        if i in a:
            step[i] = 0
    else:
        step[i] = step[i-1] + step[i-2]
        if i in a:
            step[i] = 0
        step[i] %= MOD

print(step[-1])


### FIXED CODE ###

n, m = map(int, input().split())
a = [0]*(n+1)
for j in range(m):
    pos = int(input())
    a[pos] = 1

MOD = 10**9+7

step = [0] * (n+1)
step[0] = 1
step[1] = 1

for i in range(n+1):
    if a[i] == 1:
        step[i] = 0
    else:
        if i != 0 and i != 1:
            step[i] = (step[i-1] + step[i-2]) % MOD

print(step[-1])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
m = [K for x in range(N)] 

for i in range(Q):
  m1 = [x-1 for x in m]
  a = int(input())
  m1[a-1] += 1
  m = m1
  
for b in m1:
  if b >0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

start = [K - Q] * N

for i in range(Q):
  a = int(input())
  start[a-1] += 1
     
for i in range(N):
  if start[i] > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

S = input()
Q = int(input())
reverse_count = 0
for i in range(Q):
  query = list(input().split())
  if(query[0] == '1'):
    reverse_count += 1
  else:
    if((int(query[1]) + reverse_count) % 2 == 1):
      S = query[2] + S
    else:
      S = S + query[2]
if(reverse_count % 2 == 1):
  S = S[::-1]
print(S)

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
cnt = 0
for i in range(Q):
  x = list(input().split())
  if(int(x[0]) == 1):
    cnt += 1
  else:
    if((cnt+int(x[1])) % 2 == 1):
      S.appendleft(x[2])
    else:
      S.append(x[2])

S = list(S)
if(cnt % 2 == 1):
  S = S[::-1]
print("".join(S))
### BUGGY CODE ###

class DisjointSet():
    def __init__(self):
        self.parent = None


def ancestor(elems, x):
    s = elems[x]
    while s.parent is not None:
        s = s.parent
    return s


def unite(elems, x, y):
    parent = DisjointSet()
    ancestor(elems, x).parent = parent
    ancestor(elems, y).parent = parent


def same(elems, x, y):
    return ancestor(elems, x) is ancestor(elems, y)


def main():
    n, q = [int(x) for x in input().split()]
    elems = [DisjointSet() for _ in range(n)]

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            unite(elems, x, y)
        else:
            print(1 if same(elems, x, y) else 0)


if __name__ == '__main__':
    main()



### FIXED CODE ###

class DisjointSetElement():
    def __init__(self, x):
        self.parent = x
        self.rank = 0


class DisjointSet():
    def __init__(self, n):
        self.elems = [DisjointSetElement(n) for n in range(n)]

    def _find_set(self, x):
        if x != self.elems[x].parent:
            self.elems[x].parent = self._find_set(self.elems[x].parent)
        return self.elems[x].parent

    def same(self, x, y):
        return self._find_set(x) == self._find_set(y)

    def _link(self, x, y):
        if self.elems[x].rank > self.elems[y].rank:
            self.elems[y].parent = x
        else:
            self.elems[x].parent = y
            if self.elems[x].rank == self.elems[y].rank:
                self.elems[y].rank += 1

    def unite(self, x, y):
        self._link(self._find_set(x), self._find_set(y))


def main():
    n, q = [int(x) for x in input().split()]
    ds = DisjointSet(n)

    for _ in range(q):
        com, x, y = [int(x) for x in input().split()]
        if com == 0:
            ds.unite(x, y)
        else:
            print(1 if ds.same(x, y) else 0)


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

N = int(input())

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

d = []
for i in range(1, len(A_list)):
		left = sum(A_list[:i])
		right = sum(A_list[i:])
		temp = abs(left - right)
		d.append(temp)

print(min(d))


### FIXED CODE ###

N = int(input())

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

left = 0
A_sum = sum(A_list)
ans = A_sum
for a in A_list:
		left += a
		right = A_sum - left
		ans = min(ans, abs(left-right))

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

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

for i in range(n):
    A2 = A.copy()
    A2.pop(i)
    A2.sort()
    print(A2[(n // 2) - 1])

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
sortA = sorted(A)

for i in range(n):
    if A[i] <= sortA[(n // 2) - 1]:
        print(sortA[n // 2])
    else:
        print(sortA[(n // 2) - 1])
### BUGGY CODE ###

L, R = map(int, input().split())
ans = []
for i in range(L,R):
    for j in range(i+1,R+1):
        ans.append((i*j)%2019)
print(min(ans))

### FIXED CODE ###

L, R = map(int, input().split())
ans_l = []
if R-L<2019:
    for i in range(L,R):
        for j in range(i+1,R+1):
            ans = (i*j)%2019
            ans_l.append(ans)
    print(min(ans_l))
else:
    print(0)
### BUGGY CODE ###

R = 1000000
p = [1]*R
p[0] = p[1] = 0
p[2] = 1
p[4::2] = [0 for i in range(4,R,2)]
idx = 2
for i in range(3,int(R**0.5)+1,2):
    if p[i]:
        p[i] = idx
        idx += 1
        p[2*i::i] = [0]*len(p[2*i::i])
while True:
    try:print p[i]
    except:break

### FIXED CODE ###

import math
n = []
while True:
    try:
        n.append(int(raw_input()))
    except:
        break
  
r = max(n)+1
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
p[3::2] = [0 for x in range(3,r,2)]
for i in range(2,sqrt,2):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)] 
  
for i in n:
     print sum(p[:i])