Có \(m\) điểm du lịch ở Manado, được đánh số từ 1 đến \(m\). Hôm nay, có n khách du lịch ở Manado, được đánh số từ 1 đến \(n\). Vì có rất nhiều điểm du lịch nên hôm nay mỗi du khách chỉ có thể đến thăm một số điểm du lịch. Khách du lịch thứ \(i\) đến thăm \(a[i], a[i]+1, a[i]+2,..., b[i]\) điểm thu hút khách du lịch.

Một khách du lịch sẽ làm quen với một khách du lịch khác nếu có ít nhất một điểm du lịch được cả hai du khách đến thăm. Những khách du lịch này muốn biết số lượng khách du lịch mà họ sẽ làm quen, không bao gồm bản thân họ.

Input

• Dòng đầu tiên chứa số nguyên \(n,m (1≤n≤2×10^5,1≤m≤10^9 ).\)

• \(n\) dòng tiếp theo mỗi dòng chứa số \(a[i],b[i] (1≤a[i]≤b[i]≤m).\)

Output

• Đưa ra \(n\) dòng là số lượng người làm quen của từng khách du lịch.

Ràng buộc

• Subtask 1: 25% test với \(n,m≤400.\)

• Subtask 2: 25% test với \(n≤2000\).

• Subtask 3: 25% test với \(m≤4*10^5.\)

• Subtask 4: 25% không có ràng buộc gì thêm.

Sample Input

4 5
2 3
1 2
3 4
5 5

Sample Output

2
1
1
0