Bài tập

Sau chuỗi ngày ôn và thi mệt mỏi, Bờm quyết định du lịch đến đất nước Byteland. Đất nước xinh đẹp này có \(n\) thành phố, các thành phố kết nối với nhau bởi \(n-1\) con đường hai chiều. Con đường thứ \(i\) nối từ thành phố \(x\) đến thành phố \(y\) có độ dài \(w\).

Thêm nữa, qua quá trình khảo sát Bờm có lên thang điểm về độ đẹp cho mỗi thành phố. Độ đẹp của thành phố thứ \(i\) được đánh giá là \(a_i\).

Việc đi lại giữa các thành phố được thực hiện bằng xe buýt. Cách vận hành xe buýt ở đây cũng rất đặc biệt:

Giả sử xe buýt đang ở thành phố \(u\), nó sẽ xác định tuyến đi tiếp theo bằng cách chọn một thành phố \(v\) (\(v \neq u\) và có thể \((u,v)\) không có cạnh nối) sao cho giá trị \(a_v - d(u, v)\) là lớn nhất. Trong đó \(d(u, v)\) được định nghĩa là khoảng cách đi từ \(u\) đến \(v\). Nếu có nhiều thành phố thỏa mãn thì xe buýt sẽ di chuyển đến thành phố có chỉ số nhỏ nhất. Khi đã chọn được điểm đến là thành phố \(v\), xe buýt sẽ đi thẳng từ \(u\) đến \(v\) mà không dừng ở các thành phố trung gian.

Yêu cầu: Cho \(Q\) truy vấn, mỗi truy vấn có hai tham số \(s, k\) ứng với việc Bờm xuất phát từ thành phố \(s\) và di chuyển qua \(k\) tuyến đường bằng xe buýt theo cách mô tả ở trên. Hãy cho biết, với mỗi truy vấn thì Bờm sẽ kết thúc chuyến đi ở thành phố nào?

Input

• Dòng đầu chứa hai số nguyên dương \(n, Q\) (\(n, Q \leq 2 \times 10^5\)) là số thành phố và số truy vấn.
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) là độ đẹp của các thành phố (\(|a_i| \leq 10^9\)).
• \(n - 1\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(x, y, w\) mô tả một con đường hai chiều (\(1 \leq x, y \leq n,~ 0 < w \leq 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(s, k\) mô tả một truy vấn: thành phố xuất phát \(s\) và số tuyến đường \(k\) (\(1 \le s \le n\), \(k \le 10^6\)).

Output

Gồm \(Q\) dòng, mỗi dòng in ra chỉ số thành phố mà Bờm sẽ kết thúc chuyến đi ở mỗi truy vấn.

Example

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

5
3
3
1

Scoring

• Có 20% số test với \(n, Q \leq 200,~ k \leq 200\).
• Có 25% số test khác với \(n, Q \leq 2000\).
• Có 25% số test khác với \(k = 1\).
• Số test còn lại không có ràng buộc gì thêm.

Trong thời gian chờ vào tiết học, An và Lạc cùng nhau chơi một trò chơi đơn giản. An lấy một tờ giấy và học sinh hình chữ nhật kẻ ô vuông có chiều rộng \(W\), chiều cao \(H\) và vẽ một số điểm lên tờ giấy đó. Có thể xem góc dưới bên trái của tờ giấy có tọa độ \((0, 0)\) và góc trên bên phải có tọa độ \((W, H)\). Các điểm có thể vẽ trùng nhau nhưng được tính như các điểm phân biệt.

Lạc lấy ra một mảnh giấy hình chữ nhật có chiều rộng \(w\), chiều cao \(h\) và hai bạn tìm cách đặt mảnh giấy này lên tờ giấy sao cho các cạnh của mảnh giấy song song với các biên của tờ giấy đã vẽ các điểm, chiều rộng và chiều cao mảnh giấy tương ứng với chiều rộng và chiều cao của tờ giấy, và mảnh giấy phủ nhiều điểm nhất có thể. Các điểm nằm trên biên của mảnh giấy cũng được xem là bị phủ.

An, Lạc đã vào lớp. Bạn hãy tiếp tục trò chơi khi tờ giấy và mảnh giấy có kích thước lớn hơn.

Yêu cầu: Cho \(n\) điểm và kích thước \(w, h\) của mảnh giấy, hãy tìm số điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật đó.

Input

• Dòng đầu chứa ba số nguyên \(n, w, h\) (\(1 \leq n \leq 10^5\), \(1 \leq w, h \leq 10^8\));
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_i, y_i\) là tọa độ của điểm thứ \(i\) được vẽ trên tờ giấy (\(1 \leq x_i, y_i \leq 10^8\)).

Output

In ra một số là số lượng điểm lớn nhất bị phủ bởi mảnh giấy hình chữ nhật.

Example

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

4

10 8 8
8 9
20 14
3 9
7 8
3 4
7 8
10 19
6 11
5 10
8 2

7

Sau khi trải qua kì thi International Cat Programming Contest (ICPC) đầy căng thẳng và nhân dịp Giáng Sinh sắp đến, Neko đã quyết định sẽ quay trở về hành tinh mèo để du lịch và đón Giáng Sinh. Một trong những trò chơi truyền thống tại hành tinh mèo mỗi dịp Giáng Sinh là trò chơi "Permeowtation" với luật chơi như sau:

Ban đầu, người chơi sẽ được cho một hoán vị \(p_1, p_2, \ldots, p_n\). Ở mỗi bước, người chơi có thể hoán đổi hai phần tử liên tiếp trong hoán vị (nói cách khác, chọn một vị trí \(i\) sao cho \(1 \le i < n\) và hoán đổi hai phần tử \(p_i\) và \(p_{i+1}\)). Người chơi cần sắp xếp lại hoán vị \(p\) ban đầu với số lượng bước ít nhất có thể.

Vốn là người chơi giỏi nhất tại hành tinh mèo, Neko đã cảm thấy quá nhàm chán với trò chơi và nghĩ ra một phiên bản nâng cấp như sau:

Người chơi sẽ được cho hai hoán vị \(a\) và \(b\) với cùng độ dài \(n\). Với mỗi hoán vị có thứ tự từ điển từ \(a\) đến \(b\), người chơi sẽ xác định số bước ít nhất cần thực hiện để hoàn thành trò chơi. Cuối cùng, người chơi cần cho biết tổng số bước với tất cả hoán vị nói trên.

Neko nhận ra rằng việc hoàn thành trò chơi trên sẽ mất rất nhiều thời gian, và nhà cậu còn bao việc khác phải làm. Hãy giúp Neko hoàn thành trò chơi trên nhé.

Do đáp án có thể rất lớn, hãy in ra đáp án sau khi chia lấy phần dư cho \(10^9 + 7\).

\InputFile
Dòng đầu tiên gồm số nguyên dương \(n\) (\(1 \le n \le 200\,000\)) -- độ dài của hai hoán vị \(a\) và \(b\).

Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\)) -- mô tả hoán vị \(a\).

