Vào năm 2077, Hacker huyền thoại mang biệt danh "Zero" đã xâm nhập vào lõi máy chủ của tập đoàn MegaCorp để tìm kiếm "Mã Nguồn Genesis" – một chuỗi dữ liệu chứa đựng bí mật của thế giới cũ. Tuy nhiên, lõi máy chủ được bảo vệ bởi một siêu AI có tên là "The Eraser" (Kẻ Xóa Bỏ).

"The Eraser" không tấn công ngay lập tức, mà kích hoạt một giao thức trò chơi cổ xưa. Nó hiển thị một dòng mã hóa gồm các khối dữ liệu năng lượng. Để trích xuất được thông tin, Zero buộc phải tham gia trò chơi này. Nếu thắng, anh sẽ lấy được khối dữ liệu giá trị nhất. Nếu thua, anh sẽ chỉ nhận được rác thải dữ liệu vô giá trị.

Quy tắc trò chơi

Trước mặt Zero là một chuỗi mã hóa có độ dài ~n~, bao gồm ~n~ số nguyên. Hệ thống đảm bảo rằng ~n~ luôn là một số lẻ.

Hai người chơi, Zero (Người đi trước) và AI "The Eraser" (Người đi sau), sẽ lần lượt thực hiện thao tác:

1. Trong mỗi lượt, người chơi buộc phải chọn hai khối dữ liệu nằm liền kề nhau và xóa chúng khỏi chuỗi.
2. Sau khi xóa, các khối dữ liệu còn lại ở hai bên sẽ tự động được nối lại với nhau (liền kề nhau).
3. Trò chơi tiếp diễn cho đến khi chỉ còn lại duy nhất một khối dữ liệu trong chuỗi.

Mục tiêu:

• Zero (Người đi trước): Muốn khối dữ liệu cuối cùng còn sót lại có giá trị lớn nhất có thể.
• The Eraser (Người đi sau): Muốn khối dữ liệu cuối cùng có giá trị nhỏ nhất có thể (để phá hoại Zero).

Đối mặt với khả năng tính toán siêu việt của AI, Zero nhận ra những chiến thuật đơn giản đều vô dụng. Lúc này, trên màn hình hiện lên dòng thông báo trêu ngươi từ AI: "Những gì ngươi cố tình bỏ qua, những gì ngươi không cần đến, đôi khi lại chính là chìa khóa của định mệnh."

Hãy giúp Zero tìm ra chiến thuật tối ưu để đánh bại AI.

Yêu cầu

Hãy tìm giá trị của khối dữ liệu cuối cùng khi Zero chơi tối ưu (để tối đa hóa kết quả) và AI cũng chơi tối ưu (để tối thiểu hóa kết quả).

Định dạng đầu vào (Input)

• Dòng đầu tiên chứa số nguyên ~T~ - số lượng bộ dữ liệu (test cases).
• Với mỗi bộ dữ liệu:
  • Dòng đầu tiên chứa một số lẻ ~n~ - độ dài của chuỗi.
  • Dòng thứ hai chứa ~n~ số nguyên ~a_1, \ldots, a_n~ - giá trị của các khối dữ liệu trong chuỗi.

Định dạng đầu ra (Output)

• Với mỗi bộ dữ liệu, in ra một dòng chứa một số nguyên duy nhất: giá trị của khối dữ liệu còn lại cuối cùng.

Ví dụ (Sample)

Input

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

Output

3
3
2
2

Giới hạn

~T \geq 1~

~1 \leq n \leq 10^6~

~1 \leq a_i \leq n~

Tổng ~n~ trong tất cả các test case (~\sum n~) không quá ~10^6~.

Nhà Thám hiểm Huyền thoại Elara đang đứng trước cổng Hầm Ngục Vĩnh Cửu . Để chinh phục hầm ngục này, cô cần lập một đội hình tinh nhuệ từ các Đặc nhiệm của Vương quốc.

Vương quốc có ~n~ Đặc nhiệm được đánh số từ ~1~ đến ~n~. Mỗi đặc nhiệm thứ ~i~ có ba chỉ số quan trọng: Sức mạnh Tấn công ~a_i~, Khả năng Phòng thủ ~b_i~ và Điểm Vinh quang ~c_i~. Tất cả họ đều là chiến binh dày dạn kinh nghiệm, với ~a_i \ge b_i~. Đặc biệt, chỉ số Khả năng Giữ vị trí (~b_i~) của bất kỳ hai đặc nhiệm nào cũng khác nhau (đảm bảo mỗi vị trí phòng thủ là độc nhất).

Nhà Thám hiểm Elara quyết định áp dụng một quy tắc tuyển chọn đội hình như sau:

Quy tắc Thay thế Chiến trường

Trong mỗi nhiệm vụ, Elara xác định ba tham số: phạm vi đặc nhiệm tiềm năng ~l~ đến ~r~, và quy mô đội hình chính ~k~.

1. Đội hình Khởi tạo: Đội hình ban đầu gồm ~k~ đặc nhiệm đầu tiên trong phạm vi, tức là các đặc nhiệm thứ ~l, l+1, \ldots, l+k-1~.

