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