3 ms·

You can decide which bits to set for an input in k^2 time I guess, not k*n time, then set each one with a single memory access.