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

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
s = set() # いったところ
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = [-2, -1, 0, 1, 2]

while True:
  # 移動A
  stemp = set()
  while d != deque():
    Th, Tw = d.popleft()
    s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h = Th + i
      _w = Tw + j
      _p = (_h, _w)
      if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
        d.append(_p)
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in b:
      for j in b:
        _h = Th + i
        _w = Tw + j
        _p = (_h, _w)
        if (not (_p) in s) and _h >= 0 and _h < h and _w >= 0 and _w < w and t[_h][_w] == '.':
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

### FIXED CODE ###

from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()
### BUGGY CODE ###

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

ret = 1
MOD = 10 ** 9 + 7

from collections import Counter
import sys

ca = Counter(A)
cb = Counter(B)

if ca.most_common(1)[0][1] >= 2 or cb.most_common(1)[0][1] >= 2:
    print(0)
    sys.exit(0)


for n in range(N * M, 0, -1):
    a = A.index(n) if n in A else -1
    b = B.index(n) if n in B else -1

    # 両方みつけた
    if a != -1 and b != -1:
        pass

    # Bの方だけ見つけた
    elif a == -1 and b != -1:
        cnt = sum(1 for x in A if x > n)
        ret *= cnt

    # Aの方だけ見つけた
    elif a != -1 and b == -1:
        cnt = sum(1 for x in B if x > n)
        ret *= cnt

    # 両方なかった
    else:
        cntA = sum(1 for x in A if x > n)
        cntB = sum(1 for x in B if x > n)
        ret *= (cntA * cntB - (N * M - n))
    ret = ret % MOD

print(ret)


### FIXED CODE ###

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

ret = 1
MOD = 10 ** 9 + 7

from collections import Counter
import sys

ca = Counter(A)
cb = Counter(B)

if ca.most_common(1)[0][1] >= 2 or cb.most_common(1)[0][1] >= 2:
    print(0)
    sys.exit(0)

A.sort()
B.sort()

import bisect


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1


for n in range(N * M, 0, -1):
    a = index(A, n)
    b = index(B, n)
    cntA = len(A) - bisect.bisect_right(A, n)
    cntB = len(B) - bisect.bisect_right(B, n)

    # 両方みつけた
    if a != -1 and b != -1:
        pass

    # Bの方だけ見つけた
    elif a == -1 and b != -1:
        ret *= cntA

    # Aの方だけ見つけた
    elif a != -1 and b == -1:
        ret *= cntB

    # 両方なかった
    else:
        ret *= (cntA * cntB - (N * M - n))
    ret = ret % MOD

print(ret)
### BUGGY CODE ###

a, b, c, k = map(int, input().split())

ans = 0
for i in range(k):
    if a:
        ans += 1
        a -= 1

    elif b:
        b -= 1

    elif c:
        ans -= 1
        c -= 1

print(ans)

### FIXED CODE ###

a, b, c, k = map(int, input().split())

ans = 0
if a < k:
    ans = a
else:
    ans = k

minus = k - (a + b)

if minus > 0:
    ans -= minus

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

n = input()
A = [int(x) for x in input().split()]
product = 1
 
for a in A:
    product *= a
    if a ==0:
      break
 
print(product if product <= 10**18 else -1)

### FIXED CODE ###

import sys

n = input()
A = sorted([int(x) for x in input().split()], reverse=True)

if A[-1] == 0:
    print(0)
    sys.exit()

product = 1
for a in A:
    product *= a
    if product > 10**18:
        product = -1
        break

print(product)
### BUGGY CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if h[i] in h_list and w[i] in w_list:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

print(ans)

### FIXED CODE ###

H,W,M = map(int,input().split())
h = [0]*M
w = [0]*M

from collections import defaultdict
counter_h = defaultdict(int)
counter_w = defaultdict(int)

for i in range(M):
    h[i],w[i] = map(int, input().split())
    counter_h[h[i]] += 1
    counter_w[w[i]] += 1

MAX_h = max(counter_h.values())
h_list = [k for k, v in counter_h.items() if v == MAX_h]
MAX_w = max(counter_w.values())
w_list = [k for k, v in counter_w.items() if v == MAX_w]


ans = MAX_h+MAX_w
check = 0

for i in range(M):
    if counter_h[h[i]]==MAX_h and counter_w[w[i]]==MAX_w:
        check += 1

if len(h_list)*len(w_list)==check:
    ans -= 1

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

a = input()
#l = list(a)

q = int(input())

