Bài tập

Trên trục số, Roy và Biv có một tập hợp gồm \(n\) điểm, mỗi điểm có vị trí và màu sắc. Mỗi điểm là một trong ba màu: đỏ (R), xanh lá (G) hoặc xanh dương (B).

Họ muốn nối các điểm lại bằng những đoạn thẳng (cạnh). Mỗi cạnh có thể nối hai điểm bất kỳ, và chi phí của cạnh chính là khoảng cách giữa hai điểm được nối.

Mục tiêu là chọn một số cạnh sao cho toàn bộ \(n\) điểm được kết nối (trực tiếp hoặc gián tiếp). Tuy nhiên, có một điều đặc biệt:

• Roy không nhìn thấy màu đỏ.
• Biv không nhìn thấy màu xanh dương.

Do đó, họ muốn chọn các cạnh sao cho:

• Nếu bỏ toàn bộ điểm màu đỏ, thì các điểm còn lại (xanh lá và xanh dương) vẫn phải kết nối được với nhau.
• Nếu bỏ toàn bộ điểm màu xanh dương, thì các điểm còn lại (xanh lá và đỏ) cũng phải kết nối được với nhau.

Hãy giúp họ tìm cách kết nối các điểm với tổng chi phí nhỏ nhất, thoả mãn hai điều kiện trên.

Chú ý: Tọa độ các điểm là phân biệt và tăng dần.

Hai điểm được xem là "kết nối với nhau" nếu tồn tại chuỗi các cạnh nối giữa chúng.

\InputFile

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 300\,000\)) --- số lượng điểm.
• \(n\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(p_i\) (\(1 \le p_i \le 10^9\)) và một ký tự \(c_i\) (\(c_i \in \{R, G, B\}\)) --- tọa độ và màu sắc của điểm thứ \(i\).
• Các tọa độ \(p_i\) là phân biệt và tăng dần.

\OutputFile

In ra chi phí nhỏ nhất cần thiết để kết nối các điểm, thỏa mãn điều kiện của Roy và Biv.

\Scoring

• Subtask 1 (10 điểm): tất cả các điểm chỉ có màu G.
• Subtask 2 (11 điểm): không có điểm nào có màu G.
• Subtask 3 (15 điểm): tất cả các điểm có màu R hoặc màu G.
• Subtask 4 (17 điểm): \(n \le 10\).
• Subtask 5 (47 điểm): không có ràng buộc gì thêm.

Example

4
1 G
4 R
8 B
15 G

24

Cho một cây có \(n\) đỉnh, được đánh số từ \(1\) đến \(n\). Mỗi đỉnh có một giá trị ban đầu.

Nhiệm vụ của bạn là xử lý các loại truy vấn sau:

• Thay đổi giá trị của đỉnh \(s\) thành \(x\).
• Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \cdot 10^5)\) -- số đỉ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 \leq v_i \leq 10^9)\) -- giá trị của mỗi đỉnh.
• \(n-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) -- biểu thị một cạnh nối giữa hai đỉnh \(a\) và \(b\).

• \(q\) dòng cuối cùng mô tả các truy vấn, mỗi truy vấn có một trong hai dạng sau:

• 1 s x: Thay đổi giá trị của đỉnh \(s\) thành \(x\) \((1 \leq s \leq n, 1 \leq x \leq 10^9)\).

• 2 a b: Tìm giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\) \((1 \leq a, b \leq n)\).

Output

• In ra \(Q\) số nguyên trên một dòng duy nhất biểu thị giá trị lớn nhất trên đường đi giữa hai đỉnh \(a\) và \(b\).

Example

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

4 3 

Cho một dãy số nguyên \(A\) gồm \(n\) phần tử.

Với mỗi đoạn con \(A[l..r]\) (\(1 \le l \le r \le n\)), ta định nghĩa:

• \(W(l,r,x)\) là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\dots,A[r]\).

