Một lớp học có ~n~ học sinh, các học sinh được đánh số hiệu từ 1 đến ~n~. Thầy chủ nhiệm muốn tổ chức một trò chơi, trò chơi đòi hỏi các thành viên tham gia phải rất hiểu nhau. Là một giáo viên có nhiều năm kinh nghiệm và rất sâu sắc với học sinh, nên thầy biết hai học sinh ~i~ và ~j~ bất kỳ có hiểu nhau hay không (học sinh ~i~ hiểu học sinh ~j~ thì học sinh ~j~ cũng hiểu học sinh ~i~). Với ba số nguyên ~a, b, k~, nhóm học sinh mà thầy giáo muốn chọn để tham gia trò chơi sẽ thỏa mãn các yêu cầu sau:

• Các học sinh có thể được chọn là học sinh có số hiệu từ ~a~ đến ~b~;
• Mỗi học sinh trong nhóm sẽ có ít nhất ~k~ học sinh trong nhóm hiểu mình;
• Số lượng học sinh trong nhóm được chọn là nhiều nhất.

Yêu cầu: Cho mối quan hệ hiểu nhau của tất cả các học sinh trong lớp và ~T~ bộ ba số nguyên ~a_s, b_s, k_s~ (~s = 1, 2, ..., T~), với mỗi bộ ba hãy giúp thầy giáo chọn nhóm thỏa mãn yêu cầu.

Input

• Dòng đầu chứa hai số nguyên ~n, m~;
• ~m~ dòng sau, mỗi dòng chứa 2 số nguyên ~i, j~ (~i \neq j~) cho biết học sinh ~i~ và ~j~ hiểu nhau;
• Dòng tiếp theo chứa số nguyên ~T~ là số bộ ba;
• Dòng thứ ~s~ trong ~T~ dòng tiếp theo chứa ba số ~a_s, b_s, k_s~ (~1 \le a_s \le b_s \le n; s = 1, 2, ..., T~).

Output

• Ghi ra ~T~ dòng, dòng thứ ~s~ ghi một số nguyên là số lượng học sinh trong nhóm chọn được tương ứng với bộ ba thứ ~s~.

Sample Input 1

4 4
1 2
1 3
1 4
3 4
2
1 4 2
1 3 2

Sample Output 1

3
0

Subtasks

• Có 30% số test ứng với 30% số điểm có ~n \le 20; m \le 100; T = 1~;
• Có 30% số test khác ứng với 30% số điểm có ~n \le 10^4; m \le 10^5; k = 1; T \le 3~;
• Có 30% số test khác ứng với 30% số điểm có ~n \le 10^4; m \le 10^5; k = 1; T = 1~;
• Có 10% số test còn lại ứng với 10% số điểm có ~n \le 10^5; m \le 10^5; T \le 300~.