Mỗi chiếc chìa khóa có \(n\) rãnh đánh số từ \(0\), rãnh thứ \(i\) có độ sâu \(A[i]\) là một số nguyên không âm \(60\)-bit.
Bạn muốn đánh ra một chiếc chìa sơ cua, nhưng vì nhìn bằng mắt thường không thể xác định vẽ lại chính xác độ sâu của từng rãnh, vì thế phải đưa vào dụng cụ đo. Nói cách khác, ban đầu bạn không biết giá trị của mảng \(A\).

Dụng cụ đo có hai chế độ:

• AND i1 i2 i3: bạn sẽ chọn ra ba vị trí rãnh thỏa mãn \(0 \le i_1 < i_2 < i_3 < n\), và chìa khóa sẽ trả về \(A[i_1] \ \& \ A[i_2] \ \& \ A[i_3]\) là giá trị của phép AND ba số.
• OR i1 i2 i3: bạn sẽ chọn ra ba vị trí rãnh thỏa mãn \(0 \le i_1 < i_2 < i_3 < n\), và chìa khóa sẽ trả về \(A[i_1] \ | \ A[i_2] \ | \ A[i_3]\) là giá trị của phép OR ba số.

Biết rằng:

• Mỗi số nguyên không âm \(60\)-bit \(X\) luôn tồn tại một bộ số nhị phân \((x_{59}, x_{58}, x_{57}, \dots, x_1, x_0)\) duy nhất sao cho \(\forall i, 0 \le i < 60 : 0 \le x_i \le 1\) và

  \[ X = \sum_{i=0}^{59} (x_i \cdot 2^i) \]

• Giả sử hai số \(X\) và \(Y\) có bộ số tương ứng là \((x_{59}, x_{58}, x_{57}, \dots, x_1, x_0)\) và \((y_{59}, y_{58}, y_{57}, \dots, y_1, y_0)\). Khi đấy:

  • \(Z = X \ \& \ Y\) được biểu diễn bởi bộ số \((z_{59}, z_{58}, z_{57}, \dots, z_1, z_0)\) thỏa mãn \(\forall i, 0 \le i < 60\): \(z_i = 1\) nếu \(x_i = 1\) và \(y_i = 1\), ngược lại \(z_i = 0\).
  • \(Z' = X \ | \ Y\) được biểu diễn bởi bộ số \((z'_{59}, z'_{58}, z'_{57}, \dots, z'_1, z'_0)\) thỏa mãn \(\forall i, 0 \le i < 60\): \(z'_i = 0\) nếu \(x_i = 0\) và \(y_i = 0\), ngược lại \(z'_i = 1\).
• Phép AND và OR đều có tính chất giao hoán và kết hợp: \(X \ \& \ Y = Y \ \& \ X\) và \((X \ \& \ Y) \ \& \ Z = X \ \& \ (Y \ \& \ Z)\), tương tự với phép OR.

Có \(\tau\) chiếc chìa khóa như vậy. Với mỗi chìa khóa, bạn hãy tìm cách dùng ít lần đo nhất để xác định được chính xác hình dáng của các rãnh khóa.

Tương tác

Bạn cần cài đặt hàm vector<long long> keyDuplication(int n), mỗi lần gọi hàm tương ứng với một chiếc chìa khóa có \(n\) rãnh bạn cần xác định độ sâu. Hàm cần trả về một vector<long long> gồm \(n\) phần tử, phần tử thứ \(i\) của vector có giá trị bằng \(A[i]\).

Trong cài đặt của hàm keyDuplication, bạn được phép gọi tới một trong hai hàm sau thuộc thư viện andor.h:

• long long AND(int i1, int i2, int i3) nhận vào ba vị trí theo thứ tự \(i_1, i_2, i_3\), với điều kiện \(0 \le i_1 < i_2 < i_3 < n\), và trả về \(A[i_1] \ \& \ A[i_2] \ \& \ A[i_3]\).
• long long OR(int i1, int i2, int i3) nhận vào ba vị trí theo thứ tự \(i_1, i_2, i_3\), với điều kiện \(0 \le i_1 < i_2 < i_3 < n\), và trả về \(A[i_1] \ | \ A[i_2] \ | \ A[i_3]\).

Khi chấm bài, với mỗi test, hàm keyDuplication sẽ được gọi \(\tau\) lần, mỗi lần gọi tương ứng với một trường hợp chìa khóa cần xác định.