2. Quá trình Thử thách: Các đặc nhiệm còn lại trong phạm vi, từ ~l+k, l+k+1, \ldots, r~, sẽ lần lượt được cử vào cuộc thử thách gia nhập đội. Đối với mỗi đặc nhiệm đang thử thách ~i~:

   • Thách thức Vị trí: Đặc nhiệm ~i~ kiểm tra xem có tồn tại một đặc nhiệm ~j~ hiện đang trong đội mà Sức mạnh Tấn công của ~i~ đủ mạnh để xuyên thủng Khả năng phòng thủ của ~j~: ~a_i \ge b_j~
   • Thay thế Chiến thuật: Nếu tìm thấy đặc nhiệm ~j~ như vậy, đặc nhiệm ~i~ sẽ thay thế ~j~. Nếu có nhiều đặc nhiệm ~j~ thỏa mãn điều kiện, đặc nhiệm có Khả năng phòng thủ (~b_j~) thấp nhất sẽ bị loại khỏi đội, và đặc nhiệm ~i~ gia nhập.
   • Rút lui: Nếu không tìm được đặc nhiệm ~j~ nào trong đội để thay thế, đặc nhiệm ~i~ sẽ rút lui (không tham gia đội), và đội hình hiện tại không thay đổi.

Sau khi tất cả đặc nhiệm từ ~l+k~ đến ~r~ đã hoàn thành thử thách, đội hình cuối cùng sẽ được chốt để tiến vào Hầm Ngục.

Yêu cầu Bài toán

Tuyển chọn diễn ra trong ~q~ nhiệm vụ. Mỗi nhiệm vụ, Elara đưa ra các tham số ~l, r, k~ khác nhau.

Hãy tính tổng Điểm Vinh quang (~c_i~) của tất cả các đặc nhiệm trong đội hình cuối cùng sau mỗi vòng tuyển chọn.

Định dạng Dữ liệu

Đầu vào

• Dòng 1: Hai số nguyên ~n, q~ (số đặc nhiệm, số nhiệm vụ).
• Dòng 2: ~n~ số nguyên ~a_1,\ldots,a_n~ (Sức mạnh Tấn công).
• Dòng 3: ~n~ số nguyên ~b_1,\ldots,b_n~ (Khả năng Phòng thủ).
• Dòng 4: ~n~ số nguyên ~c_1,\ldots,c_n~ (Điểm Vinh quang).
• ~q~ dòng tiếp theo: Mỗi dòng ba số nguyên ~l, r, k~ (phạm vi và quy mô đội hình).

Đầu ra

• ~q~ dòng: Mỗi dòng là tổng Điểm Vinh quang của đội hình cuối cùng tương ứng với nhiệm vụ đó.

Giới hạn

• Đối với toàn bộ dữ liệu: ~1 \leq n,q \leq 5 \times 10^5~

  ~1 \leq a_i, b_i \leq n~

  ~1 \leq c_i \leq 10^9~

  ~1 \leq l \leq r \leq n~

  ~1 \leq k \leq r-l+1~

• Đảm bảo khả năng phòng thủ (~b_i~) của bất kỳ hai đặc nhiệm nào cũng khác nhau.

Input

5 3 
4 4 3 5 5 
4 2 3 1 5 
1 10 100 1000 10000 
1 4 2 2 
5 2 
1 5 3

Output

1001 
10100 
10101

* Giải thích * Ở truy vấn 1: Ban đầu có đặc nhiệm 1, 2 trong team. Sau đó 3 thay thế 2, rồi 4 thay thế 3

Subtest

• 25% số lượng test có N<=2000, Q<=2000
• 25% số lượng test có k = 1

Vào năm 30XX, Trái Đất đứng trước nguy cơ bị xâm lăng bởi người ngoài hành tinh. Để đối phó, Hội đồng Phòng thủ Liên hành tinh quyết định kích hoạt một lá chắn năng lượng khổng lồ bao quanh hành tinh.

Hệ thống lá chắn này được tạo thành bởi K trạm vệ tinh (được đánh số ID từ 1 đến K). Để lá chắn hoạt động, toàn bộ K vệ tinh này phải được kết nối với nhau tạo thành một vòng tròn khép kín duy nhất (mỗi vệ tinh kết nối tín hiệu với đúng 2 vệ tinh khác bên cạnh nó).

Tuy nhiên, việc thiết lập không hề đơn giản. Do các hạn chế về phần cứng cũ, một số cặp vệ tinh bắt buộc phải được kết nối trực tiếp với nhau để truyền tải dữ liệu lõi. Cụ thể, các kỹ sư đã liệt kê ra các cặp (A, B) nghĩa là vệ tinh A bắt buộc phải kết nối trực tiếp với vệ tinh B trong vòng tròn (kết nối theo chiều nào cũng được).

Nhiệm vụ của bạn là giúp Hội đồng kiểm tra xem liệu có thể sắp xếp và kết nối các vệ tinh sao cho thỏa mãn tất cả các ràng buộc phần cứng này và tạo thành một vòng tròn năng lượng hoàn chỉnh đi qua tất cả K vệ tinh hay không?

Input:

Dữ liệu được cho trên nhiều test (bộ dữ liệu). Với mỗi test:

• Dòng đầu tiên chứa 2 số nguyên K và M (3 <= K <= 10^9, 0 <= M <= 10^5). Trong đó K là tổng số lượng vệ tinh và M là số lượng cặp kết nối bắt buộc.
• M dòng tiếp theo, mỗi dòng chứa 2 số A và B (1 <= A, B <= K, A khác B) mô tả yêu cầu vệ tinh A phải kết nối trực tiếp với vệ tinh B.

Bộ test được kết thúc bằng một dòng chứa 2 số 0. Bạn không cần xử lí test này.

Output:

• Với mỗi test, hãy ghi ra màn hình ký tự Y (Yes) nếu việc thiết lập vành đai là khả thi, hoặc N (No) nếu không thể thỏa mãn các yêu cầu.

Example test

Input:

4 3
2 3
1 3
2 1
1000000000 0
3 6
3 2
2 1
1 2
1 3
2 3
3 1
0 0

Output:

N
Y
Y