Cây nhị phân cân bằng bậc $n$ được định nghĩa bao gồm tổng cộng $2^n-1$ đỉnh và được đánh số từ $1$ đến $2^n-1$. Với mọi đỉnh thứ $i$ từ $1$ đến $2^{n-1}-1$ sẽ có đúng 2 đỉnh con là $2i$ và $2i+1$. Tất cả các đỉnh từ $2^{n-1}$ đến $2^n-1$ không có đỉnh con nào.

Một hôm, weqd muốn thử thách khả năng lập trình của bạn bằng một trò chơi. Ban đầu, weqd có 1 món đồ chơi có dạng cây nhị phân cân bằng bậc $n$. Cậu ta sẽ đánh các giá trị trên cây, với đỉnh thứ $i$, cậu ta sẽ đánh giá trị là $i$. Sau đó, weqd sẽ tiến hành thay đổi giá trị giữa $2$ đỉnh bất kì (anh ấy sẽ thực hiện điều đó trong $q$ lần). weqd sẽ yêu cầu bạn tính giá trị hàm $f(i)+g(i)$ với mọi $1\le i\le 2^n-1$. Trong đó, hàm $f(x)$ là giá trị nhỏ nhất trong đường đi từ đỉnh $1$ tới đỉnh thứ $x$, còn hàm $g(x)$ là giá trị lớn nhất trong đường đi từ đỉnh $1$ tới đỉnh thứ $x$

Nhiệm vụ của bạn là hãy viết chương trình để hoàn thành thử thách trên.

2 2
1 2
2 3

4 5 3