Lưu ý

• Thí sinh cần có dòng lệnh khai báo thư viện #include "andor.h" ở dòng đầu tiên của chương trình.
• File mã nguồn của thí sinh không được chứa hàm main. Việc viết hàm main có thể gây ra lỗi biên dịch cho bài làm của thí sinh.
• Thí sinh có thể định nghĩa thêm hàm hoặc khai báo thêm các biến toàn cục nếu cần.
• Thí sinh không được đọc dữ liệu từ thiết bị vào chuẩn hay bất cứ tệp tin nào, cũng như không được in ra thiết bị ra chuẩn hay bất kì tệp tin nào.
• Thí sinh sẽ nhận được kết quả chấm là Wrong Answer nếu như tham số truyền vào hàm AND hoặc hàm OR không hợp lệ, hay kết quả trả về của hàm keyDuplication không chính xác.
• Tải chương trình mẫu và môi trường biên dịch.

Giới hạn

• \(\tau \le 20000\).
• \(0 \le A[i] < 2^{60}\).
• Tổng số rãnh của \(\tau\) chiếc chìa khóa không quá \(10^5\).

Chấm điểm

Chương trình chấm mẫu nhận vào dữ liệu đầu vào theo mẫu sau:

• Dòng đầu tiên chứa duy nhất số \(\tau\), là số lượng chiếc chìa khóa cần xác định của bộ test.
• Tiếp theo là \(\tau\) bộ dữ liệu, mỗi bộ dữ liệu gồm hai dòng:
  • Dòng đầu tiên chứa duy nhất số \(N\) là số rãnh của chiếc chìa khóa.
  • Dòng thứ hai lần lượt chứa \(N\) số \(A[0], A[1], \dots, A[n - 1]\) lần lượt là độ sâu của \(N\) rãnh chìa khóa.

Chương trình chấm mẫu sẽ in ra \(\tau\) dòng, dòng thứ \(i\) cho biết chiếc chìa khóa thứ \(i\) đã được đoán đúng hay sai.

• Subtask \(1\) (\(15\) điểm): \(A[0] = A[1]\) với mọi chiếc chìa khóa.
• Subtask \(2\) (\(20\) điểm): \(0 \le A[i] \le 1\) với mọi rãnh chìa khóa.
• Subtask \(3\) (\(30\) điểm): Tổng số rãnh của \(\tau\) chìa khóa \(\le 200\).
• Subtask \(4\) (\(35\) điểm): Tổng số rãnh của \(\tau\) chìa khóa \(\le 10^5\).

Với mỗi chiếc chìa khóa, giả sử bạn đoán đúng độ sâu của cả \(N\) rãnh thông qua \(\beta\) phép đo lường. Giám khảo đã ấn định trước \(5\) số \(\alpha_1 \le \alpha_2 \le \alpha_3 \le \alpha_4 \le \alpha_5 < N^3\).

• Nếu \(\beta \le \alpha_1\), hệ số điểm của chìa khóa đó là \(100\%\).
• Nếu \(\alpha_1 < \beta \le \alpha_2\), hệ số điểm của chìa khóa đó là \(80\%\).
• Nếu \(\alpha_2 < \beta \le \alpha_3\), hệ số điểm của chìa khóa đó là \(50\%\).
• Nếu \(\alpha_3 < \beta \le \alpha_4\), hệ số điểm của chìa khóa đó là \(30\%\).
• Nếu \(\alpha_4 < \beta \le \alpha_5\), hệ số điểm của chìa khóa đó là \(20\%\).
• Nếu \(\alpha_5 < \beta\), hệ số điểm của chìa khóa là \(10\%\).

Điểm của test là mức hệ số điểm nhỏ nhất của các lần đoán chìa khóa trong test đó.
Giá trị các rãnh chìa khóa là cố định từ trước khi thực hiện các câu hỏi.

Giải thích

Giả sử ta phải xác định chiếc chìa khóa có \(N = 6\) và \(A = [12, 23, 34, 45, 56, 67]\). Khi đó, hàm keyDuplication(6) được gọi.

Giả sử trong trường hợp này hàm gọi tới các hàm sau:

• AND(1, 3, 5) trả về \(1\).
• OR(0, 2, 3) trả về \(47\).

Cuối cùng, hàm trả về mảng {12, 23, 34, 45, 56, 67}.