Problem Description

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

as large as possible, where $\oplus$ is the bitwise XOR operation.

Input Format

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 Format

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.

2 5 1
0 31

1 0

4 2 2
0 0 2 2

4 0
3 0

5 6 4
63 15 0 10 5

5 5
4 5
4 4
5 4

Hint

Translated by ChatGPT 5