Problem Description

Given a sequence \( a \) of length \( N \) where each number is less than \( 2^K \). You need to perform exactly \( P \) operations, each involving flipping a single binary bit of one of the numbers. The goal is to maximize the sum

\[ \sum_i \sum_j a_i \oplus a_j \quad (i < j) \]

where \( \oplus \) denotes the bitwise XOR operation.

Input Format

The first line contains the integers \( N \), \( K \), and \( P \), with the constraints \( 1 \leq N \leq 10^5 \), \( 1 \leq K \leq 30 \), and \( 1 \leq P \leq N \times K \).

The next line contains \( N \) integers, representing the sequence \( a \). For all \( 1 \leq i \leq N \), it is guaranteed that \( 0 \leq a_i < 2^K \).

Output Format

Output \( P \) lines, each containing two integers \( i \) and \( j \), satisfying \( 1 \leq i \leq N \) and \( 0 \leq j < K \), indicating that the \( j \)-th bit of number \( a_i \) is flipped. 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 sum, output any one of them.

Sample Input and Output

Sample Input #1

2 5 1
0 31

Sample Output #1

1 0

Sample Input #2

4 2 2
0 0 2 2

Sample Output #2

4 0
3 0

Sample Input #3

5 6 4
63 15 0 10 5

Sample Output #3

5 5
4 5
4 4
5 4

见题面 Input 部分

见题面 Output 部分