반평면

평면 위에 $n$개의 점이 있다. $i$번째 점 $(x_i, y_i)$의 값은 $\mathbf{d}_i \in D$이다. 집합 $D$는 $\mathbb{F}_p$ 위의 모든 $3 \times 1$ 행렬이고, 집합 $O$는 $\mathbb{F}_p$ 위의 모든 $3 \times 3$ 행렬이며, $p = 10^9+7$이다. $+$는 행렬 덧셈으로, 두 종류의 곱은 $p$를 법으로 한 행렬 곱으로 계산한다.

$\varepsilon_D$는 $D$의 영원소이고, $\varepsilon_O$는 $O$의 항등원이다. $D$의 덧셈은 교환법칙과 결합법칙을 만족하며 $\varepsilon_D$가 항등원이다. $O$와 $D$의 곱은 $O$의 곱과 호환되고 $D$의 덧셈에 대해 분배법칙을 만족한다. $O$의 곱은 결합법칙을 만족하며 $\varepsilon_O$가 항등원이다. 풀이에서는 이 성질만 사용한다.

$m$개의 질의가 주어진다. 각 질의는 $a$, $b$, $c$와 $3 \times 3$ 행렬 $\mathbf{o}$로 이루어진다. 질의마다 $\mathbf{s} = \varepsilon_D$로 둔다. $ax_i + by_i < c$를 만족하는 모든 점 $i$에 대해 $\mathbf{s}$를 $\mathbf{s} + \mathbf{d}_i$로 바꾸고, 이어서 $\mathbf{d}_i$를 $\mathbf{o} \cdot \mathbf{d}_i$로 바꾼다. 마지막 $\mathbf{s}$가 질의의 답이다. 질의는 입력 순서대로 수행하며, 바뀐 $\mathbf{d}_i$는 이후 질의에도 그대로 남는다.

첫 줄에 $n$ ($1 \le n \le 3 \cdot 10^5$)이 주어진다. 이어지는 $n$개의 줄에는 정수 다섯 개 $x_i, y_i, d_{i0}, d_{i1}, d_{i2}$가 주어진다. 단, $|x_i|, |y_i| \le 10^6$이다.

다음 줄에는 $m$ ($1 \le m \le 1.5 \cdot 10^4$)이 주어진다. 이어지는 $m$개의 줄에는 정수 열두 개 $a, b, c, o_{00}, o_{01}, o_{02}, o_{10}, \ldots, o_{22}$가 주어진다. 단, $|a|, |b| \le 10^3$, $b \ne 0$, $|c| \le 10^6$이며, 행렬의 모든 원소는 $0$ 이상 $10^9+6$ 이하이다.

모든 질의 $i$와 점 $j$에 대해 $a_i x_j + b_i y_j \ne c_i$이다. 서로 다른 두 질의 $i$, $j$에 대해 $(a_i/b_i, c_i/b_i)$와 $(a_j/b_j, c_j/b_j)$는 서로 다르다.

각 질의마다 $\mathbf{s}$의 성분 $s_0$, $s_1$, $s_2$를 공백으로 구분해 한 줄에 출력한다.

풀이는 문제에 나온 성질 이외의 행렬 연산 성질에 의존하지 않는다. 행렬은 이 문제를 채점기로 시험할 수 있도록 하기 위해서만 사용되었다.