Vương quốc Azura sở hữu một hệ thống hầm mỏ cổ xưa khổng lồ dưới lòng đất. Hệ thống này bao gồm ~N~ hang động lớn, được đánh số từ ~1~ đến ~N~. Để di chuyển giữa các hang động, người xưa đã đào các đường hầm nối chúng lại với nhau sao cho từ một hang động bất kỳ có thể đi đến mọi hang động khác (cấu trúc dạng cây).

Tại mỗi hang động đều tồn tại một Tinh thể Pha lê mang nguồn năng lượng magi: Hang động thứ ~i~ chứa tinh thể có mức năng lượng là ~W_i~.

Nhà thám hiểm Luna đang thực hiện các chuyến khảo sát trong hầm mỏ. Cô ấy sẽ di chuyển từ hang động ~u~ đến hang động ~v~ theo con đường duy nhất nối giữa chúng. Để hiệu chỉnh thiết bị bảo hộ, Luna cần biết: Trong tất cả các tinh thể cô ấy gặp trên đường đi (tính cả ở ~u~ và ~v~), tinh thể có mức năng lượng yếu thứ ~k~ là bao nhiêu?

Hãy giúp Luna trả lời các câu hỏi này để cô ấy hoàn thành chuyến thám hiểm an toàn!

Dữ liệu vào (Input)

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~M~ (~N, M \le 100000~).
• Dòng thứ hai chứa ~N~ số nguyên. Số thứ ~i~ biểu thị mức năng lượng của tinh thể tại hang động ~i~.
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~, mô tả một đường hầm nối giữa hang ~u~ và hang ~v~.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u, v, k~, mô tả một truy vấn tìm mức năng lượng nhỏ thứ ~k~ trên đường đi từ ~u~ đến ~v~.

Dữ liệu ra (Output)

• Với mỗi truy vấn, in ra kết quả tìm được trên một dòng riêng biệt.

Ví dụ

Input:

8 5
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5 1
2 5 2
2 5 3
2 5 4
7 8 2

Output:

2
8
9
105
7

Tại vương quốc Algorithmia, Đại pháp sư Sim sở hữu một bộ sưu tập cổ vật ma thuật vô giá gồm ~N~ viên đá Rune, được xếp thành một hàng dài trên kệ bảo tàng. Mỗi viên đá Rune mang trong mình một nguồn năng lượng cụ thể, được đại diện bởi một số nguyên ~A_i~.

Tuy nhiên, những viên đá này rất khó tính. Nếu đặt bừa bãi chúng vào cùng một chiếc rương, năng lượng xung đột sẽ gây ra vụ nổ lớn. Theo nghiên cứu cổ xưa, hai viên đá mang năng lượng ~x~ và ~y~ chỉ có thể nằm chung một rương an toàn nếu và chỉ khi tích năng lượng của chúng (~x \times y~) tạo ra một "Cộng hưởng Hoàn hảo" (tức là kết quả phải là một số chính phương).

Đức Vua thường xuyên gửi các đoàn sứ giả đến mượn một dãy các viên đá liên tiếp từ vị trí ~l~ đến ~r~ để trưng bày. Để tiết kiệm ngân khố hoàng gia, Đại pháp sư Sim cần tìm cách chia các viên đá trong đoạn ~[l, r]~ vào ít rương chứa nhất có thể, sao cho trong mỗi rương, bất kỳ cặp đá nào cũng tạo ra "Cộng hưởng Hoàn hảo".

Nhiệm vụ của bạn là lập trình giúp Đại pháp sư Sim trả lời nhanh các yêu cầu của Đức Vua.

Yêu cầu

Với mỗi truy vấn từ ~l~ đến ~r~, hãy tìm số lượng rương ~k~ ít nhất cần sử dụng để chứa hết các viên đá thuộc đoạn này, tuân thủ quy tắc an toàn đã nêu.

Dữ liệu (Input)

• Dòng đầu tiên: Ghi hai số nguyên dương ~N~, ~Q~ (~N \le 300,000~, ~Q \le 50,000~) - tương ứng với độ dài dãy số đá Rune và số lượng truy vấn.
• Dòng tiếp theo: Gồm ~N~ số nguyên ~A_1, A_2, \dots, A_N~ (~|A_i| \le 10^7~) mô tả năng lượng của dãy đá.
• ~Q~ dòng tiếp theo: Dòng thứ ~i~ gồm hai số nguyên dương ~l_i, r_i~ (~1 \le l_i \le r_i \le N~) mô tả truy vấn thứ ~i~.

