Cho \(n+1\) hình chữ nhật trên mặt phẳng \(Oxy\), các hình chữ nhật đều có các cạnh song song hoặc vuông góc với trục tọa độ. Hãy tìm điểm (\(x,y\)) nằm trong ít nhất \(n\) hình chữ nhật đã cho. Điểm (\(x,y\)) được gọi là nằm trong hình chữ nhật xác định bởi hai điểm (\(x_1,y_1\)) và (\(x_2,y_2\)) nếu:

• \(min(x_1,x_2) \le x \le max(x_1,x_2)\).
• \(min(y_1,y_2) \le y \le max(y_1,y_2)\).

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 2 \times 10^5\)).
• \(n+1\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1,y_1,x_2,y_2\) (\(0 \le x_1,x_2,y_1,y_2 \le 10^9\)) mô tả hai điểm (\(x_1,y_1\)) và (\(x_2,y_2\)) là hai góc của hình chữ nhật, dữ liệu đảm bảo hai điểm này là phân biệt.

Output

• Hai số nguyên \(x,y\) là tọa độ của điểm nằm trong ít nhất \(n\) hình chữ nhật, nếu có nhiều điểm thỏa mãn có cùng \(x\) nhỏ nhất thì đưa ra điểm có \(y\) nhỏ nhất. Nếu không có điểm nào thỏa mãn chỉ ghi -1.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(x_1,x_2,y_1,y_2 \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(x_1,x_2,y_1,y_2 \le 2000\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 2000\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

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

2 1

Alice và Bob cùng chơi một trò chơi trên dãy số nguyên. Alice muốn nhanh chóng tìm được một đoạn gồm các phần tử liên tiếp mà khi tính AND (\(\&\)) của các phần tử đó bằng \(0\). Bob thì tìm cách thay đổi các số làm khó Alice. Cụ thể, Bob muốn nhờ bạn lập trình giải các bài toán sau:

Cho số nguyên \(k\) (\(1 \le k \le n\)) và hai dãy số \(a\) và \(c\) có cùng độ dài \(n\). Với mỗi vị trí \(i\) (\(1 \le i \le n\)) ta có thể thay đổi \(a_i\) thành giá trị bất kì với chi phí là \(c_i\). Tìm tổng chi phí nhỏ nhất để thay đổi dãy \(a\) sao cho \(a_i\) \(\&\) \(a_{i+1}\) \(\&\) \(...\) \(\&\) \(a_{i+k-1} = 0\) với mọi \(1 \le i \le n-k+1\).

Nhắc lại, phép toán AND (có kí hiệu là \(\&\)) được định nghĩa như sau: Kết quả của phép toán AND giữa hai số nguyên không âm \(x\) và \(y\) là một số nguyên không âm \(z\) trong đó bit thứ \(i\) trong biểu diễn nhị phân của \(z\) sẽ là \(1\) khi vào chỉ khi bit thứ \(i\) trong biểu diễn nhị phân của \(x\) và \(y\) đồng thời bằng \(1\), ngược lại bit thứ \(i\) trong biểu diễn nhị phân của \(z\) sẽ là \(0\).

Input

• Dòng đầu tiên là một số nguyên \(t\) (\(1 \le t \le 10^6\)) là số bộ dữ liệu, tiếp theo mỗi bộ có dạng:
  • Dòng đầu tiên gồm hai số nguyên \(n\) và \(k\) (\(1 \le k \le n \le 10^6\)).
  • Dòng thứ hai gồm \(n\) số nguyên \(a_1,a_2,...,a_n\) (\(0 \le a_i < 2^{30}\)).
  • Dòng cuối cùng gồm \(n\) số nguyên \(c_1,c_2,...,c_n\) (\(0 \le c_i < 2^{30}\)).

Output

• Gồm \(t\) dòng, mỗi dòng tương ứng là tổng chi phí nhỏ nhất tìm được của bộ dữ liệu xuất hiện trong dữ liệu vào.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Tổng các giá trị của \(n\) trong \(t\) bộ dữ liệu không vượt quá \(20\).
• Subtask \(2\) (\(20\%\) số điểm): \(c_i \le 1\) với mọi \(1 \le i \le n\).
• Subtask \(3\) (\(30\%\) số điểm): Tổng các giá trị của \(n\) trong \(t\) bộ dữ liệu không vượt quá \(5000\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

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

4

Cho một cây gồm \(n\) đỉnh với đỉnh \(1\) làm gốc. Mỗi \(1 \le i \ne n\) có một số nguyên \(c_i\) gọi là màu của đỉnh \(i\). Bạn cần xử lí \(q\) truy vấn thuộc một trong hai dạng sau:

• \(1\) \(u\) \(x\): Thay đổi màu của đỉnh \(u\) thành \(x\), nghĩa là \(c_u = x\).
• \(2\) \(k\) \(u_1\) \(u_2\) \(...\) \(u_k\): Xét tập hợp gồm màu của các đỉnh nằm trong các cây con \(u_1,u_2,...,u_k\) (các đỉnh xuất hiện nhiều lần được tính nhiều lần). Gọi số lượng phần tử của tập là \(S\), tìm màu vượt trội trong tập này, cụ thể là màu xuất hiện nhiều hơn \(\frac{S}{2}\) lần.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(q\) (\(1 \le n,q \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(c_1,c_2,...,c_n\) (\(1 \le c_i \le n\)).
• Mỗi dòng trong \(n-1\) dòng tiếp theo gồm hai số nguyên \(u\) và \(v\) (\(1 \le u,v \le n\)) thể hiện có cạnh nối giữa \(u\) và \(v\) trên cây.
• Mỗi dòng trong \(q\) dòng tiếp theo là một truy vấn thuộc một trong hai dạng đã mô tả. Dữ liệu đảm bảo tổng các giá trị \(k\) của các truy vấn loại \(2\) không vượt quá \(10^6\).

Output

• Đối với mỗi truy vấn loại \(2\), ghi ra màu vượt trội hoặc -1 nếu không tồn tại.

Scoring

Gọi \(S_k\) là tổng \(k\) qua các truy vấn loại \(2\).

• Subtask \(1\) (\(10\%\) số điểm): \(n,S_k \le 500\), \(c_i \le 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(n,S_k \le 5000\), \(c_i \le 10\).
• Subtask \(3\) (\(20\%\) số điểm): \(n,S_k \le 10^5\), \(c_i \le 10\).
• Subtask \(4\) (\(20\%\) số điểm): \(n,S_k \le 10^5\).
• Subtask \(5\) (\(20\%\) số điểm): không có truy vấn loại \(1\).
• Subtask \(6\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

-1
2