Chọn nhóm

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.

Nhóm có thể rỗng: nếu không chọn được học sinh nào thỏa mãn thì số lượng là $0$.

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,\dots ,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.

Dữ liệu vào

• 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$ ($1\le i,j\le n$, $i\ne j$) cho biết học sinh $i$ và $j$ hiểu nhau; mỗi cặp học sinh xuất hiện không quá một lần;
• 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$; $1\le k_s\le n$).

Dữ liệu ra

In 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$.

Ràng buộc

• $1\le n\le {10}^5$, $0\le m\le {10}^5$, $1\le T\le 300$.
• $1\le a_s\le b_s\le n$, $1\le k_s\le n$.

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$; $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$.

Ví dụ