I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists.

For example, if I give you $[00110, 01100, 11000]$ then the only solution is $\{00110, 11000\}$. Alternatively, the input $[111, 011, 110, 101]$ has no solution. And any list that contains the all-zero bitvector $000...0$ and another element $e$ has a trivial solution $\{e, 000...0\}$.

Here's a slightly harder example, with no solution (each row is a bit vector, the black squares are 1s and the white squares are 0s):

```
■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □ 
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

```

How efficiently can two non-overlapping bitvectors be found, or be shown not to exist?

The naive algorithm, where you just compare every possible pair, is $O(n^2 k)$. Is it possible to do better?