Şimali Avropa Universiteti öz kitabxanası ilə məşhurdur. Lakin paxıllıqdan başqa bir məşhur universitet NEU-ya kitab qurdları buraxıb. İndi isə baş kitabxanaçı Aleks təcili olaraq zərərin miqdarını müəyyən etməlidir.
Kitabxanadakı bütün N kitab bir, çox uzun rəfdə yerləşdirilib. Aleks kitabın belinə baxaraq toxunmadan onun nömrəsini təyin edə bilir. Kitablar soldan sağa doğru bir-bir nömrələnib, birincidən başlayır. Heç bir kitab tərs deyil.
Aleks kitabxanada M qurd aşkar edib. O, hər bir qurdun haradan başladığını və harada yolunu bitirdiyinə müəyyən edib. Hər bir qurd birbaşa xətt üzərində hərəkət edir, ya soldan sağa, ya da sağdan sola. Ziyanı düzgün hesablamaq üçün Aleks dəqiq müəyyən etmək istəyir ki, məhz k qurd tərəfindən neçə səhifə gəmirilib. Ona bu məsələdə kömək edin və proqram yazın.
Giriş fayının birinci sətrində bir boşluqla ayrılmış iki tam ədəd verilir: N və M (1 \leq N \leq 10000, 1 \leq M \leq 100000). İkinci sətirdə N müsbət tam ədəd p_i verilib, burada p_i - i-ci kitabdakı səhifələrin sayıdır (p_i \leq 10000). Sonrakı M sətirdə qurdların yolları təsvir olunur. Hər yolun təsvirində dörd müsbət tam ədəd var: qurdun yolunun başladığı kitab və səhifə nömrəsi, habelə bitdiyi kitab və səhifə nömrəsi.
Çıxış fayında (M+1) sətir olmalıdır. k-cı sətirdə dəqiq (k-1) qurd tərəfindən gəmirilən səhifələrin sayını çap edin.
Nümunə 1