Background

My heart is still beating.

Problem Description

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$.

Input Format

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.

Output Format

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$.

3
5 2 1
3 0 1
-2 2 2
1 -3 3
-2 -1 4
0 0 5
2
5
5 4 2
3 0 1
-2 2 2
1 -3 3
-2 -1 4
0 0 5
2 3
2 4
5 1
3 5
5 6 3
3 0 1
-2 2 2
1 -3 3
-2 -1 4
0 0 5
3 5 4
2 5 3
4 2 1
2 4 3
3 1 2
3 1 4

10
0110
100101

Hint

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

Translated by ChatGPT 5