Plinko là một trò chơi trong đó người chơi thả một quả bóng từ đỉnh của một bảng có nhiều chốt. Quả bóng rơi xuống, nảy qua lại, và cuối cùng đi tới một trong các ô ở phía dưới.

Trong bài này, thay vì một bảng có chốt, Alice được cho một mê cung bằng gỗ với ~n~ hàng và ~m~ cột. Mê cung được biểu diễn như một lưới gồm ~n \times m~ ô, với các hàng được đánh số từ ~0~ đến ~n - 1~, và các cột được đánh số từ ~0~ đến ~m - 1~. Ô ở hàng thứ ~i~ và cột thứ ~j~ được ký hiệu là ~(i,j)~.

Một số ô của mê cung là ô trống, còn các ô còn lại là các khối gỗ. Các ô trống trong mỗi hàng được mô tả bởi một số đoạn rời nhau.

Ở hàng thứ ~i~, có ~s_i~ đoạn trống. Đoạn trống thứ ~j~ của hàng ~i~ được mô tả bởi hai số nguyên ~l_{i,j}~ và ~r_{i,j}~, nghĩa là mọi ô ~(i,k)~ thỏa mãn ~l_{i,j} \leq k < r_{i,j}~ đều là ô trống. Tất cả các ô khác trong hàng ~i~ là khối gỗ. Các đoạn trống trong mỗi hàng thỏa mãn ~0 \leq l_{i,1} < r_{i,1} < l_{i,2} < r_{i,2} < \ldots < l_{i,s_i} < r_{i,s_i} \leq m~.

Khi một quả bóng được đặt vào ô trống ~(x,y)~, nó có thể di chuyển tới một trong các ô kề sau:

• ~(x+1,y)~, đi xuống;

• ~(x,y+1)~, đi sang phải;

• ~(x,y-1)~, đi sang trái.

Quả bóng chỉ được phép di chuyển tới ô trống. Nó không được phép đi lên.

Ta nói rằng ô ~(a,b)~ có thể đi tới ô ~(c,d)~ nếu tồn tại một dãy các bước đi hợp lệ bắt đầu từ ~(a,b)~ và kết thúc tại ~(c,d)~.

Bob hỏi Alice ~q~ câu hỏi. Trong mỗi câu hỏi, Alice được cho năm số nguyên ~a,b,c,l,r~. Một quả bóng được đặt tại ô ~(a,b)~, và Alice phải xác định có bao nhiêu ô ~(c,d)~ thỏa mãn ~l \leq d \leq r~ có thể đi tới từ ~(a,b)~.

Đảm bảo rằng ~a \leq c~.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n \leq 5 \cdot 10^5~, ~1 \leq m \leq 10^9)~ – số hàng và số cột của mê cung.

Mỗi trong ~n~ dòng tiếp theo mô tả một hàng của mê cung. Dòng thứ ~i~ (~0 \le i < n~) bắt đầu bằng một số nguyên ~s_i~ – số đoạn trống trong hàng thứ ~i~. Sau đó là ~2\cdot s_i~ số nguyên: ~l_{i,1}, r_{i,1}, l_{i,2}, r_{i,2}, \ldots, l_{i,s_i}, r_{i,s_i}~ (~0 \leq l_{i,1} < r_{i,1} < l_{i,2} < r_{i,2} < \ldots < l_{i,s_i} < r_{i,s_i} \leq m~).

~\quad~ Gọi ~z = \sum_{i=0}^{n-1} s_i~. Đảm bảo rằng ~1 \leq z \leq 5 \cdot 10^5~.

Dòng tiếp theo chứa một số nguyên ~q~ ~(1 \leq q \leq 5 \cdot 10^5)~ – số câu hỏi.

Mỗi trong ~q~ dòng tiếp theo chứa năm số nguyên ~a,b,c,l,r~ mô tả một câu hỏi: ~0 \leq a \leq c < n~, ~0 \leq b < m~, và ~0 \leq l \leq r < m~.

Output

Với mỗi câu hỏi, in ra một số nguyên: số ô ~(c,d)~ sao cho ~l \leq d \leq r~ và ~(c,d)~ có thể đi tới từ ~(a,b)~.

Scoring

Sample Input 1

3 12
1 0 10
2 0 4 6 10
3 0 2 4 6 8 10
5
0 5 2 0 11
0 5 2 0 3
0 5 2 4 7
0 5 2 8 11
1 1 2 0 11

Sample Output 1

4
2
0
2
2

Notes

Trong ví dụ, đoạn trống ở hàng ~0~ là ~[0,10)~. Các đoạn trống ở hàng ~1~ là ~[0,4)~ và ~[6,10)~. Các đoạn trống ở hàng ~2~ là ~[0,2)~, ~[4,6)~, và ~[8,10)~.

Nếu quả bóng bắt đầu từ ô ~(0,5)~, nó có thể đi tới hai đoạn ~[0,4)~ và ~[6,10)~ ở hàng ~1~. Từ đó, nó có thể đi tới hai đoạn ~[0,2)~ và ~[8,10)~ ở hàng ~2~.

Vì vậy, trong các cột từ ~0~ đến ~11~ ở hàng ~2~, chính xác có ~4~ ô có thể đi tới.