XOR lớn nhất trên đoạn · canuc80k6114

Cho dãy giá trị $c_{1}, \dots, c_{n}$ và $q$ đoạn $[l, r]$ . Với mỗi đoạn, chọn một tập con vị trí bất kỳ trong đoạn và lấy XOR các giá trị. Tập con được phép rỗng và khi đó XOR bằng $0$ . Hãy in XOR lớn nhất có thể.

Input

Dòng đầu chứa $n$ .
Dòng tiếp theo chứa $c_{1}, \dots, c_{n}$ .
Dòng tiếp theo chứa $q$ , rồi $q$ dòng chứa $l$ $r$ .

Output

In một XOR lớn nhất cho mỗi truy vấn.

Constraints

$1 \leq n, q \leq 5 \cdot 1 0^{5}$ .
$0 \leq c_{i} \leq 1 0^{6}$ .
$1 \leq l \leq r \leq n$ .

Scoring

Subtask $1$ ( $50%$ số điểm): $n, q \leq 18$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

7
14
4

Giải thích: Ba đoạn lần lượt sinh được các giá trị lớn nhất $7, 14$ và $4$ bằng cách chọn toàn bộ các bit độc lập phù hợp.

Mô hình: Cho dãy giá trị c_1..c_n và q đoạn [l,r]. Với mỗi đoạn, chọn một tập con vị trí bất kỳ trong đoạn và lấy XOR các giá trị. Tập con được phép rỗng và khi đó XOR bằng 0. Hãy in XOR lớn nhất có thể.
Thuật toán: Sắp xếp truy vấn theo r, quét dãy và chèn bằng latest-position basis 20 bit. Với truy vấn [l,r], đặt ans=0, duyệt pivot từ cao xuống; chỉ xét pivot có pos>=l, và XOR nếu làm ans tăng.
Thuật toán: Do invariant latest-position, các pivot được phép sinh đúng span đoạn. Greedy maximum giống bài 02.
Chứng minh đúng: Bài 14 đã chứng minh các pivot pos>=l sinh đúng span [l,r]. Trên cơ sở đó, quyết định greedy từ bit cao xuống cho phần tử lớn nhất của span. Vì vậy câu trả lời cho mỗi đoạn là maximum subset XOR chính xác.
Độ phức tạp: O((n+q)*20 + q log q) thời gian, O(n+q) bộ nhớ.