Problem: 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 li and ends in position ri (we will mark it as [li, ri]). Your task is to process m queries, each consists of number cnti and a set of cnti 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·105) — 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 li, ri (1 ≤ li ≤ ri ≤ 106) — the borders of the i-th segment.

Next m lines contain the description of the queries, one per line. Each line starts from integer cnti (1 ≤ cnti ≤ 3·105) — the number of points in the i-th query. Then the line contains cnti distinct positive integers p1, p2, ..., pcnti (1 ≤ p1 < p2 < ... < pcnti ≤ 106) — 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·105. 

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

Solution (in JAVA):

Solution:
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.ObjectInputStream.GetField;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;
 
		public	class Q2 {
				
				static long MOD = 1000000007;
				static boolean b1,b[],bc[];
				static boolean boo[][][];
				static int ans1 = -1,ans2 = -1, root;
				static ArrayList<Integer>[] amp,amp1;
				static ArrayList<Pair>[] pmp;
				static int sum[],dist[],cnt[],ans[],size[],col[][];
				static int p = 0,cnt1 =0 ,cnt2 = 0;
				//static ArrayList<Pair3>[][][] pmp;
				static FasterScanner sc = new FasterScanner(System.in);
				static Queue<Integer> q = new LinkedList<>();
				static int arr[],start[],end[],color[],parent[];
				static PriorityQueue<Integer> pq;
				//static ArrayList<Integer> parent = new ArrayList<>();
				static LinkedList<Integer> fa;
				static BufferedWriter log;
				static TreeMap<Integer,Integer> tm = new TreeMap<>();
			//	static HashMap<Integer,Pair> hs;
				static Stack<Integer> stack = new Stack<>();
				static Pair prr[];
				static int dp[][];
				static long parent1[],parent2[],size1[],size2[],value[];
				static long Ans;
				public static void main(String[] args) throws Exception {
					new Thread(null, new Runnable() {
						public void run() {
							try {
								soln();
							} catch (Exception e) {
								System.out.println(e);
							}
						}
					}, "1", 1 << 26).start();
			    }
				static int MAX = 1000005;
				static int n , m ,k, max, x1, x2;
				static HashSet<Integer>[] hs;
				public static void soln() throws IOException {
					//FasterScanner in = new FasterScanner(new FileInputStream("C:\\Users\\Admin\\Desktop\\QAL.txt"));
					//PrintWriter out = new PrintWriter("C:\\Users\\Admin\\Desktop\\A1.txt");
					log = new BufferedWriter(new OutputStreamWriter(System.out));
					int n = sc.nextInt(), m = sc.nextInt();
					ArrayList<Pair>[] amp = new ArrayList[MAX];
					amp1 = new ArrayList[MAX];
					for(int i = 0; i< MAX;i++){
						amp[i] = new ArrayList<>();
						amp1[i] = new ArrayList<>();
					}
					for(int i = 0; i < n ;i ++){
						int l = sc.nextInt(), r = sc.nextInt();
						amp1[r].add(l);
					}
					FenwickTree ft = new FenwickTree(MAX);
					for(int i = 0; i< m; i++){
						int t = sc.nextInt();
						ArrayList<Integer> temp = new ArrayList<>();
						temp.add(0);
						while(t-->0){
							temp.add(sc.nextInt());
						}
						temp.add(MAX-1);
						for(int j= 1;j<temp.size();j++){
							int l = temp.get(j-1)+1, r = temp.get(j)-1;
							amp[r].add(new Pair(l,i));
						}
					}
					int ans[] = new int[m];
					for(int i = 1;i<=MAX-1;i++){
						for(int j = 0;j<amp1[i].size();j++){
							ft.update(amp1[i].get(j), 1);
						}
						for(int j = 0;j<amp[i].size();j++){
							int idx = amp[i].get(j).v;
							ans[idx]+=ft.rsq(amp[i].get(j).u, i);
						}
					}
					for(int i:ans){
						log.write(n-i+"\n");
					}
					log.close();
					
					//out.close();
				}
				public static class FenwickTree {

				    int[] array; // 1-indexed array, In this array We save cumulative information to perform efficient range queries and updates

				    public FenwickTree(int size) {
				        array = new int[size + 1];
				    }

				    /**
				     * Range Sum query from 1 to ind
				     * ind is 1-indexed
				     * <p>
				     * Time-Complexity:    O(log(n))
				     *
				     * @param  ind index
				     * @return sum
				     */
				    public int rsq(int ind) {
				        assert ind > 0;
				        int sum = 0;
				        while (ind > 0) {
				            sum += array[ind];
				            //Extracting the portion up to the first significant one of the binary representation of 'ind' and decrementing ind by that number
				            ind -= ind & (-ind);
				        }

				        return sum;
				    }

				    /**
				     * Range Sum Query from a to b.
				     * Search for the sum from array index from a to b
				     * a and b are 1-indexed
				     * <p>
				     * Time-Complexity:    O(log(n))
				     *
				     * @param  a left index
				     * @param  b right index
				     * @return sum
				     */
				    public int rsq(int a, int b) {
				        assert b >= a && a > 0 && b > 0;

				        return rsq(b) - rsq(a - 1);
				    }

				    /**
				     * Update the array at ind and all the affected regions above ind.
				     * ind is 1-indexed
				     * <p>
				     * Time-Complexity:    O(log(n))
				     *
				     * @param  ind   index
				     * @param  value value
				     */
				    public void update(int ind, int value) {
				        assert ind > 0;
				        while (ind < array.length) {
				            array[ind] += value;
				            //Extracting the portion up to the first significant one of the binary representation of 'ind' and incrementing ind by that number
				            ind += ind & (-ind);
				        }
				    }

				    public int size() {
				        return array.length - 1;
				    }
				}
				public static int[] answer(int[][] m) { 
					int n = m[0].length;
					int cnt[][] = new int[n][2];
					boolean b[] = new boolean[n];
					for(int i = 0; i< n;i++){
						boolean x = true;
						int deno = 0, numo = 1;
						for(int j:m[i]) deno+=j;
						for(int j = 0;j<n;j++){
							if(m[i][j]!=0){
								if(i==j){
									numo = 1;
								}
							}
						}
					}
					return new int[n];
			        // Your code goes here.
 
			    } 
				public static void dfs(int x){
					b[x] = true;
					int max = dist[x];
					boolean v = false;
					for(int e:amp[x]){
						if(!b[e]){
							dfs(e);
							max = Math.max(max, size[e]);
						}
					}
					for(int e:amp[x]){
						v = true;
						if(size[e]==max){
							cnt[x]++;
						}
					}
					size[x] = max;
					if(!v)
					cnt[x]++;
				}
				public static void bfs(int x){
					b[x] = true;
					q = new LinkedList<Integer>();
					q.add(x);
					while(!q.isEmpty()){
						//System.out.println(q);
						int y = q.poll();
							for(int i:amp[y]){
							if(!b[i]){
								q.add(i);
								dist[i] = Math.max(dist[i], dist[y]+1);
								if(dist[i]>max){
									max = dist[i];
									k = i;
								}
								b[i]= true;
							}
						}
					}
				}
				static class Pair implements Comparable<Pair> {
					int u;
					int v;
					public Pair(){
						u = 0;
						v = 0;
					}
					public Pair(int u, int v) {
						this.u = u;
						this.v = v;
					}
					public int hashCode() {
						int hu = (int) (u ^ (u >>> 32));
						int hv = (int) (v ^ (v >>> 32));
						return 31*hu + hv;
					}
			 
					public boolean equals(Object o) {
						Pair other = (Pair) o;
						return (u == other.u && v == other.v);
					}
			 
					public int compareTo(Pair other) {
						return Long.compare(u, other.u) != 0 ? (Long.compare(u, other.u)) : (Long.compare(v, other.v));
					}
					
					public String toString() {
						return "[u=" + u + ", v=" + v + "]";
					}
				}
				
				public static int gcd(int n, int m){
					if(m!=0) return gcd(m,n%m);
					else return n;
				}
				
				static int CeilIndex(int A[], int l, int r, int key)
			    {
			        while (r - l > 1)
			        {
			            int m = l + (r - l)/2;
			            if (A[m]>=key)
			                r = m;
			            else
			                l = m;
			        }
			 
			        return r;
			    }
			/*	public static Pair recur(int N, int K, int C){
					if(K>k) return new Pair(Long.MAX_VALUE/2,-1);
					if(N>=n && k<K) return new Pair(Long.MAX_VALUE/2,-1);
					if(N>=n && k==K) return new Pair(0,k);
					if(N>=n) return new Pair(0,0);
					if(dp[N][C][K]!=null){
						//System.out.println(dp[N][C][K]);
						return dp[N][C][K];
					} 
					Pair ans = new Pair(Long.MAX_VALUE/2,-1);
					if(arr[N]>0){
						Pair p;
						if(arr[N]==C) p = recur(N+1,K,arr[N]);
						else p = recur(N+1,K+1,arr[N]);
						if((p.u)<ans.u){
							ans = p;
						}
						if(p.u==ans.u){
							if(p.v>ans.v){
								ans = p;
							}
						}
					}
					else{
					for(int i = 1 ;i <= m; i++){
						Pair p;
						if(i==C)
						p = recur(N+1,K,i);
						else p = recur(N+1,K+1,i);
						p.u+=col[N][i-1];
						if((p.u)<ans.u){
							ans = p;
						}
						if(p.u==ans.u){
							if(p.v>ans.v){
								ans = p;
							}
						}
					}
					//System.out.println(ans);
					}
					return dp[N][C][K] = ans;
				}*/
				public static void mergeSort(int[] arr2, int l ,int r){
					if((r-l)>=1){
						int mid = (l+r)/2;
						mergeSort(arr2,l,mid);
						mergeSort(arr2,mid+1,r);
						merge(arr2,l,r,mid);
						//System.out.println(Ans);
					}
				}
				public static void merge(int arr[], int l, int r, int mid){
					int n1 = (mid-l+1), n2 = (r-mid);
					int left[] = new int[n1];
					int right[] = new int[n2];
					for(int i =0 ;i<n1;i++) left[i] = arr[l+i];
					for(int i =0 ;i<n2;i++) right[i] = arr[mid+1+i];
					int i =0, j =0, k = l;
					while(i<n1 && j<n2){
						if(left[i]>right[j]){
							cnt[right[j]]+=(n1-i);
							arr[k++] = right[j++];
						}
						else{
							arr[k++] = left[i++];
						}
					}
					while(i<n1) arr[k++] = left[i++];
					while(j<n2) arr[k++] = right[j++];
				}
				public static void buildGraph(int n){
					for(int i =0;i<n;i++){
						int x = sc.nextInt(), y = sc.nextInt(), w = sc.nextInt();
						pmp[--x].add(new Pair(--y,w));
						pmp[y].add(new Pair(x,w));
					}
				}
				
				
 
				public static int getParent(int x){
					while(parent[x]!=x){
						parent[x] = parent[ parent[x]];
						x = parent[ x];
					}
					return x;
				}
				
				static int min(int a, int b, int c){
					if(a<b && a<c) return a;
					if(b<c) return b;
					return c;
				}
				private static void permutation(String prefix, String str) {
				    int n = str.length();
				    if (n == 0); //hs.add(prefix);
				    else {
				        for (int i = 0; i < n; i++)
				            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
				    }
				}
				static class Graph{
					int vertex;
					long weight;
				}
				public static void buildTree(int n){
					int arr[] = sc.nextIntArray(n);
					for(int i = 0;i<n;i++){
						int x = arr[i]-1;
						amp[i+1].add(x);
						amp[x].add(i+1);
					}
				}/*
				static class SegmentTree {
					Pair st[];
				//	long lazy[];
					SegmentTree(int n) {
						int size = 8 * n;
						st = new Pair[size];
						for(int i = 0; i< size;i++) st[i] = new Pair();
					//	lazy = new long[size];
						build(0, n - 1, 1);
					}
					Pair build(int ss, int se, int si) {
						if (ss == se) {
							st[si] = new Pair();
							if(arr[ss]==0){
								st[si].u = 1;
							}
							st[si].v = (se-ss+1)-st[si].u;
							st[si].z = 0;
							return st[si];
						}
						int mid = (ss + se) / 2;
						Pair temp1 = build(ss, mid, 2*si), temp2 = build(mid+1, se, si*2+1);
						long a1 = temp1.u+temp2.u, a2 = temp1.v+temp2.v, a3 = temp1.z+temp2.z+temp1.u*temp2.u+temp1.v*temp2.v;
						return st[si] = new Pair(a1,a2,a3);
					}
 
					void update(int si, int ss, int se, int idx, int val) {
						if (ss == se) {
							st[si] = new Pair();
							arr[idx] = val;
							if(arr[idx]==0){
								st[si].u = 1;
							}
							st[si].v = (se-ss+1)-st[si].u;
							st[si].z = 0;
						} 
						else {
							int mid = (ss + se) / 2;
							if(ss <= idx && idx <= mid)
					        {
					             update(2*si, ss, mid, idx, val);
					        }
					        else
					        { update(2*si+1, mid+1, se, idx, val);
					        }
							long a1 = st[si*2].u+st[si*2+1].u, a2 = st[si*2].v+st[si*2+1].v, a3 = st[si*2].z+st[si*2+1].z+st[si*2+1].u*st[si*2].u+st[si*2+1].v*st[si*2].v;
							st[si] = new Pair(a1,a2,a3);
						}
					}
					Pair get(int qs, int qe, int ss, int se, int si){
						if(qs>se || qe<ss){
							return new Pair(0,0,0);
						}
						if (qs <= ss && qe >= se) {
							return st[si];
						}
						int mid = (ss+se)/2;
						Pair temp1 = get(qs, qe, ss, mid, si * 2), temp2 = get(qs, qe, mid + 1, se, si * 2 + 1);
						long a1 = temp1.u+temp2.u, a2 = temp1.v+temp2.v, a3 = temp1.z+temp2.z+temp1.u*temp2.u+temp1.v*temp2.v;
						st[si] = new Pair(a1,a2,a3);
						return st[si];
					}
					/*void updateRange(int node, int start, int end, int l, int r, long val)
					{
					    if(lazy[node] != 0)
					    { 
					        // This node needs to be updated
					        st[node] += (end - start + 1) * lazy[node];    // Update it
					        if(start != end)
					        {
					            lazy[node*2] += lazy[node];                  // Mark child as lazy
					            lazy[node*2+1] += lazy[node];                // Mark child as lazy
					        }
					        lazy[node] = 0;                                  // Reset it
					    }
					    if(start > end || start > r || end < l)              // Current segment is not within range [l, r]
					        return;
					    if(start >= l && end <= r)
					    {
					        // Segment is fully within range
					        st[node] += (end - start + 1) * val;
					        if(start != end)
					        {
					            // Not leaf node
					            lazy[node*2] += val;
					            lazy[node*2+1] += val;
					        }
					        return;
					    }
					    int mid = (start + end) / 2;
					    updateRange(node*2, start, mid, l, r, val);        // Updating left child
					    updateRange(node*2 + 1, mid + 1, end, l, r, val);   // Updating right child
					    st[node] = st[node*2] + st[node*2+1];        // Updating root with max value 
					}
 
					long queryRange(int node, int start, int end, int l, int r)
					{
					    if(start > end || start > r || end < l)
					        return 0L;         // Out of range
					    if(lazy[node] != 0)
					    {
					        // This node needs to be updated
					        st[node] += (end - start + 1) * lazy[node];            // Update it
					        if(start != end)
					        {
					            lazy[node*2] += lazy[node];         // Mark child as lazy
					            lazy[node*2+1] += lazy[node];    // Mark child as lazy
					        }
					        lazy[node] = 0L;                 // Reset it
					    }
					    if(start >= l && end <= r)             // Current segment is totally within range [l, r]
					        return  st[node];
					    int mid = (start + end) / 2;
					    long p1 = queryRange(node*2, start, mid, l, r);         // Query left child
					    long p2 = queryRange(node*2 + 1, mid + 1, end, l, r); // Query right child
					    return (p1 + p2);
					}
					void print() {
						for (int i = 0; i < st.length; i++) {
							System.out.print(st[i].u+" "+st[i].v+" "+st[i].z+"\n");
						}
						System.out.println();
					}
				}*/
				static class Tree {
					ArrayList<Integer>[] g ;
					int T[]; // parent
					int L[]; // level
					int P[][]; // P[i][j] = 2^j th parent of i
 
					public Tree(int n) {
						T = new int[n];
						L = new int[n];
						P = new int[n][log2(n) + 1];
						g = (ArrayList<Integer>[])new ArrayList[n];
						L[0] = 0;
						T[0] = -1;
						for (int i = 0; i < n; i++) {
							g[i] = new ArrayList<>();
						}
						for (int i = 0; i < n ; i++) {
							int a = sc.nextInt();
							for(int j = 0; j<a; j++){
								int b = sc.nextInt()-1;
								g[i].add(b);
								g[b].add(i);
							}
						}
						dfs(0, -1);
						for (int j = 0; (1 << j) <= n; j++)
							pre(0, j,-1);
					}
 
					public int log2(int n) {
						return (int) (Math.log10(n) / Math.log10(2));
					}
 
					public void dfs(int node, int p) {
						for (int k : g[node]) {
							if (k != p) {
								T[k] = node;
								L[k] = L[node] + 1;
								dfs(k, node);
							}
						}
					}
					public void pre(int node, int j,int p) {
						if (j == 0) {
							P[node][j] = T[node];
						} else {
							P[node][j] = P[P[node][j - 1]][j - 1];
						}
						for (int k : g[node]) {
							if(k!=p)
								pre(k, j,node);
						}
					}
					public int lca(int u, int v) {
						if (L[u] > L[v]) {
							int temp = u;
							u = v;
							v = temp;
						}
						int log;
						for (log = 0; (1 << log) <= L[v]; log++)
							; // convert level into log
						log--;
 
						for (int i = log; i >= 0; i--) {
							if ((1 << i) <= L[v] - L[u]) // make both node's level same
								v = P[v][i];
						}
						if (u == v)
							return u;
						for (int i = log; i >= 0; i--) {
							if (P[u][i] != -1 && P[u][i] != P[v][i]) // shift up both u and v
							{
								u = P[u][i];
								v = P[v][i];
							}
						}
						return T[u];
					}
				}
				public static long max(long x, long y, long z){
					if(x>=y && x>=z) return x;
					if(y>=x && y>=z) return y;
					return z;
				}
				
				public static void seive(long n){
					b = new boolean[(int) (n+1)];
					Arrays.fill(b, true);
					for(int i = 2;i*i<=n;i++){
						if(b[i]){
							for(int p = 2*i;p<=n;p+=i){
								b[p] = false;
							}
						}
					}
				}
				static long modInverse(long a, long mOD2){
				            return  power(a, mOD2-2, mOD2);
				}
				static long power(long x, long y, long m)
				{
				    if (y == 0)
				        return 1;
				    long p = power(x, y/2, m) % m;
				    p = (p * p) % m;
				 
				    return (y%2 == 0)? p : (x * p) % m;
				}
				static long d,x,y;
				public static void extendedEuclidian(long a, long b){
					if(b == 0) {
				        d = a;
				        x = 1;
				        y = 0;
				    }
				    else {
				        extendedEuclidian(b, a%b);
				        int temp = (int) x;
				        x = y;
				        y = temp - (a/b)*y;
				    }
				}
				
				
				static class FasterScanner {
 
					private final InputStream stream;
					private final byte[] buf = new byte[8192];
					private int curChar, snumChars;
					private SpaceCharFilter filter;
					public int read() {
						if (snumChars == -1)
							throw new InputMismatchException();
						if (curChar >= snumChars) {
							curChar = 0;
							try {
								snumChars = System.in.read(buf);
							} catch (IOException e) {
								throw new InputMismatchException();
							}
							if (snumChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
					public FasterScanner(InputStream stream) {
						this.stream = stream;
					}
					public String nextString() {
						int c = read();
						while (isSpaceChar(c))
							c = read();
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = read();
						} while (!isSpaceChar(c));
						return res.toString();
					}
					public int snext() {
						if (snumChars == -1)
							throw new InputMismatchException();
						if (curChar >= snumChars) {
							curChar = 0;
							try {
								snumChars = stream.read(buf);
							} catch (IOException e) {
								throw new InputMismatchException();
							}
							if (snumChars <= 0)
								return -1;
						}
						return buf[curChar++];
					}
 
					public int nextInt() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = snext();
						}
						int res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
 
					public long nextLong() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						int sgn = 1;
						if (c == '-') {
							sgn = -1;
							c = snext();
						}
						long res = 0;
						do {
							if (c < '0' || c > '9')
								throw new InputMismatchException();
							res *= 10;
							res += c - '0';
							c = snext();
						} while (!isSpaceChar(c));
						return res * sgn;
					}
 
					public int[] nextIntArray(int n) {
						int a[] = new int[n];
						for (int i = 0; i < n; i++) {
							a[i] = nextInt();
						}
						return a;
					}
 
					public long[] nextLongArray(int n) {
						long a[] = new long[n];
						for (int i = 0; i < n; i++) {
							a[i] = nextInt();
						}
						return a;
					}
			                
					public String readString() {
						int c = snext();
						while (isSpaceChar(c)) {
							c = snext();
						}
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = snext();
						} while (!isSpaceChar(c));
						return res.toString();
					}
 
					public String nextLine() {
						int c = snext();
						while (isSpaceChar(c))
							c = snext();
						StringBuilder res = new StringBuilder();
						do {
							res.appendCodePoint(c);
							c = snext();
						} while (!isEndOfLine(c));
						return res.toString();
					}
 
					public boolean isSpaceChar(int c) {
						if (filter != null)
							return filter.isSpaceChar(c);
						return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
					}
 
					private boolean isEndOfLine(int c) {
						return c == '\n' || c == '\r' || c == -1;
					}
 
					public interface SpaceCharFilter {
						public boolean isSpaceChar(int ch);
					}
				}
			}