Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Set, Intersection and Range

Limits: 1s, 1.0 GB

You are given N sets of integers (S[1] , S[2] , S[3] , … , S[N]) and Q queries.

Each query has 4 integers X, Y, L, R. You just need to find :

A = ( S[X] ) Intersection ( S[Y] ) 
[ Intersection means taking the common elements of the two sets ]
Ans = 0
For i = L to R 
    if S[i] is equal to A
        Ans = Ans + 1
    end if
end For

For each query just print Ans.

Input

The first line contains two integer N ( 1 ≤ N ≤ 105 ) and Q ( 1 ≤ Q ≤ 105 ).

For the next N lines, first integer denotes the number of elements in the ith set and then the elements of the set is given.

Next there are Q queries with four integers which is described above.

Size of any of the sets are within 105.
And their summation is within 2 * 105.
The numbers in a set fits in 32 bit signed integer.

Output

For each query print the corresponding Ans.

Samples

InputOutput
4 4
3 1 2 3
2 2 3
3 2 3 4
2 2 3
1 3 1 4 
1 3 1 2
1 3 2 4
1 3 1 1
2
1
2
0

A Set is a collection of unique elements where the elements are always sorted.

Discussion
Submit

Login to submit

Editorial

Login to unlock editorial