Lớp 10 Tin đang cần cử người đi thi khiêu vũ nhân ngày 20/10 sắp tới. Lớp chuyên tin có \(B\) bạn nam có chiều cao lần lượt là \(b_{1}, b_{2}, \ldots, b_{B}\) và \(G\) bạn nữ có chiều cao lần lượt là \(g_{1}, g_{2}, \ldots, g_{G}\). Theo quy định của cuộc thi, mỗi lớp phải cử \(K\) cặp đôi tham gia. Tất cả các bạn đều có kĩ thuật nhảy rất tốt nên thầy giáo muốn chọn ra \(K\) cặp đôi sao cho: cặp đôi có chệnh lệch chiều cao lớn nhất là nhỏ nhất có thể. Bạn hãy giúp thầy chọn ra \(K\) cặp đôi đó.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(B, G, K\) \((1 \leq B, G \leq 10^{6}, 1 \leq K \leq \min(B, G))\) là số bạn nam, số bạn nữ và số cặp đôi phải chọn.
• Dòng thứ hai chứa \(B\) số nguyên dương \(b_{1}, b_{2}, \ldots, b_{B}\) là chiều cao của \(B\) bạn nam \((1 \leq b_{i} \leq 10^{9})\).
• Dòng thứ ba chứa \(G\) số nguyên dương \(g_{1}, g_{2}, \ldots, g_{G}\) là chiều cao của \(G\) bạn nữ \((1 \leq g_{i} \leq 10^{9})\).

Output

• In ra một số nguyên duy nhất là chênh lệch nhỏ nhất tìm được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq \max(B, G) \leq 10\).
• Subtask \(2\) (\(15\%\) số điểm): \(1 \leq \max(B, G) \leq 100\).
• Subtask \(3\) (\(15\%\) số điểm): \(1 \leq \max(B, G) \leq 1000\).
• Subtask \(4\) (\(15\%\) số điểm): \(k = 1\).
• Subtask \(5\) (\(10\%\) số điểm): \(k = \min(B, G)\).
• Subtask \(6\) (\(25\%\) số điểm): không có ràng buộc nào thêm.

Example

4 3 2
165 170 180 180
164 165 172

2

Bạn được cho một mảng \(a\) gồm \(n\) số nguyên dương, đánh số từ \(1\) đến \(n\). Hãy gọi một mảng là đầy đủ nếu với mọi cặp giá trị \(x\) và \(y\) trong mảng (biết \(x\) và \(y\) không nhất thiết phải khác nhau), với điều kiện \(x \geq y\), thì số \(\left \lfloor \frac{x}{y} \right \rfloor\) (lấy \(x\) chia cho \(y\) rồi làm tròn xuống) cũng phải nằm trong mảng.

Bạn được đảm bảo rằng tất cả các số trong mảng \(a\) đều không vượt quá \(c\). Nhiệm vụ của bạn là kiểm tra xem mảng này có phải là đầy đủ hay không.

Bạn sẽ phải trả lời nhiều truy vấn.

Input

• Dòng đầu tiên gồm một số nguyên dương \(t\) \((1 \le t \le 10^4)\) là số truy vấn, mỗi truy vấn sẽ có dạng như sau:
  • Dòng đầu chứa hai số nguyên dương \(n,c\) mô tả dãy \(a\) ban đầu và cận trên của các giá trị \(a_i\) trong dãy \((1 \le n \le 2 \times 10^5, 1 \le C \le 10^7)\).
  • Dòng thứ hai chứa \(n\) số nguyên dương \(a_1,a_2,...,a_n\) \((1 \le a_i \le c)\).
• Gọi \(N\) là tổng \(n\) của các truy vấn, tương tự \(C\) là tổng \(c\) của các truy vấn, dữ liệu đảm bảo \(N \le 10^6\) và \(C \le 10^7\).

Output

• Với mỗi truy vấn, in ra Yes nếu dãy đó là dãy đầy đủ, ngược lại in ra No.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(N \le 100, C \le 10^7\)
• Subtask \(2\) (\(20\%\) số điểm): \(N \le 10^5, C \le 10^4\)
• Subtask \(3\) (\(20\%\) số điểm): \(N \le 1000\)
• Subtask \(4\) (\(30\%\) số điểm): \(N \le 10^5\)
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm

Example

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

Yes
No
No

HNAms là một quốc gia rộng lớn với mạng lưới hàng không phát triển. Tổng cộng, có \(n\) thành phố trong nước được phục vụ bởi hãng hàng không \(BBQ\). Hãng này vận hành các chuyến bay hai chiều giữa \(m\) cặp thành phố, chuyến bay thứ \(i\) nối các thành phố có số thứ tự \(a_i\) và \(b_i\) và có giá vé \(c_i\) cho cả hai chiều.

