D. Flip
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Having been an amazing skateboarder, you know how cool flips are: Heelflips, Kickflips, Frontflips and so on. You know what it's all about!

Because you retired, today you are going to have fun with a different type of flip.

You are given an array $$$a$$$ of $$$N$$$ numbers represented on $$$K$$$ bits and a number $$$P$$$.

Exactly $$$P$$$ times you have to pick a bit from a number and flip it (you are allowed to flip the same bit as many times as you want) such that after you perform all the flips, the following sum is maximized:

$$$\sum\limits_{1 \leq i \lt j \leq N} a_i \oplus a_j$$$

where $$$\oplus$$$ represents the bit-wise xor operator.

In case there are multiple such solutions, you should print any.

Input

The first line contains integers $$$N$$$, $$$K$$$ and $$$P$$$. It is guaranteed that $$$1 \leq N \leq 10^5$$$, $$$1 \leq K \leq 30$$$ and $$$1 \leq P \leq N*K$$$.

The next line contains $$$N$$$ integers, the array $$$a$$$. It is guaranteed that $$$0 \leq a_i \lt 2^K$$$ for all $$$1 \leq i \leq N$$$.

Output

The output file should contain exactly $$$P$$$ lines each containing two integers $$$i$$$ and $$$j$$$ such that $$$1 \leq i \leq N$$$ and $$$0 \leq j \lt K$$$, which represent flipping bit $$$j$$$ of number $$$a_i$$$. Namely, $$$a_i \Leftarrow a_i \oplus 2^j$$$.

You are allowed to flip the same bit multiple times. Any solution that maximizes the sum is valid. The order in which you output the operations is not important.

Examples
Input
2 5 1
0 31
Output
1 0
Input
4 2 2
0 0 2 2
Output
4 0
3 0
Input
5 6 4
63 15 0 10 5
Output
5 5
4 5
4 4
5 4