A class has $n$ students, numbered from $1$ to $n$. The homeroom teacher wants to organize a game that requires the participants to have a deep understanding of each other. Being a teacher with many years of experience and a profound understanding of the students, the teacher knows whether any two students $i$ and $j$ understand each other (if student $i$ understands student $j$, then student $j$ also understands student $i$). With three integers $a$, $b$, $k$, the group of students that the teacher wants to select to participate in the game must satisfy the following requirements:
- Students can be selected with serial numbers from $a$ to $b$;
- Each student in the group will have at least $k$ students in the group who understand them;
- The number of students in the group selected should be maximized.
Given the understanding relationships of all students in the class and $T$ triplets of integers $a_s, b_s, k_s (s = 1,2, ... , T)$, for each triplet, help the teacher choose a group that meets the requirements.
### Input
- The first line contains two positive integers $n, m$.
- The next $m$ lines each contain two integers $i, j (i \neq j)$, indicating that student $i$ understands student $j$.
- The next $T$ lines, each containing three integers $a_s, b_s, k_s (1 \le a_s \le b_s \le n; s=1,2,...,T)$.
### Output
- Output $T$ lines, where the $s$-th line contains an integer representing the number of students in the selected group corresponding to the $s$-th triplet.
### Constraints
- 30% of the tests have $n \le 20, m\le100, T=1$.
- 30% of the tests have $n \le 10^4, m\le10^5, k=1, T\le3$.
- 30% of the tests have $n \le 10^4, m\le10^5, T=1$.
- 10% of the tests have $n\le10^5, m\le10^5, T\le300$.
### Example
Input:
```
4 4
1 2
1 3
1 4
3 4
2
1 4 2
1 3 2
```
Output:
```
3
0
```
