Một đoạn trong thứ tự XOR · canuc80k6111

Cho dãy $A$ . Gọi $s_{1} < s_{2} < \dots < s_{k}$ là toàn bộ giá trị phân biệt có thể nhận được bằng XOR của một dãy con không nhất thiết liên tiếp, cho phép dãy con rỗng. Cho $L, R$ , hãy in $s_{L}, \dots, s_{R}$ .

Input

Dòng đầu chứa $N$ $L$ $R$ .
Dòng tiếp theo chứa $A_{1}, \dots, A_{N}$ .

Output

In các giá trị ở vị trí $L, \dots, R$ theo thứ tự tăng.

Constraints

$1 \leq N \leq 2 \cdot 1 0^{5}$ .
$0 \leq A_{i} < 2^{60}$ .
$1 \leq L \leq R, R - L + 1 \leq 2 \cdot 1 0^{5}$ , và $R$ không vượt số XOR phân biệt.

Scoring

Subtask $1$ ( $50%$ số điểm): $N \leq 18$ và $R - L + 1 \leq 1000$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

3 2 4
1 2 4

Output

1 2 3

Giải thích: Ba số $1, 2, 4$ sinh mọi giá trị từ $0$ đến $7$ , nên các vị trí từ $2$ đến $4$ lần lượt là $1, 2, 3$ .

Mô hình: Cho dãy A. Gọi s_1<s_2<...<s_k là toàn bộ giá trị phân biệt có thể nhận được bằng XOR của một dãy con không nhất thiết liên tiếp, cho phép dãy con rỗng. Cho L,R, hãy in s_L..s_R.
Thuật toán: Xây cơ sở 60 bit và rút gọn từ pivot thấp lên cao. Gom pivot theo bit tăng thành v. Với mỗi chỉ số zero-based idx từ L-1 đến R-1, tính XOR của v_i tại các bit i được bật trong idx; đó là s_(idx+1).
Thuật toán: Không cần sinh các giá trị trước L, nên thời gian phụ thuộc vào R-L+1, không phụ thuộc L.
Chứng minh đúng: Cơ sở rút gọn có các pivot riêng biệt và không vector cao hơn nào chứa pivot thấp hơn. Vì vậy ánh xạ từ mask hệ số sang giá trị span là song ánh và bảo toàn thứ tự số như chứng minh ở bài 11. Do đó mask idx cho đúng phần tử phân biệt thứ idx+1; lặp qua đoạn chỉ số cho đúng output.
Độ phức tạp: O(N*60+60^2+(R-L+1)*60), bộ nhớ O(60).