Một lớp học có ~n~ học sinh.

Một số học sinh đã tham gia các kỳ thi olympiad:

• ~a~ học sinh tham gia olympiad toán,
• ~b~ học sinh tham gia olympiad tin học,
• ~c~ học sinh tham gia olympiad tiếng Nga.

Một học sinh có thể tham gia nhiều hơn một kỳ thi.

Hãy tìm số lượng nhỏ nhất và lớn nhất có thể của số học sinh không tham gia bất kỳ kỳ thi nào trong ba kỳ thi trên.

Dữ liệu vào

Dòng 1: số nguyên ~n~ -- số học sinh trong lớp (~1 \le n \le 2 \cdot 10^5~).

Dòng 2, 3, 4: lần lượt là các số nguyên ~a~, ~b~, ~c~ (~0 \le a, b, c \le n~).

Dữ liệu ra

Dòng 1: số lượng nhỏ nhất có thể của số học sinh không tham gia kỳ thi nào.

Dòng 2: số lượng lớn nhất có thể của số học sinh không tham gia kỳ thi nào.

Ví dụ

Có ~n~ tấm bưu thiếp, tấm thứ ~i~ là hình chữ nhật có chiều cao ~h_i~ và chiều rộng ~w_i~. Tất cả các tấm bưu thiếp sẽ được xếp chồng lên nhau và đặt vào một chiếc phong bì hình chữ nhật duy nhất có chiều cao ~H~ và chiều rộng ~W~.

Mỗi tấm bưu thiếp được đặt sao cho các cạnh của nó song song với các cạnh của phong bì. Được phép xoay bưu thiếp ~90^\circ~. Một tấm bưu thiếp vừa vào phong bì khi mỗi cạnh của bưu thiếp không vượt quá cạnh song song tương ứng của phong bì.

Hãy xác định chiều cao ~H~ và chiều rộng ~W~ của phong bì nhỏ nhất (theo diện tích ~H \cdot W~) có thể chứa tất cả ~n~ tấm bưu thiếp.

Dữ liệu vào

Dòng 1: số nguyên ~n~ (~1 \le n \le 10^5~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~h_i~ và ~w_i~ (~1 \le h_i, w_i \le 10^9~).

Dữ liệu ra

In hai số nguyên ~H~ và ~W~ -- chiều cao và chiều rộng của phong bì. Nếu ~H \ne W~, in cạnh nhỏ hơn trước.

Ví dụ

Cho mảng số nguyên ~a_1, a_2, \ldots, a_n~, trong đó ~0 \le a_i < 2^{30}~.

Số ~y~ được gọi là mặt nạ con của số ~x~ nếu ~y \mathbin{\&} x = y~, trong đó ~\&~ là phép AND theo bit. Nói cách khác, ~y~ có thể thu được từ ~x~ bằng cách thay một số bit ~1~ của ~x~ thành ~0~.

Hãy tìm một số nguyên ~x~ (~0 \le x < 2^{30}~) sao cho số lượng phần tử của mảng là mặt nạ con của ~x~ là số lẻ, hoặc thông báo rằng không tồn tại số ~x~ như vậy.

Nếu một giá trị xuất hiện nhiều lần trong mảng thì mỗi lần xuất hiện được đếm riêng.

Dữ liệu vào

Dòng 1: số nguyên ~t~ -- số bộ test (~1 \le t \le 10^4~).

Mỗi bộ test gồm:

• Dòng 1: số nguyên ~n~ (~1 \le n \le 10^5~).
• Dòng 2: ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i < 2^{30}~).

Tổng ~n~ trên tất cả các bộ test không vượt quá ~10^5~.

Dữ liệu ra

Với mỗi bộ test, in ~-1~ nếu không tồn tại ~x~ thỏa mãn. Ngược lại, in bất kỳ một giá trị ~x~ thỏa mãn.

Ví dụ

Có ~n~ bài hát trong hàng đợi của máy nghe nhạc, mỗi bài có tên và độ dài (tính bằng giây).

Máy phát bài hát đầu tiên trong hàng đợi và lập tức xóa nó khỏi hàng đợi. Đôi khi người dùng nhấn nút Phát tiếp theo -- bài hát mới được chèn vào đầu hàng đợi, nhưng bài đang phát vẫn tiếp tục đến khi kết thúc. Nếu sự kiện này xảy ra đúng vào thời điểm bài hiện tại vừa kết thúc, bài mới sẽ được phát ngay tiếp theo.

Hãy xác định thứ tự các bài hát được nghe và thời điểm bắt đầu phát mỗi bài.

Dữ liệu vào

Dòng 1: số nguyên ~n~ -- số bài hát ban đầu trong hàng đợi (~1 \le n \le 10^5~).

~n~ dòng tiếp theo, mỗi dòng chứa tên bài ~\text{name}_i~ và độ dài ~\text{len}_i~ (~1 \le \text{len}_i \le 10^9~).

Dòng tiếp theo: số nguyên ~m~ -- số sự kiện nhấn Phát tiếp theo (~0 \le m \le 10^5~).

~m~ dòng tiếp theo, mỗi dòng chứa ba giá trị ~t_j~, ~\text{name}_j~, ~\text{len}_j~ -- thời điểm xảy ra sự kiện (tính bằng giây), tên và độ dài bài hát được thêm vào (~0 \le t_j \le 10^9~, ~1 \le \text{len}_j \le 10^9~).

Các sự kiện được cho theo thứ tự không giảm của ~t_j~. Tên bài hát chỉ gồm các chữ cái Latin, độ dài tên không vượt quá ~20~.

Dữ liệu ra

Với mỗi bài hát được phát, in một dòng gồm tên bài ~\text{name}_k~ và thời điểm bắt đầu phát ~\text{start}_k~, theo đúng thứ tự phát.

Ví dụ