30050번 - 트리와 쿼리 ${10}^{9}$

루트의 번호가 $1$이고 정점의 개수가 무한한 포화 이진 트리가 있다. 이 트리에서 $i$번 정점의 왼쪽 자식은 $2i$, 오른쪽 자식은 $2i+1$번 정점이며, 서로 양방향으로 연결되어 있다. 이 트리에 $Q$개의 쿼리를 수행해 보자.

쿼리의 종류는 다음과 같다.

• 1 a b: $b$번 정점과 그 부모를 잇는 간선을 제거하고, $a$번 정점과 $b$번 정점을 잇는 간선을 추가한다. 단, $ \lfloor \log_{2}{a} \rfloor < \lfloor \log_{2}{b} \rfloor$를 만족하는 경우만 주어진다.
• 2 c d: $c$번 정점에서 $d$번 정점으로 가는 단순 경로상에 존재하는 모든 정점의 번호의 합을 출력한다.

1번 쿼리를 수행한 후에도 항상 트리의 조건을 만족함을 증명할 수 있다. 2번 쿼리는 최소 한 번 이상 주어진다.

첫 번째 줄에 쿼리의 개수를 나타내는 정수 $Q$가 주어진다. $(1 \le Q \le 50\,000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 주어진다. $(1 \le a,b,c,d \le {10}^{9})$

2번 쿼리가 주어질 때마다 그 결과를 한 줄에 하나씩 출력한다.

$\lfloor x \rfloor$는 $x$와 같거나 그보다 작은 정수 중 가장 큰 정수이다.