Larry is looking for a mate, but since his is such a busy man he is employing two of his friends to help him.
There are ~N~ candidate mates, each of which have two values: a beauty value ~(a_i)~ and a personality value ~(b_i)~.
One of Larry's friends cares about both values, and will only consider a mate for larry if their beauty is at least ~A~ and their personality is at least ~B~.
The other of his friends cares about the overall value, and will only consider a mate for Larry if their beauty value + their personality value is at least ~C~.
Larry doesn't know his friends' values of ~A~, ~B~, and ~C~ though, so given ~Q~ triplets of integers ~(A,B,C)~, he wants you to detemine how many mates will be considered a candidate by both of his friends. Can you help him?
The first line will contain two integers ~N~ and ~Q\ (1 \leq N,Q \leq 10^5)~.
The next ~N~ lines will contain two values ~a_i,b_i\ (0 \leq a_i,b_i \leq 10^9)~
The next ~Q~ lines will contain three values ~A~, ~B~, and ~C\ (0 \leq A,B,C \leq 10^9)~.
You are to output ~Q~ lines: the number of mates considered to be a candidate by both of his friends for each query.
Subtask 1 (2%)
~N,Q \leq 3000~
Subtask 2 (20%)
~a_i,b_i,A,B \leq 10^5~, ~C=0~
Subtask 3 (21%)
~a_i,b_i,A,B \leq 10^5~, ~C \leq 2\cdot 10^5~
Subtask 4 (57%)
No additional constraints.
5 4 35 100 70 70 45 15 80 40 20 95 20 50 120 10 10 100 60 60 80 0 100 100
2 4 1 1