Bükülmüş intervallar

İnəklər n intervaldan ibarət bir oyun oynayırlar. Burada i-ci interval ədədi oxda a[i] mövqeyindən başlayır və b[i] mövqeyində bitir, burada b[i] ≥ a[i]. Həm a[i], həm də b[i] ədədləri 0..m intervalında tam ədədlərdir, burada 1 ≤ m ≤ 5000.

Bu oyunu oynamaq üçün Bessi müəyyən bir interval seçir, məsələn, i-ci. Elsa isə müəyyən bir interval seçir, məsələn, j-ci, bəlkə də eyni intervalı. Verilmiş k dəyəri üçün onlar qalib gəlirlər, əgər a[i] + a[j] ≤ k ≤ b[i] + b[j].

0..2m intervalında bütün k üçün Bessi və Elsa bu oyunu qazanacaqları sıralı cütlərin (i, j) sayını hesablayın.

Giriş Məlumatları

Girişin birinci sətiri n (1 ≤ n ≤ 2 * 10^5) və m ədədlərini ehtiva edir. Sonrakı n sətirin hər biri a[i] və b[i] tam ədədləri ilə intervalı təsvir edir.

Çıxış Məlumatları

0..2m intervalında hər bir k üçün bir sətirdə 2 * m + 1 sətir çıxarın.

Nümunə

Bu nümunədə k = 3 üçün Bessi və Elsa üçün qalib gələn 3 sıralı cüt var: (1, 1), (1, 2) və (2, 1).