Một lớp học có \(𝑛\) học sinh, các học sinh được đánh số hiệu từ 1 đế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 \(𝑖\) và \(𝑗\) bất kỳ có hiểu nhau hay không (học sinh \(𝑖\) hiểu học sinh \(𝑗\) thì học sinh \(𝑗\) cũng hiểu học sinh \(𝑖\)). Với ba số nguyên \(𝑎, 𝑏, 𝑘,\) 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ừ \(𝑎\) đến \(𝑏\);
• Mỗi học sinh trong nhóm sẽ có ít nhất \(𝑘\) 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à \(𝑇\) bộ ba số nguyên \(𝑎_𝑠, 𝑏_𝑠, 𝑘_𝑠\ (𝑠 = 1,2, … , 𝑇)\), 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 \(𝑛, 𝑚\);
• \(𝑚\) dòng sau, mỗi dòng chứa 2 số nguyên \(𝑖,𝑗\ (𝑖 ≠ 𝑗)\) cho biết học sinh \(𝑖\) và \(𝑗\) hiểu nhau;
• Dòng tiếp theo chứa số nguyên \(𝑇\) là số bộ ba;
• Dòng thứ \(𝑠\) trong \(𝑇\) dòng tiếp theo chứa ba số \(𝑎_𝑠, 𝑏_𝑠, 𝑘_𝑠\ (1 \le 𝑎_𝑠 \le 𝑏_𝑠 \le 𝑛; 𝑠 = 1,2, … , 𝑇)\).

Output

• Gồm \(𝑇\) dòng, dòng thứ \(𝑠\) 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ứ \(𝑠\).

Scoring

• Subtask #1 (\(30\%\) số điểm): \(𝑛 \leq 20; 𝑚 \leq 100; 𝑇 = 1\)
• Subtask #2 (\(30\%\) số điểm): \(𝑛 \leq 10^4; 𝑚 \leq 10^5; 𝑘 = 1; 𝑇 \leq 3\)
• Subtask #3 (\(30\%\) số điểm): \(𝑛 \leq 10^4; 𝑚 \leq 10^5; 𝑇 = 1;\)
• Subtask #4 (\(10\%\) số điểm): \(𝑛 \leq 10^5; 𝑚 \leq 10^5; 𝑇 \leq 300.\)

Example

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

3
0

Nguồn: 2019 chính thức