16966번 - 구간과 쿼리 2

문제

N개의 쿼리가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 2가지 종류가 있고 아래와 같다. 가장 처음에 집합에는 아무것도 없다.

• 1 x y (x < y): 새로운 구간 (x, y)를 집합에 추가한다. 구간의 크기는 이전에 추가된 구간의 크기보다 크다.
• 2 a b (a ≠ b): a번째 추가된 구간에서 b번째 추가된 구간으로 이동하는 경로가 있으면 1, 없으면 0을 출력한다. 가장 처음 추가된 구간은 1번째 구간이다.

구간 (x₁, y₁)에서 구간 (x₂, y₂)로 이동하려면 x₂ < x₁ < y₂ 또는 x₂ < y₁ < y₂를 만족해야 한다. 구간 I₁에서 I₂로 이동하는 경로가 있다는 것은 I1에서 I2로 집합에 추가된 구간만을 이용해서 이동할 수 있을 때이다.

입력

첫째 줄에 쿼리의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 입력으로 주어지는 모든 값은 절댓값이 10⁹보다 작거나 같은 정수이다. 2번 쿼리는 적어도 2개의 쿼리가 집합에 추가된 이후에 주어진다.

출력

2번 쿼리가 주어질 때마다 결과를 출력한다.

제한

힌트