sIs there any (efficient) algorithm for the following problem:

Let $n = 128$ and $m = 64$ (in the end only $n > m$ matters) and $p_1, \ldots, p_t \in \{ -1,1 \} ^{128}$ be given ($t << 2^{128}$) . Find a matrix $A \in M(n \times m, \frac{1}{2^{64}}\mathbb{Z})$ and vectors $q_1, \ldots, q_t \in \{ -1, 1 \}^{64}$, such that if $b_i = A q_i \in \mathbb{R}^{128}$ then $$p_{ij} = sgn (b_{ij})$$ for most $1 \leq i \leq t$ and $1 \leq j \leq n$, i.e., the number of tuples $(i,j)$ violating the equation is neglible compared to $tn$.