{-# LANGUAGE OverloadedStrings #-}

import Data.Maybe
import qualified Data.ByteString.Char8 as C
import Control.Monad(forM_)

data Tree a = Node (Tree a) a (Tree a)

initTree :: a -> Tree a
initTree x = Node (initTree x) x (initTree x)

insert' :: Int -> a -> Tree a -> Tree a
insert' 0 y (Node l _ r) = Node l y r
insert' i y (Node l x r)
  | mod i 2 == 1 = Node l' x r
  | otherwise = Node l x r'
    where i' = div i 2
          l' = (insert' i' y l)
          r' = (insert' (i' - 1) y r)

at :: Tree a -> Int -> a
at (Node _ x _) 0 = x
at (Node l _ r) i
  | mod i 2 == 1 = at l i'
  | otherwise = at r (i' - 1)
    where i' = div i 2

getInts :: IO [Int]
getInts = do
  ss <- C.getLine
  return $ map (fst . fromJust . C.readInt) $ C.words ss

getIntss :: Int -> IO [[Int]]
getIntss 0 = return []
getIntss n = do
  xs <- getInts
  xss <- getIntss (n - 1)  
  return $ xs : xss

getRoot :: Tree (Int,Int) -> Int -> (Int,Int)
getRoot tree i = if i' == (-1) || i' == i then (i,rank) else getRoot tree i'
  where x@(i',rank) = tree `at` i
  
solve :: [[Int]] -> [C.ByteString]
solve xss = solve' xss tree
  where tree = initTree ((-1),1)

solve' :: [[Int]] -> Tree (Int,Int) -> [C.ByteString]
solve' [] _ = []
solve' ([p,a,b]:xss) tree = if p == 0
  then solve' xss $ if xr == yr then insert' xi (xi, xr+1) (insert' yi (xi,yr) tree) else if xr < yr then (insert' xi (yi,xr) tree) else (insert' yi (xi,yr) tree)
  else t : solve' xss tree 
    where (xi, xr) = getRoot tree a
          (yi, yr) = getRoot tree b
          t = (if xi == yi then "1" else "0")
   
main :: IO ()
main = do
  xs <- getInts
  xss <- getIntss $ xs !! 1
  let ys = solve xss
  forM_ ys $ \y -> C.putStrLn y 