• Gọi \(B\) là dãy gồm các phần tử đoạn \(A[l..r]\), và sắp xếp \(B\) tăng dần được dãy \(C\).

  Tập trung vị của đoạn là:
  $
  S(l,r) = { C[\lfloor (k-1)/2 \rfloor],\; C[\lceil (k-1)/2 \rceil] },
  $
  trong đó \(k = r-l+1\).

Giá trị của đoạn \((l,r)\) được định nghĩa là:
$
\max_{x \in S(l,r)} W(l,r,x).
$

Lưu ý: tập \(S(l,r)\) sẽ chứa phần tử trung vị duy nhất nếu đoạn có số phần tử lẻ, và chứa hai phần tử trung vị nếu đoạn có số phần tử chẵn.

Yêu cầu: Tìm giá trị lớn nhất trong tất cả các đoạn \((l,r)\).

\InputFile

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 5 \times 10^5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(A_i\) (\(1 \le A_i \le n\)).

\OutputFile

In ra một số nguyên duy nhất --- giá trị lớn nhất có thể đạt được.

\Scoring

• \(11\) điểm: \(n \le 100\).
• \(17\) điểm: \(n \le 2 \times 10^3\).
• \(7\) điểm: tồn tại \(x\) sao cho dãy tăng đến \(x\) rồi giảm sau đó.
• \(12\) điểm: \(A_i \le 3\).
• \(13\) điểm: mỗi giá trị xuất hiện nhiều nhất 2 lần.
• \(22\) điểm: \(n \le 8 \times 10^4\).
• \(18\) điểm: không có ràng buộc thêm.

Example

7
1 2 3 1 2 1 3

3

9
1 1 2 3 4 3 2 1 1

2

Vương quốc Byteland có \(N\) nút giao thông trọng điểm được đánh số từ \(1\) đến \(N\). Hệ thống đường cao tốc gồm \(M\) con đường hai chiều đảm bảo đi lại giữa các nút giao thông với nhau, các con đường được đánh số từ \(1\) đến \(M\). Con đường thứ \(i\) nối nút giao thông \(X_i\) với \(Y_i\) (\(1 \le i \le M, 1 \le X_i, Y_i \le N\)) có phí đường bộ là \(Z_i\) (\(Z_i \le 10^6\)).

\begincenter

\endcenter

Ví dụ: Từ nút giao thông 1 đến nút giao thông 4 (như hình vẽ) có hai đường đi khác nhau: đường đi thứ nhất là \(1 \to 2 \to 4\) có tổng phí đường bộ là 30, đường đi thứ hai là \(1 \to 3 \to 4\) có tổng phí đường bộ là 35.

Để giảm chi phí đi lại góp phần thúc đẩy phát triển kinh tế giữa các vùng, Quốc vương đã ban hành chính sách mới cho phép người dân đăng kí miễn phí tối đa \(K\) con đường bất kì trên hành trình của mình.

Yêu cầu: Hãy lập trình tính tổng phí đường bộ nhỏ nhất khi đi từ nút giao thông \(S\) đến nút giao thông \(T\) sau khi được Quốc vương ban hành chính sách mới.

Input

• Dòng đầu ghi năm số nguyên dương \(N, M, K, S, T\).
• Dòng thứ \(i\) trong \(M\) dòng tiếp theo ghi ba số nguyên dương \(X_i, Y_i, Z_i\).
• Các số trong tệp cách nhau ít nhất một dấu cách.

Output

• Gồm một số nguyên duy nhất là tổng phí đường bộ nhỏ nhất tìm được.

Example

4 4 1 1 4
1 2 10
1 3 30
2 4 20
3 4 5

5 

Scoring

• Có 20% số điểm tương ứng \(1 < N, M \le 100000\) và \(K = 0\);
• Có 20% số điểm tương ứng \(1 < N \le 100, M \le 1000\) và \(K = 1\);
• Có 20% số điểm tương ứng với \(1 < N, M \le 100000\) và \(K = 1\);
• Có 40% số điểm tương ứng với \(100 < N, M \le 100000\) và \(1 < K \le 10\).