``Cano lướt song'' là một trò chơi cảm giác mạnh phổ biến ở các khu du lịch bãi biển hay hải đảo. Trò chơi có một chiếc phao dài hình quả chuối được bơm căng và gắn chặt với một chiếc cano. Một nhóm người chơi ngồi thành hàng lên chiếc phao này để người điều khiển chiếc cano kéo đi.

Cô giáo Mây ở trường LK tổ chức chuyến đi dã ngoại cho các bạn trong lớp. Lần này, đảo Lý Sơn là địa điểm được cô giáo chọn. Sẽ có \(n\) bạn tham dự chuyến đi này. Các bạn được đánh số từ \(1\) đến \(n\); bạn thứ \(i\) có độ sợ nước là \(w_i\). Độ sợ nước càng cao, bạn đó càng sợ bị rơi xuống nước. Ngược lại, những bạn có độ sợ nước thấp là những bạn sẵn sàng xông pha chinh phục biển khơi.

Cô giáo Mây muốn cho cả \(n\) bạn thử sức với trò chơi ``cano lướt sóng'' ở trên. Do có đông học sinh; cô giáo dự định sẽ chia các bạn vào một hoặc nhiều nhóm và mỗi nhóm sẽ cùng leo lên một chiếc phao chuối. Cách chia nhóm của cô giáo thoả mãn các điều kiện sau:

• Mỗi nhóm chứa một hoặc nhiều bạn học sinh.
• Mỗi bạn thuộc vào chính xác một nhóm.
• Các bạn trên cùng một nhóm phải có số thứ tự liên tiếp nhau.
• Số nhóm có thể là một số nguyên bất kỳ từ \(1\) đến \(n\).

Như đã nói ở trên, để trò chơi ``cano lướt sóng'' được hấp dẫn, một nhóm nên có sự kết hợp của những bạn dũng cảm, ham cảm giác mạnh và cả những bạn run sợ, nhút nhát. Bởi thế, cô giáo Mây cho rằng, độ hấp dẫn của một nhóm được tính bằng chênh lệch độ sợ nước của bạn có độ sợ nước nhỏ nhất và bạn có độ sợ nước lớn nhất trong nhóm. Nói cách khác, nếu một nhóm chứa các bạn học sinh có số thứ tự từ \(l\) đến \(r\) \((1 \leq l \leq r \leq n)\), độ hấp dẫn của nhóm là \(\max(w_l, w_{l+1}, \ldots, w_{r - 1}, w_r) - \min(w_l, w_{l+1}, \ldots, w_{r - 1}, w_r)\).

Cô giáo Mây muốn chia nhóm sao cho tổng độ hấp dẫn của các nhóm là lớn nhất có thể. Và đây là bài toán mà bạn cần giúp cô.

Tuy nhiên, cô giáo nhận ra rằng, việc chia nhóm có thể không đơn giản như vậy, bởi các bạn có thể quý nhau hoặc ghét nhau một cách ngẫu nhiên. Do đó, sẽ có những đôi bạn đòi phải được lên cùng một chiếc phao chuối, nhưng cũng có những đôi bạn khác lại nhất quyết không chịu đồng hành cùng nhau.

Bởi vậy, cô giáo đã viết ra \(q\) tình huống, mỗi tình huống thuộc một trong hai dạng sau:

• L \(x\) \(y\): Bạn thứ \(x\) và bạn thứ \(y\) là một cặp và nhất định phải được xếp vào cùng một nhóm.
• H \(x\) \(y\): Bạn thứ \(x\) và bạn thứ \(y\) đã từng quý nhau nhưng giờ lại ghét nhau, vì vậy hai bạn nhất quyết phải ở hai nhóm khác nhau.

Với mỗi tình huống kể trên, các bạn cần giúp cô tìm ra cách chia nhóm sao cho vẫn thoả mãn các tiêu chí ban đầu, vẫn tối đa hoá tổng độ hấp dẫn của các nhóm, mà đồng thời thoả mãn điều kiện bổ sung. Lưu ý rằng, trong mỗi tình huống, chỉ có một đôi bạn quý hoặc ghét nhau, nên chỉ có thêm chính xác một ràng buộc bổ sung so với bài toán ban đầu.

Input

• Dòng đầu tiên chứa số nguyên \(\theta\) \((1 \leq \theta \leq 6)\) là số thứ tự của subtask chứa test này.
• Dòng thứ hai chứa hai số nguyên \(n\) và \(q\) \((0 < n, \frac{q}{3} \leq 500^2)\) lần lượt là số bạn tham gia chuyến đi và số tình huống của cô giáo.
• Dòng thứ ba chứa \(n\) số nguyên \(w_1, w_2, \ldots, w_n\) \((0 \leq w_i \leq 10^8)\) thể hiện độ sợ nước của các bạn.
• Trong \(q\) dòng cuối cùng, mỗi dòng mô tả một tình huống theo một trong hai dạng ở trên. Các tham số \(x\) và \(y\) thoả mãn \(1 \leq x, y \leq n\) và \(\sin{x} \cos{y} \neq \sin{y} \cos{x}\).

Output

• In ra \(q + 1\) số nguyên, trong đó:
  • Số nguyên đầu tiên là kết quả của bài toán gốc, tức tổng độ hấp dẫn tối đa của các nhóm trong trường hợp không có ràng buộc bổ sung.
  • \(q\) số nguyên còn lại thể hiện kết quả của bài toán trong \(q\) tình huống khi có thêm một ràng buộc bổ sung.
• Các số nguyên được viết trên một dòng, ngăn nhau bởi dấu cách.

Scoring

• Subtask \(1\) (\(18\) điểm): \(n \leq 17\) và \(q \leq 52\)
• Subtask \(2\) (\(13\) điểm): \(n \leq 80\) và \(q \leq 400\)
• Subtask \(3\) (\(17\) điểm): \(n \leq 300\) và \(q \leq 900\)
• Subtask \(4\) (\(15\) điểm): \(q \leq 60\) và tất cả các tình huống đều có dạng H \(x\) \(y\).
• Subtask \(5\) (\(16\) điểm): Tất cả các tình huống đều có dạng H \(x\) \(y\).
• Subtask \(6\) (\(21\) điểm): Không có ràng buộc gì thêm.

Examples

1
7 4
2 2 7 1 9 9 7
L 2 4
H 4 5
L 4 5
H 2 4

15 10 8 15 15