_minhduc biết rằng muốn tán được người yêu cũ của shiba thì trước tiên bản thân phải giàu trước đã. Nhờ sự dẻo mồm nịnh hót của mình nên _minhduc trở thành giám đốc của một công ti giàu nhất Việt Nam ~trước khi shiba thành lập nên một công ti lớn hơn cả công ti này...~. Từ đây, có một vấn đề "nho nhỏ" lại được sinh ra...

Trong mùa hè, trường đại học Flower_On_Stone đã gửi \(M\) sinh viên, được đánh số từ \(1\) đến \(M\), tham gia các cuộc nghiên cứu với các địa điểm khác nhau. Tất cả các địa điểm đều gần một con đường, bắt đầu từ trường Flower_On_Stone, và sinh viên thứ \(i\) đang ở địa điểm cách Flower_On_Stone \(x_i\) km (theo hướng từ trái qua phải). Tất cả các \(x_i\) đều là số nguyên không âm và chúng ta có \(x_1 \le x_2 \le … \le x_{M-1} \le x_M\).

Do công việc nghiên cứu khoa học sôi nổi trong mùa hè, tất cả các sinh viên đã tiêu hết tiền của họ và họ cần Flower_On_Stone cung cấp thêm tiền để có thể trở về trường. Mỗi sinh viên sẽ về trường bằng con đường sinh viên đó đi từ trường đến địa điểm họ tham gia nghiên cứu (có nghĩa là khoảng cách từ địa điểm họ đang tham gia về trường cũng là \(x_i\), nhưng chỉ được đi từ phải qua trái). Sinh viên thứ \(i\) sẽ cần \(v_i\) VND cho mỗi km để chi trả cho thức ăn và các nhu cầu khác. Ngoài ra, có các chuyến xe bus ở \(N\) địa điểm mà các sinh viên có thể thuê. Một chiếc xe bus ở địa điểm cách \(y_j\) km từ Flower_On_Stone sẽ có chi phí là \(c_j\) VND và nó có thể chở các sinh viên trở lại trường (tất nhiên là các xe bus sẽ đi hướng bên trái để giúp các sinh viên về đến trường). Mỗi lần thuê một chiếc xe thì chiếc xe đó chở được nhiều người mà chỉ cần trả với giá \(c_j\) một lần(*). Các chiếc xe bus di chuyển trực tiếp đến Flower_On_Stone mà không có các trạm dừng trung gian để người khác lên xe. Trường đại học đã đặt điều kiện rằng mỗi sinh viên bắt buộc phải trở lại Flower_On_Stone bằng xe bus để đảm bảo rằng mỗi sinh viên sẽ xuống ở trạm của trường đại học và sẽ đến trường để giao các tài liệu đã được thu thập trong cuộc nghiên cứu.

