Problem3250--CF369E - E. Valera and Queries

3250: CF369E - E. Valera and Queries

[Creator : ]
Time Limit : 2.000 sec  Memory Limit : 256 MiB

SubmitSolved: 3Submit Num: 3StatisticsShowOff!

Description

Valera loves segments. He has recently come up with one interesting problem.
The $Ox$ axis of coordinates has $n$ segments, the $i$-th segment starts in position $l_i$ and ends in position $r_i$ (we will mark it as $[l_i,r_i]$). Your task is to process $m$ queries, each consists of number $cnt_i$ and a set of $cnt_i$ coordinates of points located on the $Ox$ axis. The answer to the query is the number of segments, such that each of them contains at least one point from the query. Segment $[l,r]$ contains point $q$, if $l≤q≤r$.
Valera found the solution of this problem too difficult. So he asked you to help him. Help Valera.

Input

The first line contains two integers $n,m\ (1≤n,m≤3·10^5)$ − the number of segments on the axis of coordinates and the number of queries.

Next $n$ lines contain the descriptions of the segments. The $i$-th line contains two positive integers $l_i,r_i\ (1≤l_i≤r_i≤10^6)$ − the borders of the $i$-th segment.

Next $m$ lines contain the description of the queries, one per line. Each line starts from integer $cnt_i\ (1≤cnt_i≤3·10^5)$ − the number of points in the $i$-th query. Then the line contains $cnt_i$ distinct positive integers $p_1,p_2,...,p_{cnt_i}\ (1≤p_1<p_2<...<p_{cnt_i}≤10^6)$ − the coordinates of points in the $i$-th query.

It is guaranteed that the total number of points in all queries doesn't exceed $3·10^5$.

Output

Print $m$ non-negative integers, where the $i$-th number is the response to the $i$-th query.

Sample 1 Input 

3 3
1 3
4 5
6 7
3 1 4 7
2 4 5
1 8

Sample 1 Output 

3
1
0

HINT

CF369E。

Source/Category

 
Submit