有 $n$ 个元素 $a_1, a_2, \dots, a_n$，每个元素都有一个锁。最初，所有元素都是未锁定的。

给出 $q$ 次询问，第 $i$ 次询问包含四个整数 $(t_s, t_e, l, r)$，其中 $1 \le l \le r \le n$。每次询问在时间轴上执行一个加锁过程和一个解锁过程。

加锁过程：从时间 $t_s$ 开始，在接下来的 $r - l + 1$ 个时间点，依次处理元素 $a_l, a_{l+1}, \dots, a_r$。具体来说，在时间 $t_s + k$，处理元素 $a_{l+k}$（$0 \le k \le r - l$）。如果该元素当前未被锁定，则将其锁定，并将该锁标记为属于当前询问；如果它已被其他询问锁定，则不执行任何操作。也就是说，如果在访问该锁时，它已经被另一个加锁过程锁定，则该锁不会发生任何变化。

解锁过程：从时间 $t_e$ 开始，在接下来的 $r - l + 1$ 个时间点，依次处理元素 $a_l, a_{l+1}, \dots, a_r$。具体来说，在时间 $t_e + k$，处理元素 $a_{l+k}$（$0 \le k \le r - l$）。如果该元素当前的锁是由该询问在加锁过程中添加的，则将其解锁；否则，不执行任何操作。

对于在同一时间发生在同一元素上的所有操作，按询问编号（索引）升序执行。

对于每次询问，统计在其加锁过程中成功锁定的元素数量。

输入格式

第一行包含两个整数 $n, q$（$1 \le n, q \le 1000$）。

接下来的 $q$ 行，每行包含四个整数 $t_s, t_e, l, r$（$1 \le l \le r \le n, 1 \le t_s < t_e \le 10^9$），表示一次询问。

输出格式

输出 $q$ 行，其中第 $i$ 行包含第 $i$ 次询问成功锁定的元素数量。

样例

输入样例 1

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

输出样例 1

0
1
2
0
1

输入样例 2

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

输出样例 2

1
0
2
3
2