Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-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*_{cnti} (1 ≤ *p*_{1} < *p*_{2} < ... < *p*_{cnti} ≤ 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-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:25:19 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|