Bài tập

Trên một hòn đảo có \(N\) ngôi làng, mỗi làng ban đầu yêu thích một màu cà vạt khác nhau. Làng thứ \(i\) có \(s_i\) người. Giữa các làng có \(M\) con đường hai chiều nối trực tiếp một số cặp làng.

Theo thời gian, mỗi tuần một làng có thể thuyết phục một làng láng giềng đổi sang màu cà vạt của mình. Việc này chỉ xảy ra nếu tổng số người yêu thích màu cà vạt của làng đi thuyết phục nhiều hơn hoặc bằng tổng số người yêu thích màu của làng bị thuyết phục. Ban đầu, mỗi làng chỉ có dân trong làng mình ủng hộ màu cà vạt của chính họ.

Quá trình thuyết phục tiếp tục cho đến khi tất cả người dân trên đảo đều yêu thích cùng một màu cà vạt.

Bạn cần xác định: màu cà vạt ban đầu của những làng nào có thể trở thành màu cà vạt duy nhất cuối cùng của toàn đảo.

Input

• Dòng \(1\): chứa hai số nguyên \(N\) và \(M\) (\(1 \le N \le 200\,000\), \(0 \le M \le 200\,000\)) — số làng và số con đường.
• Dòng \(2\): chứa \(N\) số nguyên \(s_1, s_2, \dots, s_N\) (\(1 \le s_i \le 10^9\)) — dân số mỗi làng.
• Mỗi trong \(M\) dòng tiếp theo chứa hai số nguyên \(a\) và \(b\) (\(1 \le a, b \le N\), \(a \ne b\)) — mô tả một con đường nối làng \(a\) và \(b\).

Đảm bảo rằng toàn bộ các làng tạo thành một đồ thị liên thông.

Output

In ra một chuỗi nhị phân có \(N\) ký tự. Ký tự thứ \(i\) là 1 nếu màu cà vạt của làng \(i\) có thể trở thành màu cà vạt chung cuối cùng, ngược lại in 0.

Scoring

• Subtask 1 (15 điểm): \(N \le 2000\), \(M \le 2000\).
• Subtask 2 (15 điểm): \(s_1 \ge s_2 \ge \dots \ge s_N\), và đồ thị có dạng cây. Khi đặt gốc của cây là \(1\), với tổ tiên \(p\) của đỉnh \(u\) bất kỳ thì \(1 \le p < u \le n\).
• Subtask 3 (15 điểm): Các làng được nối nếu và chỉ nếu \(|a - b| = 1\).
• Subtask 4 (30 điểm): Có tối đa \(10\) giá trị dân số khác nhau.
• Subtask 5 (25 điểm): Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

1110

Explanation

Số đầu tiên được ghi là số \(1\) bởi vì làng \(1\) có thể là làng có màu kết thúc — ta có quá trình như sau: Làng \(1\) bắt đầu với việc thuyết phục làng \(2\) (lúc này số người yêu thích màu của các làng là \(2\) và \(2\)). Sau khi thuyết phục, số người yêu thích màu của làng \(1\) là \(4\). Tiếp theo thuyết phục làng \(3\) (hiện giờ số người yêu thích màu của các làng là \(4\) và \(4\)). Số người yêu thích màu \(1\) trở thành \(8\). Cứ như vậy thuyết phục thêm làng thứ \(4\).

BT đang chơi một trò chơi gọi là "Nền văn minh". Bạn hãy giúp BT chơi trò chơi đó.

Trò chơi có \(n\) thành phố và \(m\) con đường vô hướng. Các thành phố được đánh số từ \(1\) đến \(n\). Giữa hai thành phố bất kỳ hoặc có một đường đi duy nhất hoặc không có đường đi nào cả. Một đường đi là một dãy các thành phố khác nhau \(v_1, v_2, ..., v_k\) sao cho giữa hai thành phố liên tiếp \(v_i\) và \(v_{i+1}\) \((1 \leq i < k)\) có một con đường nối chúng. Chiều dài của đường đi này bằng \(k-1\).

Chúng ta nói rằng hai thành phố cùng một vùng khi và chỉ khi có đúng một đường đi kết nối hai thành phố này.

BT muốn trả lời hai loại truy vấn sau:

• "1 x": Tìm chiều dài đường đi dài nhất trong vùng chứa thành phố \(x\).
• "2 x y": Kiểm tra xem thành phố \(x\) và thành phố \(y\) có cùng một vùng hay không. Nếu không, BT cần phải hợp nhất hai vùng như sau: chọn một thành phố trong vùng thứ nhất và một thành phố trong vùng thứ hai, nối chúng bằng một con đường sao cho chiều dài của đường đi dài nhất trong vùng hợp nhất là nhỏ nhất có thể. Nếu có nhiều cách làm như vậy, bạn được phép chọn một cách bất kỳ.

Bạn hãy giúp BT trả lời các câu hỏi loại 1 và thực hiện các yêu cầu loại 2.

Input

• Dòng đầu tiên chứa ba số nguyên \(n, m, q\) \((1 \leq n \leq 3 \times 10^5; 0 \leq m \leq n; 1 \leq q \leq 3 \times 10^5)\) --- số thành phố, số con đường ban đầu và số truy vấn.
• Mỗi trong số \(m\) dòng tiếp theo chứa hai số nguyên \(a_i\) và \(b_i\) \((1 \leq a_i, b_i \leq n, a_i \neq b_i)\) --- mô tả một con đường nối hai thành phố \(a_i\) và \(b_i\). Có thể có nhiều nhất một con đường nối hai thành phố.

