Với mỗi số nguyên từ \(0\) đến \(N - 1\), có đúng hai lá bài mang số đó ở mặt trước. Bạn và JOI đang luyện tập trò chơi lật bài ghi nhớ bằng \(2N\) lá bài này.

Khi bắt đầu luyện tập, các lá bài được đặt úp thành một hàng ngang trên bàn. Lá bài thứ \(i + 1\) từ trái sang (\(0 \le i \le 2N - 1\)) được gọi là lá bài \(i\). Gọi \(A_i\) là số nguyên viết ở mặt trước của lá bài \(i\) (\(0 \le i \le 2N - 1\)). Ban đầu, cả bạn và JOI đều không biết các giá trị \(A_i\) (\(0 \le i \le 2N - 1\)).

Bạn và JOI có thể lặp lại quá trình trao đổi sau nhiều nhất \(K\) lần:

1. Bạn chỉ định hai trong số \(2N\) lá bài.
2. JOI lật hai lá bài được chỉ định và bí mật xem các số viết ở mặt trước để bạn không nhìn thấy. Nếu hai số bằng nhau, JOI ghi nhớ số đó và cho bạn biết. Nếu hai số khác nhau, JOI ghi nhớ số mà mình thấy dễ nhớ hơn trong hai số đó và cho bạn biết số này.

Mức độ dễ nhớ của các số đối với JOI được biểu diễn bằng \(N\) số nguyên \(P_0, P_1, \ldots, P_{N-1}\). Các số nguyên này thỏa mãn hai điều kiện:

• \(0 \le P_i \le N - 1\) (\(0 \le i \le N - 1\)).
• \(P_i \ne P_j\) (\(0 \le i < j \le N - 1\)).

JOI thấy số \(i\) dễ nhớ hơn số \(j\) khi và chỉ khi \(P_i < P_j\).

Nhiệm vụ của bạn là xác định số viết trên từng lá bài bằng cách trao đổi với JOI không quá \(K\) lần. Tuy nhiên, bạn không biết các giá trị \(P_0, P_1, \ldots, P_{N-1}\) biểu diễn mức độ dễ nhớ của các số đối với JOI.

Yêu cầu

Hãy viết chương trình trao đổi với JOI để xác định số nguyên viết trên từng lá bài.

Chi tiết cài đặt

Bạn phải viết một chương trình C++ cài đặt phương pháp xác định số nguyên trên từng lá bài. Chương trình phải include tệp memory2.h được đính kèm theo bài.

Bạn phải cài đặt hàm sau:

void Solve(int T, int N)

Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử. Tham số T là số thứ tự của subtask; tham số N cho biết có \(2N\) lá bài.

Hàm này phải gọi Flip để xác định các số viết trên những lá bài, rồi gọi Answer để báo kết quả.

Trong chương trình, bạn có thể gọi các hàm sau.

Hàm Flip

int Flip(int I, int J)

Gọi hàm này để chỉ định các lá bài cho JOI. Hai tham số I, J là chỉ số của hai lá bài mà JOI sẽ lật.

I và J phải là hai số nguyên khác nhau, cùng nằm trong đoạn từ \(0\) đến \(2N - 1\). Nếu gọi Flip với các tham số không thỏa mãn điều kiện này, bài làm bị chấm Sai đáp án [1].

Nếu \(A_I = A_J\), hàm trả về giá trị đó. Nếu không, hàm trả về số mà JOI thấy dễ nhớ hơn trong hai số \(A_I\) và \(A_J\).

Nếu gọi hàm này quá \(K\) lần, bài làm bị chấm Sai đáp án [2].

Hàm Answer

void Answer(int I, int J, int X)

Gọi hàm này để báo rằng bạn đã xác định được chỉ số của hai lá bài có số \(X\) viết ở mặt trước.

Các tham số I, J, X phải thỏa mãn tất cả các điều kiện sau:

• \(0 \le I \le 2N - 1\).
• \(0 \le J \le 2N - 1\).
• \(I \ne J\).
• \(A_I = A_J = X\).

Nếu gọi Answer với các tham số không thỏa mãn các điều kiện này, bài làm bị chấm Sai đáp án [3].

Tham số X phải khác với tham số X của mọi lần gọi Answer trước đó. Nếu không, bài làm bị chấm Sai đáp án [4].

Bạn phải gọi hàm này đúng \(N\) lần. Nếu không, bài làm bị chấm Sai đáp án [5].

Bạn được tự do cài đặt các hàm khác và khai báo biến toàn cục để sử dụng nội bộ. Tuy nhiên, bài nộp không được đọc hay ghi đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác bằng bất kỳ cách nào.

Cách nộp bài

Nộp một tệp mã nguồn C++ chứa hàm Solve và include memory2.h. Không viết hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn. Hệ thống chấm sẽ cung cấp các hàm Flip và Answer, đồng thời gọi Solve đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 50\).
• \(0 \le P_i \le N - 1\) (\(0 \le i \le N - 1\)).
• \(P_i \ne P_j\) (\(0 \le i < j \le N - 1\)).
• \(0 \le A_i \le N - 1\) (\(0 \le i \le 2N - 1\)).
• Với mỗi \(x\) (\(0 \le x \le N - 1\)), có đúng hai chỉ số \(i\) (\(0 \le i \le 2N - 1\)) thỏa mãn \(A_i = x\).

Phân nhóm

1. 10 điểm: \(T = 1\); \(K = 10\,000\); \(P_i = i\) (\(0 \le i \le N - 1\)).
2. 50 điểm: \(T = 2\); \(K = 400\); \(P_i = i\) (\(0 \le i \le N - 1\)).
3. 40 điểm: \(T = 3\); \(K = 300\).

Ví dụ giao tiếp

Dưới đây là một ví dụ dữ liệu vào của chương trình chấm mẫu và một chuỗi lời gọi hàm tương ứng.

1 3 10000
0 1 2
1 0 2 0 1 2

Các lời gọi hàm

Cột bên trái là lời gọi hàm, cột bên phải là giá trị trả về. Hàm Answer không trả về giá trị.

Lưu ý rằng các lời gọi hàm trong ví dụ này không nhất thiết đều có ý nghĩa.