Lunch Menu

Time limit1sMemory limit512 MB

Summary

Count the menus whose spiciness falls in [u, v] and whose sweetness falls in [x, y] for each query.

Level: Medium5 of 10
Topics: Segment tree, Sorting, Binary search
Solved: No attempts yet

Problem

Seungkwan and Youngwoo will eat lunch together for the next $Q$ days.

Seungkwan likes every menu whose spiciness is at least $u$ and at most $v$ , and Youngwoo likes every menu whose sweetness is at least $x$ and at most $y$ . The four numbers $u$ , $v$ , $x$ , $y$ change from day to day with their mood.

There are $N$ lunch menus in total, and each menu has one spiciness value $a$ and one sweetness value $b$ .

Write a program that counts, for each day, how many menus both of them like.

Input

The first line contains the number of lunch menus $N$ and the number of days $Q$ . ( $1 \le N \le 100\,000$ , $1 \le Q \le 5\,000$ )

Each of the next $N$ lines contains the spiciness $a$ and the sweetness $b$ of one menu. ( $1 \le a, b \le 10^9$ )

The values of $a$ are pairwise distinct, and the values of $b$ are pairwise distinct. No two different menus share a spiciness value, and no two different menus share a sweetness value.

Each of the next $Q$ lines contains $u$ , $v$ , $x$ , $y$ for one day. ( $1 \le u \le v \le 10^9$ , $v \le u + 10\,000$ , $1 \le x \le y \le 10^9$ , $y \le x + 10\,000$ )

Output

Print $Q$ lines, one answer per day. On the $i$ -th line print the number of menus that satisfy $u \le a \le v$ and $x \le b \le y$ on the $i$ -th day.

Examples2

Example 1

Input

6 4
10 50
30 30
20 70
60 20
70 40
100 10
1 1000 10 70
10 30 50 70
10 100 20 20
30 99 1 39

Expected output

Example 2
Input
```
1 1
5 7
1 10 1 10
```
Expected output
```
1
```