• Mỗi trong số \(q\) dòng tiếp theo chứa một truy vấn thuộc một trong hai dạng:

• "1 x": Xác định chiều dài của đường đi dài nhất trong vùng chứa thành phố \(x\) \((1 \leq x \leq n)\). Dữ liệu đảm bảo luôn có ít nhất một truy vấn dạng này.

• "2 x y": Hợp nhất vùng của thành phố \(x\) và vùng của thành phố \(y\) \((1 \leq x, y \leq n, x \neq y)\).

Output

Với mỗi câu hỏi dạng thứ nhất, in ra kết quả trên một dòng.

Example

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

3
0
4

Một ngày hè nóng nực, hai người bạn nhỏ Hưng và Minh ghé vào một cửa hàng bán \(n\) loại kem khác nhau, với loại kem thứ \(i\) có giá \(c_i\).

Họ muốn mua \(m\) cây kem. Minh đề xuất một cách chia tiền như sau:

Nếu cây kem có giá nhỏ hơn \(k\), Hưng sẽ trả toàn bộ số tiền.

Ngược lại, Hưng chỉ trả \(k\) đồng, phần còn lại (tức là \(c_i - k\)) sẽ do Minh trả.

Gọi \(l\) là tổng tiền Hưng phải trả, và \(f\) là tổng tiền Minh phải trả. Hưng cảm thấy cách chia tiền này không công bằng nên muốn chọn ra \(m\) cây kem sao cho biểu thức \(l - f\) nhỏ nhất có thể.

Bạn được yêu cầu tính giá trị nhỏ nhất của \(l - f\) cho mỗi trong \(q\) truy vấn, mỗi truy vấn cung cấp một giá trị \(k\) và \(m\).

Input

\begin itemize

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) --- số lượng cây kem và số truy vấn.

• Dòng thứ hai chứa \(n\) số nguyên \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^9\)) --- giá của từng loại kem.

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(k_i\) và \(m_i\) (\(1 \le k_i \le 10^9\), \(1 \le m_i \le n\)) --- truy vấn thứ \(i\).

Output

Gồm \(q\) dòng, mỗi dòng ghi giá trị nhỏ nhất của biểu thức \(l - f\) tương ứng với truy vấn thứ \(i\).

Example

5 2
1 9 22 10 19
18 4
5 2

34
-21

7 4
1 5 4 3 7 11 9
5 4
5 7
7 3
4 5

4
16
7
1

Scoring

• Subtask 1 (30 điểm): \(n, q \le 1000\), \(c_i, k_i \le 10^6\).
• Subtask 2 (30 điểm): \(k_1 = k_2 = \dots = k_n\).
• Subtask 3 (40 điểm): Không có ràng buộc bổ sung.

Một vương quốc cổ đại được xây dựng trên những cây cầu. Cây cầu chính là xương sống của mọi kết nối trong vùng đất này, nối liền các thành phố cổ xưa lại với nhau qua những con đường cây xanh mát. Mỗi cây cầu đóng một vai trò thiết yếu trong việc duy trì sự cân bằng và bền vững của hệ thống giao thông của vương quốc.

Bạn được giao nhiệm vụ giải quyết một vấn đề liên quan đến cây cầu. Vương quốc có một cây bao gồm \(N\) đỉnh, tức là một đồ thị không có chu trình và nối liền tất cả các đỉnh. Cây này có \(M\) truy vấn, và mỗi truy vấn yêu cầu kiểm tra một loạt các cạnh mới có thể được thêm vào cây ban đầu. Nhiệm vụ của bạn là trả lời xem với mỗi truy vấn, nếu thêm các cạnh này vào cây, có bao nhiêu cạnh trong đồ thị mới sẽ trở thành cầu?

Một cạnh được gọi là cầu nếu khi loại bỏ nó, đồ thị trở nên không liên thông.

Hãy lưu ý rằng các truy vấn đều độc lập với nhau, và các cạnh thêm vào chỉ mang tính giả định, không thực sự thêm vào cây.

Input

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) (\(2 \leq N \leq 100\,000\), \(1 \leq M \leq 100\,000\)) --- số lượng đỉnh của cây và số lượng truy vấn.

Dòng thứ hai chứa \(N-1\) số nguyên \(p_2, p_3, \ldots, p_N\) mô tả cấu trúc của cây. Cụ thể, cạnh thứ \(i\) nối đỉnh \(i+1\) với đỉnh \(p_i\).

Tiếp theo là \(M\) dòng, mỗi dòng chứa một truy vấn. Truy vấn thứ \(i\) bao gồm số nguyên đầu tiên \(K_i\) --- số cạnh sẽ thêm vào cây, tiếp theo là \(K_i\) cặp số nguyên \((x_{i,1}, y_{i,1}), (x_{i,2}, y_{i,2}), \dots, (x_{i,K_i}, y_{i,K_i})\). Mỗi cặp \((x_{i,j}, y_{i,j})\) mô tả một cạnh mới được thêm vào cây (\(1 \leq x_{i,j}, y_{i,j} \leq N\)). Tổng của \(K_i\) trong tất cả các truy vấn không vượt quá \(100\,000\).

Output

Với mỗi truy vấn, in ra một số nguyên duy nhất là số lượng cầu trong đồ thị sau khi thêm các cạnh của truy vấn vào cây.

Example

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

4
0
2
6
5
2
4
3

Scoring

• Subtask 1 (30% số điểm): \(N, M \leq 1000\).
• Subtask 2 (70% số điểm): không giới hạn gì thêm.