default_order = True
for i in range(q):
  x = input().split()
  if x[0] == "1":
    default_order = default_order ^ True
  elif x[0] == "2":
    insert_type = default_order ^ False
    if x[1] == "2":
      insert_type = not(insert_type)
    if insert_type:
      #l.insert(0,x[2])
      a = x[2] + a
    else:
      #l.append(x[2])
      a = a + x[2]
if not(default_order):
  l = list(a)
  l.reverse()
  a = ''.join(l)

#print(''.join(l))
print(a)


### FIXED CODE ###

a = input()
l = list(a)
list_ins = [0] * 200000
ins_cnt = 0
list_app = [0] * 200000
app_cnt = 0

q = int(input())

default_order = True
for i in range(q):
  x = input().split()
  if x[0] == "1":
    default_order = default_order ^ True
  elif x[0] == "2":
    insert_type = default_order ^ False
    if x[1] == "2":
      insert_type = not(insert_type)
    if insert_type:
      list_ins[ins_cnt] = x[2]
      ins_cnt += 1
    else:
      list_app[app_cnt] = x[2]
      app_cnt += 1
ret = ""
if ins_cnt > 0:
  list_ins = list_ins[0:ins_cnt]
else:
  list_ins = []
if app_cnt > 0:
  list_app = list_app[0:app_cnt]
else:
  list_app = []
if default_order:
  list_ins.reverse()
  ret = ''.join(list_ins) + ''.join(l) + ''.join(list_app)
else:
  list_app.reverse()
  l.reverse()
  ret = ''.join(list_app) + ''.join(l) + ''.join(list_ins)

print(ret)
### BUGGY CODE ###

n,k,q=list(map(int,input().split()))
s=[k]*n
for i in range(q):
  a=int(input())
  s=list(map(lambda x:x-1,s))
  s[a-1]+=1
t=list(map(lambda x:'Yes' if x>0 else 'No',s))
[print(i) for i in t]

### FIXED CODE ###

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

from collections import*
n,c=map(int,input().split())
d=defaultdict(list)
for s,t,r in sorted([tuple(map(int,input().split()))for i in range(n)],key=lambda x:x[0]):
    if len(d[r])>0:
        if d[r][-1][-1]==s:
            d[r].append((d[r].pop()[0],t))
        else:
            d[r].append((s,t))
    else:
        d[r].append((s,t))
di=[]
for i in d.values():
    di+=i
x=sorted(di,key=lambda x:x[0])
ans=0
bannpei=0
#print(x)
while len(x)>0:
    for s,t in x.copy():
        if bannpei+1<=s:
            x.remove((s,t))
            bannpei=t
#        print(bannpei)
    ans+=1
    bannpei=0
#    print(x)
print(ans)

### FIXED CODE ###

n,c=map(int,input().split())
table=[[0]*10**5for i in range(c)]
for i in range(n):
    s,t,c=map(int,input().split())
    table[c-1][s-1:t]=[1]*(t-s+1)
print(max(map(sum,zip(*table))))
### BUGGY CODE ###

import sys
input=sys.stdin.readline

check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    check[0]=min(check[n]+n*d,check[0])

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0,0:N*d}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
N,M=map(int,input().split())

a,b=map(int,input().split())
A=[a]
B=[b]

l=[1 for i in range(N+1)]

L=[[]for i in range(N+1)]

for i in range(M-1):
    x,y=map(int,input().split())
    L[x].append(y)
    L[y].append(x)
    
l[a]=0
l[b]=0


P=a
for i in range(10**5):
    for j in L[P]:
        if l[j]!=0:
            P=j
            l[j]=0
            A.append(j)
            break
    if len(L[P])==0:
        break
    elif max(L[P])==0:
        break
P=b
for i in range(10**5):
    for j in L[P]:
        
        if l[j]!=0:
            P=j
            l[j]=0
            B.append(j)
            break
    if len(L[P])==0:
        break
    elif max(L[P])==0:
        break
A=A[::-1]
ans=A+B
print(len(ans))

ANS=str(ans[0])
for i in range(1,len(ans)):
    ANS+=" "+str(ans[i])
print(ANS)
        
    

### FIXED CODE ###

import sys
input=sys.stdin.readline

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

R=[1 for i in range(N+1)]
A,B=map(int,input().split())
R[A]=0
R[B]=0

L=[[]for i in range(N+1)]
L[A].append(B)
L[B].append(A)

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

l=[A]
P=A
#print(L)

for i in range(10**6):
    flag=0
    #print("P",L[P])
    for j in L[P]:
        #print("j",L,L[P],j,P)
        if R[j]==1:
            P=j
            R[j]=0
            l.append(j)
            flag+=1
            break
    if flag==0:
        break