Dòng thứ bao gồm \(n\) số nguyên dương \(b_1, b_2, \ldots, b_n\) (\(1 \le b_i \le n\)) -- mô tả hoán vị \(b\).

Dữ liệu vào đảm bảo hoán vị \(a\) có thứ tự từ điển nhỏ hơn hoặc bằng hoán vị \(b\).

\OutputFile
In ra một số nguyên duy nhất là tổng số bước cần tìm sau khi chia lấy phần dư cho \(10^9 + 7\).

\Examples
\beginexample
\exmp
3
2 1 3
3 1 2

5

\endexample
\beginexample
\exmp
5
1 2 3 4 5
1 2 3 4 5

0

\endexample

\Note
Một hoán vị độ dài \(k\) là một dãy gồm \(k\) số nguyên có giá trị từ \(1\) đến \(k\), mỗi giá trị xuất hiện đúng một lần.

Với hai hoán vị \(p_1, p_2, \ldots, p_n\) và \(q_1, q_2, \ldots, q_n\) bất kì, ta định nghĩa hoán vị \(p\) có thứ tự từ điển nhỏ hơn hoán vị \(q\) nếu tồn tại một chỉ số \(i\) (\(1 \le i \le n\)) sao cho:

• \(p_j = q_j\) với \(1 \le j < i\)
• \(p_i < p_j\)

Ở ví dụ 1, ta có thể biến đổi từng hoán vị như sau:

• \([2, 1, 3] \xrightarrow{(3, 1)} [1, 2, 3]\)
• \([2, 3, 1] \xrightarrow{(2, 3)} [2, 1, 3] \xrightarrow{(1, 2)} [1, 2, 3]\)
• \([3, 1, 2] \xrightarrow{(1, 2)} [1, 3, 2] \xrightarrow{(2, 3)} [1, 2, 3]\)

Tổng số bước biến đổi cần tìm là \(1 + 2 + 2 = 5\).

Ở ví dụ 2, hoán vị \([1, 2, 3, 4, 5]\) đã được sắp xếp tăng dần nên ta không cần thực hiện bước biến đổi nào cả.

\Scoring

• Subtask 1 (\(10\%\) số điểm): \(n \le 2\,000\), \(a_i = b_i\)
• Subtask 2 (\(20\%\) số điểm): \(n \le 2\,000\), \(a_i = i\), \(b_i = N-i+1\)
• Subtask 3 (\(30\%\) số điểm): \(n \le 2\,000\)
• Subtask 4 (\(40\%\) số điểm): Không có giới hạn gì thêm

\endproblem

Cho một cây có gốc gồm \(n\) đỉnh. Các đỉnh được đánh số từ \(1\) đến \(n\), và đỉnh \(1\) là gốc của cây. Mỗi đỉnh \(i\) có một giá trị nguyên dương \(v_i\).

Bạn cần thực hiện \(q\) truy vấn thuộc một trong hai loại sau:

• Thay đổi giá trị: Gán giá trị của đỉnh \(s\) thành \(x\).
• Tính tổng đường đi: Tính tổng giá trị của tất cả các đỉnh trên đường đi từ gốc (đỉnh \(1\)) đến đỉnh \(s\) (bao gồm cả hai đầu).

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \le n, q \le 2 \cdot 10^5)\) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(n\) số nguyên \(v_1, v_2, \ldots, v_n\) \((1 \le v_i \le 10^9)\) --- giá trị ban đầu của các đỉnh.

\(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \le a, b \le n)\) --- mô tả một cạnh nối giữa hai đỉnh \(a\) và \(b\). Đảm bảo các cạnh này tạo thành một cây.

\(q\) dòng tiếp theo, mỗi dòng mô tả một truy vấn:

• Dạng 1 s x \((1 \le s \le n, 1 \le x \le 10^9)\): thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Dạng 2 s \((1 \le s \le n)\): tính tổng giá trị các đỉnh trên đường đi từ đỉnh \(1\) đến đỉnh \(s\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa tổng giá trị cần tìm.

Example

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

11
8