Qəbul et 150 saniyə ərzində#4461
Sözə baxmayan krallıqda, onlayn tramvay biletlərinin satışını təmin edən proqram təminatını yazan proqramçıların onları aldatmadığını yoxlamağa qərar verdilər. Onlayn bilet satışı belə həyata keçirilir: hər bir sərnişin A stansiyasından B stansiyasına bilet sifariş edir. Bu bədbəxt proqramçıların proqramı isə rəhbərliyə yalnız hər dayanacaqda nə qədər sərnişinin mindiyini (In) və nə qədər sərnişinin düşdüyünü (Out) bildirir.
Bu məlumatı yoxlamaq üçün nəqliyyat idarəsi marşruta nəzarətçilər göndərdi, onlar L stansiyasından R stansiyasına qədər bütün sərnişinləri nəzarət edirlər, nəqliyyata minən və düşən sərnişinləri sayırlar. Onlar L stansiyasından R stansiyasına qədər faktiki olaraq nə qədər bilet satıldığını öyrəndilər, lakin idarəyə gedərkən bu məlumatı itirdilər. Rəhbərlik onları danlamasın deyə, sizdən bu məlumatı tez bir zamanda hesablayıb nəqliyyat idarəsinə göndərməyinizi xahiş edirlər.
Tramvay marşrutu düz xəttdir, onun boyunca dayanacaqlar yerləşir. Dayanacaqlar birdən başlayaraq nömrələnir, lakin yalnız kiçik nömrəli dayanacaqdan böyük nömrəli dayanacağa qədər getmək mümkündür.
Birinci sətirdə 2 natural ədəd verilir: N – dayanacaqların sayı, M – xətt üzrə nəzarətçilərin sayı (N ≤ 10^5, M ≤ 10^5). Növbəti N sətirdə i+1-ci sətir i-ci dayanacaq üçün iki ədəd cütlüyünü təsvir edir: In – i stansiyasında nə qədər insan mindi və Out – i stansiyasında nə qədər insan düşdü (0 ≤ In, Out ≤ 10^4, Out[1] = 0, In[N] = 0, son dayanacaqda (N) tramvaydan bütün sərnişinlər düşür). Növbəti M sətirdə də iki ədəd cütlüyü L, R - nəzarətçilərin işlədiyi stansiyaların nömrələri (1 ≤ L < R ≤ N).
Hər bir nəzarətçi üçün, onlar verildiyi sırada, L və R dayanacaqları arasında nə qədər bilet satıldığını göstərin.
Nümunə 1