Chào mừng bạn đến với chương F - chương của kĩ thuật đọc mood người thương. Trong phần này, pháp sư tu luyện gần 1000 năm (cụ thể là 3 ngày) trên núi Cơn Đô - ông P. giấu tên, sẽ cho bạn cái nhìn tổng quan về mood của con gái.

Mood của con gái thực chất phân hoá như một cây vậy, với gốc là sự bình thường, từ sự bình thường đó chuyển thành các mood khác nhau ví dụ như chán nản hay vui vẻ, rồi từ chán nản hay vui vẻ đó chuyển thành các mood khác như đói bụng, buồn ngủ,...

Chúng ta mã hoá $n$ mood của con gái thành số thứ tự từ $1$ đến $n$ với $1$ là sự bình thường và từ $2$ đến $n$ là các mood khác nhau.

Với mỗi mood $i$, ta nhận định nó là tích cực hay tiêu cực dựa vào tiêu chí $a_i$, nếu $a_i=1$ thì có nghĩa đó là một trạng thái tích cực và ngược lại nếu $a_i=-1$ thì đó là một trạng thái tiêu cực.

Bạn nhờ vào kĩ năng của P. đã biết được cây mood của crush như thế nào, bây giờ, P. sẽ cho bạn $tq$ khối câu hỏi (bạn cần thực hành nhiểu để thành thục nên P. cho bạn nhiều câu hỏi như vậy) như sau:

• Với mỗi câu hỏi, bạn sẽ có quyền nhờ P. làm nhiều nhất một thao tác (có thể không nếu bạn thấy P. quá vô dụng) như sau trên cây mood của crush bạn:

  • Chọn một đỉnh rồi chuyển giá trị $a_i$ của đỉnh đó thành $-a_i$.

• Sau đó, bạn sẽ được P. cho $q$ truy vấn với truy vấn thứ $i$ sẽ đưa ra $v_i$ yêu cầu bạn phải in ra tổng các $a_i$ trong cây con gốc $v_i$.

Với mỗi câu hỏi yêu cầu bạn cần nhờ P. (hoặc không) thay đổi một đỉnh nào đấy sao cho tổng các đáp án trong $q$ truy vấn là lớn nhất có thể, nếu có nhiều đáp án thay đổi đỉnh tối ưu, hãy đưa ra cách thay đổi đỉnh có số thứ tự nhỏ nhất (lưu ý rằng $-1$ là số thứ tự nhỏ nhất có thể) và kết quả của các truy vấn trong trường hợp thay đổi đó.

Input

• Dòng đầu tiên gồm hai số $n$ và $tq$ lần lượt là số lượng đỉnh trên cây mood của crush bạn và số lượng câu hỏi P. đưa ra. $(1\le n,tq\le {2.10}^5)$
• Dòng thứ hai là $n$ số nguyên $a_i$ với $a_i$ là trạng thái tiêu cực hay tích cực của mood thứ $i$, lưu ý rằng P. có thể cho rằng sự bình thường cũng là một tiêu cực hoặc tích cực. $(|a_i|=1,1\le i\le n)$
• $n-1$ dòng tiếp theo mỗi dòng thứ $j(j>2)$ chứa hai số nguyên $u_{j-2}$ và $v_{j-2}$ - có một cạnh nối giữa hai đỉnh này trên cây mood của crush. Dữ liệu sẽ đảm bảo các cạnh tạo thành một cây có $n$ đỉnh.
• Tiếp theo gồm $tq$ block câu hỏi có dạng:
  • Dòng đầu tiên gồm số nguyên $q$ - số lượng truy vấn trong câu hỏi này.
  • Dòng tiếp theo chứa $q$ số nguyên $p_j(1\le j\le q)$ yêu cầu tính tổng các giá trị tích cực tiêu cực trong cây con gốc $p_j$.
• Dữ liệu đảm bảo tổng các $q$ trong $tq$ câu hỏi không vượt quá ${2.10}^5$. Lưu ý rằng các câu hỏi là độc lập với nhau (có nghĩa rằng các truy vấn trong câu hỏi trước không liên quan tới câu hỏi sau).

Output

• Gồm $tq$ block câu trả lời cho $tq$ câu hỏi có dạng:
  • Dòng đầu tiên gồm đỉnh bạn chọn để thay đổi, nếu không có thay đổi in ra $-1$.
  • Dòng tiếp theo là $q$ số nguyên là câu trả lời cho $q$ truy vấn của câu hỏi đó.

Subtasks

• Subtask 1: Đảm bảo $n\le 16,tq\le 3$. (30 điểm)
• Subtask 2: Đảm bảo $n,tq\le 1000$. (50 điểm)
• Subtask 3: Đảm bảo tổng của các giá trị $q$ trong $tq$ câu hỏi không quá $1000$. (50 điểm)
• Subtask 4: Không có ràng buộc gì thêm. (220 điểm)

Examples

4 1
-1 -1 -1 -1
1 2
2 3
2 4
2 
1 4

4
-2 1

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

-1
1 3 
1
5 1 3

10 1
1 1 -1 1 1 -1 1 -1 1 -1
1 2
1 3
3 4
1 5
3 6
3 7
5 8
6 9
2 10
9
9 8 2 2 3 8 7 9 4

8
1 1 0 0 1 1 1 1 1