Kết quả (Output)

• Ghi ra ~Q~ dòng, mỗi dòng gồm một số nguyên là câu trả lời cho các truy vấn (số lượng rương tối thiểu).

Ví dụ

Input

8 3
3 12 9 2 4 8 1 7
6 8
1 2
3 7

Output

3
1
2

Bạn là một Kiến trúc sư thiết kế Dungeon, nhưng lại có tấm lòng vô cùng nhân hậu. Hiện tại, bạn có một hành lang dài gồm ~n~ ô gạch. Trên mỗi ô gạch đang đặt sẵn một chiếc bẫy với mức sát thương là ~a~. Tuy nhiên, bạn không hài lòng với cách sắp xếp các bẫy này vì nó có thể quá nguy hiểm cho Người hùng sắp ghé thăm.

Bạn quyết định nhờ trợ lý của mình là Slime sử dụng phép thuật để sắp xếp lại các bẫy sao cho "dễ thở" nhất. Cụ thể, Slime có thể thực hiện phép thuật nhiều lần tùy ý. Trong mỗi lần thi triển, cô ấy chọn một đoạn liên tiếp các ô gạch từ ~l~ đến ~r~ (~a_l, a_{l+1}, \dots, a_r~) và phép thuật sẽ tự động sắp xếp lại các bẫy trong đoạn này theo thứ tự mức sát thương tăng dần (từ nhỏ đến lớn).

Bạn biết trước lộ trình của Người hùng. Anh ta sẽ chỉ bước chân lên những ô gạch nhất định, được đánh dấu trong tập hợp ~S \subseteq \{1, 2, 3, \dots, n\}~. Mục tiêu của bạn là sau khi Slime thực hiện các thao tác sắp xếp, tổng mức sát thương của các bẫy tại những ô mà Người hùng dẫm lên (~\sum\limits_{i\in S} a_i~) phải là nhỏ nhất có thể.

Hãy tính xem tổng mức sát thương nhỏ nhất mà Người hùng phải chịu là bao nhiêu.

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

Dòng đầu tiên: Một số nguyên, biểu thị số lượng bộ dữ liệu ~T~.

Đối với mỗi bộ dữ liệu:

• Dòng thứ nhất: Một số nguyên, biểu thị ~n~.
• Dòng thứ hai: ~n~ số nguyên, biểu thị ~a_1, \dots, a_n~.
• Dòng thứ ba: Một chuỗi nhị phân độ dài ~n~ là ~b~, trong đó ~b_i=1~ khi và chỉ khi ~i \in S~ (tức là Người hùng sẽ dẫm lên ô này).

Định dạng đầu ra

Gồm ~T~ dòng, mỗi dòng in ra một số nguyên, lần lượt là đáp án cho từng bộ dữ liệu.

Ví dụ

Input

5
5
4 4 4 1 4
00000
5
5 3 3 5 5
11110
5
2 5 3 3 1
01010
5
1 3 4 5 1
10110
5
1 5 1 5 5
11010

Output

0
16
4
6
7

Giới hạn

• Đối với ~100\%~ dữ liệu: ~1\le T\le 2\times 10^5~, ~n\ge 1~, ~1\le\sum n\le 2\times 10^5~, ~1\le a_i\le 10^9~, ~b_i\in\{0,1\}~.
• ~Subtask\ 1 (20\%): T\le 100~, ~n\le 8~.
• ~Subtask\ 2 (10\%):~ Trong ~b~, các số ~1~ tạo thành một đoạn tiền tố (nằm liền nhau ở đầu).
• ~Subtask\ 3 (10\%):~ Trong ~b~, các số ~1~ tạo thành một đoạn hậu tố (nằm liền nhau ở cuối).
• ~Subtask\ 4 (30\%): \sum n^2\le 2.5\times 10^7~.
• ~Subtask\ 5 (30\%):~ Không có giới hạn đặc biệt nào thêm.