Vẫn là bốc đại bài thoi

Trong buổi sinh hoạt đầu năm, cô giáo chủ nhiệm giao cho Công Đức chụp lại một số tấm ảnh kỷ niệm cho lớp ITK19. Công Đức yêu cầu tất cả \(N\) bạn học sinh trong lớp (không tính cậu ấy) xếp thành một hàng và đánh số các bạn từ \(1\) đến \(N\) từ đầu hàng đến cuối hàng. Sau đó, cậu ấy chụp tổng cộng \(M\) tấm ảnh, tấm ảnh thứ \(i\) ghi lại hình ảnh một đoạn con từ học sinh \(a_i\) đến học sinh \(b_i\).

Sau khi quan sát \(M\) tấm ảnh được chụp, cô giáo nhận ra một hiện tượng: trong mỗi tấm ảnh có đúng một học sinh không mặc đồng phục! Vì số ảnh quá lớn nên cô rất ngại rà soát ngược lại từng tấm để điểm tên những học sinh này. Cô liền nhờ Đức lập trình xác định số lượng tối đa các bạn học sinh trong lớp không mặc đồng phục (không tính Đức) theo ràng buộc trên. Các bạn hãy giúp Đức nhé!

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M (1 \le/q N \leq 2 \times 10^5, 1 \leq M \leq 10^5)\).

• Dòng thứ \(i\) trong \(M\) dòng sau chứa hai số nguyên dương \(a_i\) và \(b_i\).

Ouput

• Một số nguyên là số lượng lớn nhất có thể các học sinh không mặc đồng phục. Nếu không tìm được nghiệm thoả mãn thì in ra \(−1\).

Example

5 3
1 4
2 5
3 4 

1

Định nghĩa:

• Hàm \(f(n)\) = \(1|2 + 2|3 + ... (n-1)|n + n|(n+1)\). Trong đó | là phép toán \(Or\).

Yêu cầu: Tính hàm \(f(n)\), với \(n\) được nhập từ bàn phím.

Input

• Dòng đầu ghi \(q\) không quá \(100\) - số câu hỏi.
• \(q\) dòng tiếp theo, mỗi dòng ghi số nguyên dương \(n\) không quá \(10^6\).

Output

• Ứng với mỗi câu hỏi, in ra kết quả tương ứng.

Example

3
3
2
1

13
6
3

Cho một dãy gồm \(n\) phần tử số nguyên không âm \(a_1,a_2,...,a_n\). Nhiệm vụ của bạn là hãy chọn một dãy con gồm các phần tử liên tiếp sao cho khi thực hiện phép XOR tất cả phần tử của dãy đó thì ta thu được giá trị lớn nhất và in ra giá trị đó ra màn hình.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) \((1\le n \le 100)\).
• Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1,a_2,...,a_n\) và các giá trị \(a_i\) không vượt quá \(2^{30}\)

Output

• In ra giá trị lớn nhất cần tìm.

Example

3
1 2 1 

3

Vào dịp Giáng Sinh, Phúc quyết định đi làm thêm để giao quà cho các em nhỏ. Vì phải giao hàng bằng xe đạp, Phúc chỉ có thể mang tối đa một món quà mỗi lần. Do đó, cậu phải liên tục di chuyển từ điểm tập kết quà đến các vị trí giao quà khác nhau.

Hãy tưởng tượng thành phố nơi Phúc sống được mô phỏng như một lưới tọa độ 2D. Có \(N\) món quà cần được giao, mỗi món nằm tại tọa độ nguyên \((x, y)\) trên lưới. Ngoài ra, điểm tập kết - nơi Phúc cất giữ các món quà trước khi giao - cũng nằm tại một tọa độ cụ thể trên lưới. Lưu ý, điểm tập kết và vị trí giao hàng có thể trùng nhau.

Phúc bắt đầu hành trình từ điểm tập kết. Mỗi giây, cậu có thể di chuyển một ô theo hướng lên, xuống, trái hoặc phải. Khi đến một vị trí giao quà, Phúc sẽ giao món quà ngay lập tức, sau đó phải quay lại điểm tập kết để lấy món quà tiếp theo. Quá trình này lặp lại cho đến khi tất cả các món quà được giao xong.

Hiện tại, Phúc đang xem xét nhiều vị trí khác nhau để đặt điểm tập kết. Vì vậy, với mỗi vị trí tập kết được đề xuất, hãy tính thời gian tối thiểu cần thiết để Phúc giao hết tất cả món quà và trở về điểm tập kết, giả sử cậu làm việc nhanh nhất có thể.

Input

• Dòng 1: số nguyên dương \(N (1 \leq N \leq 10^5)\) - số lượng món quà
• \(N\) dòng tiếp theo: mỗi dòng chứa hai số nguyên \(x_i, y_i (1 \leq x_i, y_i \leq 10^5)\) - tọa độ điểm giao quà thứ \(i\)
• Dòng tiếp: số nguyên dương \(Q (1 \leq Q \leq 10^5)\) - số lượng truy vấn
• \(Q\) dòng cuối: mỗi dòng chứa hai số nguyên \(x_j, y_j (1 \leq x_j, y_j \leq 10^5)\) - tọa độ của một vị trí tập kết được xem xét

Output

• \(Q\) dòng: mỗi dòng là thời gian tối thiểu (tính bằng giây) để giao hết tất cả các món quà với vị trí tập kết tương ứng

Example

2
2 2
1 1
3
1 2
1 1
3 3

4
4
12