#print(l)
r=[B]
P=B
for i in range(10**6):
    flag=0
    #print("P",L[P])
    for j in L[P]:
        #print("j",L,L[P],j,P)
        if R[j]==1:
            P=j
            R[j]=0
            r.append(j)
            flag+=1
            break
    if flag==0:
        break
#print(r)
l=l[::-1]
ans=l+r

ANS=str(ans[0])
for i in range(1,len(ans)):
    ANS+=" "+str(ans[i])
print(len(ans))
print(ANS)
### BUGGY CODE ###

def mid_1(X):
    return X[(len(X)) // 2]


def mid(X):
    return X[(len(X)) // 2 - 1]


def main():
    N = int(input())

    X = list(map(int, input().split()))
    X_ = X[:]
    X_.sort()
    for i in range(N):
        if X[i] in X_[:N // 2]:
            print(mid_1(X_))
        else:
            print(mid(X_))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import random


def mid_1(X):
    return X[(len(X)) // 2]


def mid(X):
    return X[(len(X)) // 2 - 1]


def main():
    N = int(input())

    X = list(map(int, input().split()))
    # N = 200000
    # X = [random.randint(0, 1000000000) for _ in range(N)]
    X_ = X[:]
    X_.sort()
    X__ = X_[:N // 2]
    X__ = X__[-1]

    x_1 = mid_1(X_)
    x = mid(X_)

    ans = []
    # print(X_)
    # print(X__)
    for i in range(N):
        if X[i] <= X__:
            print(x_1)
            # ans.append(x_1)
        else:
            print(x)
            # ans.append(x)


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

A,B=map(int, input().split())
a=0
for i in range(A,B+1):
  a=a^i
print(a)

### FIXED CODE ###

s,t=map(int, input().split())
def g(x):
  u=((x-1)//2)%2
  if x%2==0:
    return x^u
  return u
def f(x,y):
  return g(s-1)^g(t)
print(f(s,t))
### BUGGY CODE ###

num = int(raw_input())
array = raw_input().split(" ")

array_list = list(set(array[:]))
contain = []
if num % 2 == 0:
    for i in range(num / 2):
        contain.append(i * 2 + 1)
else:
    for i in range(num / 2 + 1):
        contain.append(i * 2)

all_ok = True
for i in range(len(array)):

    if int(array[i]) in contain:
        if (int(array[i]) == 0 and array.count(array[i]) == 1):
            continue
        elif (int(array[i]) != 0 and array.count(array[i]) == 2):
            continue
        else:
            all_ok = False
            break
    else:
        all_ok = False
        break

div = pow(10, 9) + 7
if all_ok:
    print pow(2, (num/2) ) % div
else:
    print 0


### FIXED CODE ###

num = int(raw_input())
array = map(int, raw_input().split(" "))

a = sorted(array)

if num % 2 == 0:
    for i in xrange(0, num, 2):
        if a[i] != a[i + 1]:
            print 0
            break
    else:
        div = pow(10, 9) + 7
        print pow(2, num / 2) % div
else:
    for i in xrange(1, num, 2):
        if a[i] != a[i + 1]:
            print 0
            break
    else:
        div = pow(10, 9) + 7
        print pow(2, num / 2) % div
### BUGGY CODE ###

from heapq import heappush, heappop

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

jobs = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

ans = 0
heap = []
for day in range(1,M+1):
	for i in jobs:
		ccc = 0
		if i[0] == day:
			heappush(heap, -i[1])
			ccc += 1
		elif i[0] > day:
			del(jobs[0:ccc])
			break
    
	if len(heap) > 0:
		ans += -heappop(heap)

print(ans)

### FIXED CODE ###

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
X = sorted([list(map(int, input().split())) for _ in range(N)], key = lambda x: x[0])

hq = []
ans, j = 0, 0

for i in range(1, M + 1):  # M - i 日後にするバイトを考える
    while (j < N) and (X[j][0] <= i):
        heappush(hq, -X[j][1])  # 候補の追加
        j += 1
    if len(hq):
        ans += -heappop(hq)  # 候補があるとき、候補から最大値を取り出す

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

from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        if ai == 1:
            continue
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        if ai == 1:
            continue
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


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

import sys
from heapq import heappop, heappush

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    ch -= 1
    cw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    M = [[-1 for w in range(W)] for h in range(H)]
    for h in range(H):
        s = input().strip("\n")
        for w in range(W):
            if s[w] == "#":
                M[h][w] = -2

    q = []
    heappush(q, (0, ch, cw))
    while q:
        dist, h, w = heappop(q)
        if M[h][w] == -1:
            M[h][w] = dist
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and M[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            heappush(q, (dist, h+dh, w+dw))
                        else:
                            heappush(q, (dist + 1, h+dh, w+dw))
    print(M[fh][fw])

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1
    sw -= 1
    fh, fw = map(int, input().split())
    fh -= 1
    fw -= 1

    S = [input().strip("\n") for _ in range(H)]

    q = deque()
    P = [[-1 for _ in range(W)] for h in range(H)]
    q.append((0, sh, sw))
    while q:
        d, h, w = q.popleft()
        if P[h][w] == -1:
            P[h][w] = d
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if 0<=h+dh<H and 0<=w+dw<W and S[h+dh][w+dw] == "." and P[h+dh][w+dw] == -1:
                        if abs(dh) + abs(dw) == 1:
                            q.appendleft((d, h+dh, w+dw))
                        else:
                            q.append((d+1, h+dh, w+dw))
    print(P[fh][fw])
    

    return 0

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

class UnionFind:
    def __init__(self,n):
        self.parent = {}
        for i in range(n):
            self.parent[i] = i

    def get_root(self,x):
        r = x
        while self.parent[r]!=r:
            r = self.parent[r]
        return r

    def unite(self,x,y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        if rx!=ry: self.parent[rx] = ry

    def same(self,x,y):
        rx = self.get_root(x)
        ry = self.get_root(y)
        if rx==ry: return 1
        else: return 0


n,q = map(int,raw_input().split(' '))
tree = UnionFind(n)

answers = []
for _ in range(q):
    com,x,y = map(int,raw_input().split(' '))
    if com==0:
        tree.unite(x,y)
    elif com==1:
        answers.append(tree.same(x,y))

for a in answers:
    print a

### FIXED CODE ###

class UnionFind:
    def __init__(self,n):
        self.parent = {}
        for i in range(n):
            self.parent[i] = i

    def get_root(self,x):
        r = x
        depth = 0
        path = [r]
        while self.parent[r]!=r:
            r = self.parent[r]
            path.append(r)
            depth += 1
        for n in path:
            self.parent[n] = r
        return r,depth

    def unite(self,x,y):
        rx,dx = self.get_root(x)
        ry,dy = self.get_root(y)
        if rx!=ry:
            if dx > dy:
                self.parent[ry] = rx
            else:
                self.parent[rx] = ry

    def same(self,x,y):
        rx,_ = self.get_root(x)
        ry,_ = self.get_root(y)
        if rx==ry: return 1
        else: return 0


n,q = map(int,raw_input().split(' '))
tree = UnionFind(n)

answers = []
for _ in range(q):
    com,x,y = map(int,raw_input().split(' '))
    if com==0:
        tree.unite(x,y)
    elif com==1:
        answers.append(tree.same(x,y))

for a in answers:
    print a
### BUGGY CODE ###

import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if prime.count(m) == 1:
                count += 1
    print count

### FIXED CODE ###

import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if p[m-1] == 1:
                count += 1
    print count
### BUGGY CODE ###

S = input()
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                T = que[4]+S
            else:
                T = S+que[4]
        else:
            if flag:
                T = S+que[4]
            else:
                T = que[4]+S
        S = T
if flag:
    print(S)
else:
    for i in range(len(S)):
        print(S[len(S)-i-1], end = '')
    print()


### FIXED CODE ###

S = input()
T = ''
Q = int(input())
flag = True
for i in range(Q):
    que = input()
    if len(que) == 1:
        if flag:
            flag = False
        else:
            flag = True
    else:
        if que[2] == '1':
            if flag:
                T = T+que[4]
            else:
                S = S+que[4]
        else:
            if flag:
                S = S+que[4]
            else:
                T = T+que[4]
if flag:
    U = ''
    for i in range(len(T)):
        U += T[len(T)-i-1]
    print(U+S)
else:
    U = ''
    for i in range(len(S)):
        U += S[len(S)-i-1]
    print(U+T)
### BUGGY CODE ###

X = int(input())
l = []
for i in range(int(X ** 0.5) + 1):
  j = 2
  while i ** j <= X:
    l.append(i ** j)
    j += 1
l.sort()
print(l[-1])

### FIXED CODE ###

X = int(input())
l = []
if X < 4:
  print(1)
else:
  for i in range(2, int(X ** 0.5) + 1):
    j = 2
    while i ** j <= X:
      l.append(i ** j)
      j += 1
  l.sort()
  print(l[-1])