#216122. [ICPC 2022 NAC] Triangular Logs

The local forest has a lot of trees! Each tree is located at integer coordinates and has an integer height. Cutting down any tree gives you a log with a length equal to its height. You want to obtain three triangular logs (that is, three logs that form a non-degenerate triangle) by cutting down three trees.

Given a list of queries which each specify an axis-aligned rectangular region, can you obtain three triangular logs by cutting down three trees in that region, possibly including those on the boundary of the rectangle?

The first line of input contains two integers and (), where is the number of trees and is the number of queries.

Each of the next lines contains three integers , and (), which describes a tree at location with height . All tree locations are distinct.

Each of the next lines contains four integers , , and (, ), describing an axis-aligned rectangular region for a query.

Output lines. Each line contains a single integer, which is the answer to the given query. Output if there are three trees in the queried region that can form a non-degenerate triangle, and otherwise. Output answers to the queries in the order of the input.

样例输入 1

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

样例输出 1

0
1
0
0
1