Người ta biết rằng các chuyến bay của \(BBQ\) có thể được sử dụng để di chuyển đối với bất kì cặp thành phố nào (có thể qua các thành phố trung gian), và chi phí của bất kỳ hành trình nào bao gồm nhiều chuyến bay liên tiếp sẽ bằng chi phí của chuyến bay đắt nhất trong hành trình đó. Cụ thể hơn, chi phí của hành trình từ thành phố \(t_1\) đến thành phố \(t_k\) với \(k - 2\) điểm dừng ở các thành phố \(t_2, t_3, t_4, ..., t_{k-1}\) bằng chi phí cao nhất trong số các chuyến bay từ \(t_1\) đến \(t_2\), từ \(t_2\) đến \(t_3\), từ \(t_3\) đến \(t_4\), và cứ thế đến chuyến bay từ \(t_{k-1}\) đến \(t_k\).

Một hãng hàng không mới, \(HHC\), gần đây đã bắt đầu hoạt động tại \(HNAms\). Hãng này cung cấp các chuyến bay hai chiều giữa tất cả các cặp thành phố không được kết nối trực tiếp bởi các chuyến bay của \(BBQ\). Vì vậy, giữa mỗi cặp thành phố chỉ có một chuyến bay của \(BBQ\) hoặc \(HHC\).

Chi phí các chuyến bay của \(HHC\) được tính như sau: đối với mỗi cặp thành phố \(x\) và \(y\) được kết nối trực tiếp bởi chuyến bay của \(HHC\), chi phí chuyến bay này bằng chi phí tối thiểu của hành trình giữa hai thành phố \(x\) và \(y\) bằng các chuyến bay của \(BBQ\) theo quy tắc định giá đã mô tả trước đó.

Người ta biết rằng với các chuyến bay của \(HHC\), bạn có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác (có thể qua các điểm dừng), và tương tự như \(BBQ\), chi phí của hành trình giữa hai thành phố bằng các chuyến bay của \(HHC\) sẽ bằng chi phí của chuyến bay đắt nhất.

Do sự cạnh tranh ngày càng gia tăng với \(HHC\), \(BBQ\) quyết định thực hiện một cuộc cải cách và thay đổi giá vé cho các chuyến bay của mình. Cụ thể, đối với chuyến bay thứ \(i\) giữa các thành phố \(a_i\) và \(b_i\), \(BBQ\) muốn điều chỉnh giá vé bằng với chi phí tối thiểu của hành trình giữa các thành phố \(a_i\) và \(b_i\) qua các chuyến bay của \(HHC\). Hãy giúp các nhà quản lý của \(BBQ\) tính toán giá vé mới cho các chuyến bay này.

Input

• Ở dòng thứ nhất, bạn sẽ nhận được hai số nguyên dương \(t\) và \(subtask\) \((1 \le t \le 10^4; 1 \le subtask \le 8)\) miêu tả số test cases và số hiệu subtask của test này, mỗi test case sẽ có dạng như sau:
• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) \((4 ≤ n ≤ 200.000, n - 1 ≤ m ≤ 200.000, m ≤ \frac{(n-1)\times(n-2)}{2})\) - số lượng thành phố ở Berland và số lượng các chuyến bay của \(BBQ\).
• Tiếp theo là \(m\) dòng mô tả các chuyến bay của \(BBQ\). Dòng thứ \(i\) chứa ba số nguyên \(a_i, b_i\) và \(c_i\) \((1 ≤ a_i, b_i ≤ n, 1 ≤ c_i ≤ 10^9)\) - số thứ tự của các thành phố được kết nối bởi chuyến bay thứ \(i\) của \(BBQ\) và giá vé của chuyến bay thứ \(i\).

• Đảm bảo rằng không có chuyến bay nào kết nối một thành phố với chính nó, không có \(2\) chuyến bay nào kết nối cùng một cặp thành phố. Đảm bảo rằng bằng cách sử dụng các chuyến bay của \(BBQ\), có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác, và bằng cách sử dụng các chuyến bay của \(HHC\), cũng có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác.

• Gọi \(N\) là tổng số của \(n\) qua tất cả các trường hợp thử nghiệm và \(M\) là tổng số của \(m\) qua tất cả các trường hợp thử nghiệm. Đảm bảo rằng \(N, M ≤ 200.000\).

Output

• Đối với mỗi trường hợp thử nghiệm, bạn cần in ra \(m\) số nguyên trên một dòng, trong đó số thứ \(i\) là giá vé của chuyến bay \(BBQ\) thứ \(i\) sau khi cải cách hàng không.

Scoring

• Subtask \(1\) (\(10\%\) số điểm): \(n \le 10, N \le 10^4\)
• Subtask \(2\) (\(10\%\) số điểm): \(n \le 100, N \le 10^4\)
• Subtask \(3\) (\(10\%\) số điểm): \(n \le 1000, N \le 10^4, c_i \le 2\)
• Subtask \(4\) (\(15\%\) số điểm): \(n \le 1000, N \le 10^4,\)
• Subtask \(5\) (\(15\%\) số điểm): Ở mọi test case: \(m = n - 1\)
• Subtask \(6\) (\(15\%\) số điểm): \(c_i \le 2\)
• Subtask \(7\) (\(15\%\) số điểm): \(c_i \le 10\)
• Subtask \(8\) (\(10\%\) số điểm): Không có ràng buộc gì thêm

Example

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

3 3 3
1 1 1 2 2

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

4 4 5 3 4 4