P9685 Tricolor.

My heart is still beating.

You are given $n$ triples $(a_i,b_i,c_i)$. There are $q$ queries. In each query, you are given a set $S$. Determine whether there exists a real triple $(p,q,r)$ such that: for all $i$ satisfying $pa_i+qb_i+r>0$, the set formed by their $c_i$ is exactly $S$.

The first line contains an integer $T$, which represents the number of test cases. For each test case, the first line contains three numbers $n,q,k$, where $k=|S|$. The next $n$ lines each contain three integers $a_i,b_i,c_i$. The next $q$ lines describe the queries. The $i$-th line contains $k$ integers $s_{i,1},s_{i,2},\dots,s_{i,k}$, representing the elements of $S$ in the $i$-th query. It is guaranteed that the elements are distinct.

For each test case, output a string $R$ of length $q$ in one line. For the $i$-th query, if the answer is “exists”, then $R_i$ is $\tt 1$; otherwise, $R_i$ is $\tt 0$.

### Constraints For all testdata, $1\le n,\sum n\le 10^5$, $1\le q,\sum q \le 3\times 10^5$, $1\le k\le 3$, $1\le c_i,s_{i,j}\le n$, $|a_i|,|b_i|\le 10^9$. For any $i\neq j$, it is guaranteed that $(a_i,b_i)\neq (a_j,b_j)$, and there do not exist $(p,q)$ and three different indices $i,j,k$ such that $pa_i+qb_i=pa_j+qb_j=pa_k+qb_k$. ### Subtasks | # | Special Property | Points | | :----------: | :----------: | :----------: | | 0 | Sample | 0 | | 1 | $n\le 3$ | 2 | | 2 | $k=1$ | 11 | | 3 | $\sum n^2\le 10^6$ | 23 | | 4 | $k=2$ | 29 | | 5 | $k=3$ | 35 | Translated by ChatGPT 5