Ban đầu, _minhduc chỉ cần tính toán số tiền tối thiểu cần thiết để tất cả sinh viên có thể trở về trường để còn viết chi phiếu phát tiền cho học sinh. Tuy nhiên, sếp của anh ấy lại yêu cầu biết thêm số tiền tối thiểu cần trả để trả về lần lượt là chỉ cho sinh viên đầu tiên (đang ở gần trường nhất, chỉ cho \(2\) sinh viên đầu tiên (có số thứ tự là \(1\) và \(2\)), và cứ như thế cho đến tất cả các sinh viên. Do yêu cầu thêm độ khó cho công việc, sau khi hoàn thành nhiệm vụ này, _minhduc sẽ được một kỉ nghì dài hạn. Dù chiếc Macbook M2 Pro đã sửa xong từ đời nào, tuy nhiên sau vài năm nó đã cũ và không thể sử dụng được. Bạn hãy giúp _minhduc nhé ~để cậu ấy còn lên kế hoạch cưa đổ "người yêu cũ" của shiba nào :Đ~.

Yêu cầu: Bạn hãy viết một chương trình để giúp _minhduc tính toán tổng số tiền tối thiểu cần thiết để tất cả sinh viên có thể trở về Flower_On_Stone. Hơn nữa, ban quản lý đại học muốn biết số tiền tối thiểu cần trả để trả về lần lượt là chỉ cho sinh viên đầu tiên (đang ở gần nhất), chỉ cho \(2\) sinh viên đầu tiên (có số thứ tự là \(1\) và \(2\)), và cứ như thế đến khi in ra tất cả \(M\) sinh viên.

Input

• Dòng đầu tiên chứa số nguyên dương \(\phi\) - số thứ tự của subtask chứa test đó \((1 \le \phi \le 5)\).

• Dòng tiếp theo chứa số nguyên dương \(N\) – số lượng địa điểm có xe bus để cho thuê. \((1 \le N \le 10^5)\).

• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên không âm lần lượt là \(y_j\) và \(c_j\) - lần lượt là khoảng cách từ Flower_On_Stone đến địa điểm tương ứng nơi có thể thuê xe bus, và chi phí thuê xe bus tại địa điểm đó \((0 \le y_j \le 2^{30}, 1 \le c_j \le 2^{40})\).

• Dòng tiếp theo chứa số nguyên dương \(M\) - số sinh viên tham gia vào cuộc nghiên cứu \((1 \le M \le 10^5)\).

• \(M\) dòng cuối cùng, mỗi dòng chứa hai số nguyên không âm \(x_i\) và \(v_i\) - lần lượt là khoảng cách từ Flower_On_Stone đến địa điểm nơi sinh viên tương ứng được gửi đi vào địa điểm đó, và số tiền mà sinh viên đó cần để đi bộ mỗi km \((0 \le x_i \le 2^{30}, 1 \le v_i \le 2^{30})\).

• Bộ dữ liệu luôn đảm bảo rằng \(x_i \le x_{i+1}\) với mọi \(1 \le i < M\) và \(y_j \le y_{j+1}\) với mọi \(1 \le j < N\) và đáp án không vượt quá \(10^{18}\).

• Bộ dữ liệu vào luôn đảm bảo rằng sẽ có ít nhất một chiếc xe bus đủ điều kiện để chở tất cả các sinh viên về trường.

Output

• Gồm \(M\) dòng. Dòng thứ \(i\) \((1 \le i \le M)\) in ra số tiền tối thiểu để \(i\) sinh viên đầu tiên có thể về.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Có \(N \le 10\), \(M \le 6\).

• Subtask \(2\) (\(20\%\) số điểm): Dữ kiện đề bài khác với (*) rằng tất cả các sinh viên đi cùng một chiếc xe bus bất kì mỗi người đều trả tiền cho chiếc xe đó và tất cả các giá trị \(v_i\) đều bằng nhau.

• Subtask \(3\) (\(20\%\) số điểm): Có \(N \le 14\), \(M \le 100\).

• Subtask \(4\) (\(25\%\) số điểm): Có \(N \le 1000\), \(M \le 100\).

• Subtask \(5\) (\(15\%\) số điểm): Có \(N \le 2 \times 10^4\), \(M \le 1000\).

Example

1
3
6 5
7 10
28 12
3
7 1
8 9
29 11

6
19
42

2
3
6 5
7 10
28 12
3
7 1
8 1
29 1

6
13
26

Sau khi trở nên giàu có và có dịp được nghỉ dài ngày, _minhduc quyết định sẽ tìm đường sang nhà "bạn gái cũ" của shiba nhằm làm chuyện ai cũng biết, đó chính là rủ cô ấy đi chơi...

Nơi _minhduc sống là một thành phố có thể coi là một đồ thị vô hướng với \(n\) đỉnh và \(m\) cạnh. Nhà của _minhduc ở vị trí đỉnh \(1\) và nhà cô "bạn gái cũ" của shiba ở vị trí đỉnh \(n\).

Hiện tại, thành phố của cậu ấy đang thi công xây dựng. Có tất cả \(k\) vị trí đã được di dời dân cư nhằm chuẩn bị cho quá trình xây thêm đường phố. Có thể nói tập đoàn của shiba ở thành phố này là rất lớn, vì vậy tiếng nói của _minhduc với vai trò là một Giám đốc điều hành cũng rất có trọng lượng. Cậu ấy có thể yêu cầu xây dựng thêm một con đường giữa hai đỉnh bất kì đã được di dời dân cư để xây dựng đường phố kia. Cậu ấy cũng có thể xây dựng một con đường đè lên con đường đã có. Mục đích của cậu ấy là tối đa hóa độ dài của đường đi ngắn nhất từ nhà _minhduc tới nhà bạn gái cũ của shiba để tránh để lại dấu vết. Bạn hãy giúp cầu ấy nhé.

Yêu cầu: Tính độ dài lớn nhất của đường đi ngắn nhất sau khi đã xây dựng thêm một con đường giữa nhà của _minhduc và "bạn gái cũ" của shiba.

Input

• Dòng thứ nhất chứa số nguyên \(\phi\) - số thứ tự của subtask chứa test đó.
• Dòng thứ hai chứa ba số nguyên dương \(n,m,k\) (\(1 \le n,m \le 2 \times 10^5, 2 \le k \le n\)).
• Dòng thứ ba chứa \(k\) số nguyên dương phân biệt \(s_1, s_2,..., s_k\) (\(1 \le s_i \le n\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v\) thể hiện một cạnh của đồ thị (\(1 \le u,v \le n\)).
• Dữ liệu đảm bảo luôn có đường đi từ \(1\) đến \(n\) ngay cả khi chưa thực hiện nối hai đỉnh đặc biệt.

Output

• Một dòng chứa một số nguyên dương duy nhất là kết quả bài toán.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(k = 2\).
• Subtask \(2\) (\(20\%\) số điểm): \(k = n\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(4\) (\(20\%\) số điểm): \(k \le 10^3\).
• Subtask \(5\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

1
7 6 2
4 6
1 2
2 3
3 4
4 5
5 6
6 7

5

Sau khi rủ được cô "bạn gái cũ" kia đi chơi thành công, hai người đã có một khoảng thời gian cực kì vui vẻ ở bên nhau, dẫu cho biết rằng shiba vẫn đau khổ vì lụy tình. Trong quãng thời gian du lịch đó, "bạn gái cũ" của shiba đã đưa ra một bài toán mà shiba đã từng không làm được khi cô ấy hỏi để thách đố và sẽ cưới _minhduc nếu cậu ấy trả lời được...

Bài toán đó như sau:

Bạn được cho một cây có \(n\) đỉnh và \(n-1\) cạnh và một mảng \(a\) gồm \(n\) phần tử. Ban đầu giá trị của đỉnh thứ \(i\) bằng \(a_i\). Có hai loại truy vấn:

• 1 u v p: Gọi \(s_1, s_2,..., s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó thực hiện thao tác \(\oplus\) với tất cả các đỉnh đó, nói cách khác ta gán cho \(a_{s_1} = a_{s_1} \oplus p\), \(a_{s_2} = a_{s_2} \oplus p\),..., \(a_{s_k} = a_{s_k} \oplus p\) \((0 \le p \le 2^{10}-1)\).
• 2 u v: Gọi \(s_1, s_2,..., s_k\) là các đỉnh trên đường đi từ \(u\) đến \(v\). Sau đó cần đưa ra tổng trọng số đỉnh của các nút trên đường đi từ \(u\) đến \(v\), nói cách khác cần đưa ra tổng \(S = a_{s_1} + a_{s_2} + ... + a_{s_k}\).

Do bài toán quá khó, _minhduc lại phải nhờ tới quân sư của mình - quân sư của kẻ phản diện, đó là Flower_On_Stone. Tuy nhiên, Flower_On_Stone đang có chuyến công tác nước ngoài nên không giúp cậu ấy được. Lần này, cậu ấy quyết định sẽ đưa lên đây để hỏi các bạn. Các bạn hãy giúp cậu ấy nhé.

Biểu thức \(x\) \(\oplus\) \(y\) biểu diễn phép toán tử XOR của hai số \(x\) và \(y\).

Yêu cầu: Với mỗi truy vấn loại \(2\), đưa ra kết quả trên một dòng.

Tuy nhiên, chuyện đi chơi riêng tư này đã bị tai mắt của shiba biết được. Từ đây, mời bạn về LQDOJ Contest #6 - Bài 5 để hóng drama nhé :Đ.

Input

• Dòng đầu tiên chứa một số nguyên \(\phi\) - số thứ tự của subtask chứa test đó \((1 \le \phi \le 6)\).
• Dòng thứ hai chứa một số nguyên dương \(n\) (\(1 \le n \le 10^5\)).
• Dòng thứ ba chứa \(n\) số nguyên \(a_1,a_2,...a_n\) (\(1 \le a_i \le 2^{10}-1\)).
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v\) - mô tả một cạnh của cây.
• Dòng tiếp theo chứa một số nguyên dương \(q\) (\(q \le 10^5\)) - số lượng truy vấn.
• \(q\) dòng cuối cùng, mỗi dòng chứa một truy vấn như mô tả ở trên.

Output

• Với mỗi truy vấn loại \(2\), đưa ra kết quả bài toán trên một dòng.

Scoring

• Subtask \(1\) (\(15\%\) số điểm): \(n,q \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): cây thoả mãn điều kiện với hai cạnh \((u,v)\) bất kì \((u < v)\) thì \(u = \lfloor \frac{v}{2} \rfloor\).
• Subtask \(3\) (\(20\%\) số điểm): mọi truy vấn update đều có \(u = v\).
• Subtask \(4\) (\(10\%\) số điểm): cây thoả mãn điều kiện đỉnh \(u\) được nối với đỉnh \(u+1\) với mọi \(1 \le u \le n-1\).
• Subtask \(5\) (\(15\%\) số điểm): cây thoả mãn điều kiện mỗi đỉnh không có nhiều hơn \(2\) cạnh.
• Subtask \(6\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

1
6
4 3 2 5 3 4
1 2
1 3
2 4
2 5
3 6
2
1 2 4 2
2 1 2

5