Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Valera and Queries

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputValera 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.

Examples

Input

3 3

1 3

4 5

6 7

3 1 4 7

2 4 5

1 8

Output

3

1

0

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/12/2020 00:05:35 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|