Mock CCC would not be a real mock CCC without a data structures problem, would it?

You are given a function $f$ that maps ${\mathbb{Z}}^2$ to $\mathbb{Z}$. $f$ is zero everywhere except at $N$ points.

You must answer $Q$ queries, as follows

• Query(x_a, y_a, x_b, y_b) - let $S$ be the multiset of all integers $f(x,y)$ where $x_a\le x\le x_b$, $y_a\le y\le y_b$, and $f(x,y)$ is positive. Return 1 if there is a submultiset of $S$ of size $3$ where the three elements of the submultiset, when interpreted as side lengths, form a non-degenerate triangle.

Scoring

To get full marks, your solution must solve all test cases in under 0.5 seconds.

If your solution solves all test cases in under 1 second, you get 7 marks.

If your solution solves all test cases in under 1.5 seconds, you get 3 marks.

If your solution solves all test cases in under 2 seconds, you get 1 mark.

Constraints

$1\le N,Q\le {10}^5$

$1\le x,y,z\le {10}^9$

$1\le x_a\le x_b\le {10}^9$

$1\le y_a\le y_b\le {10}^9$

Input Specification

The first line contains two integers, $N$ and $Q$.

The next $N$ lines contain three integers, $x$, $y$, and $z$, indicating that $f(x,y)=z$.

The next $Q$ line contain four integers, $x_a$, $y_a$, $x_b$, and $y_b$.

Output Specification

Output $Q$ lines. On the $i$th line, output Query(x_a, y_a, x_b, y_b).

Sample Input

9 5
1 3 3
2 3 1
3 3 4
1 2 1
2 2 5
3 2 9
1 1 2
2 1 6
3 1 5
1 1 1 2
1 1 2 2
1 1 1 3
1 2 3 2
1 1 3 3

Sample Output

0
1
0
0
1