P9277 [AGM 2023 Qualifier] Reverse

Given a sequence $a$ of length $N$, where every number is less than $2^K$. You need to perform exactly $P$ operations. In each operation, you flip one binary bit of one number. In the end, you need to make $$\sum_i\sum_j a_i\oplus a_j(i

The first line contains integers $N$, $K$, $P$. It is guaranteed that $1 \le N \le 10^5$, $1 \le K \le 30$, $1 \le P \le N \times K$. The next line contains $N$ integers, the sequence $a$. For all $1 \le i \le N$, it is guaranteed that $0 \le a_i < 2^K$.

Output $P$ lines. Each line contains two integers $i$ and $j$, satisfying $1 \le i \le N$, $0 \le j < K$, meaning that you flip the $j$-th bit of the number $a_i$. That is, $a_i \leftarrow a_i \oplus 2^j$. **You may flip the same bit multiple times. If there are multiple solutions that maximize the total sum, output any one of them.**

Translated by ChatGPT 5