Gəmirilmiş kitablar
Min bir qurd!______________
preference oyunçularının dialoqundan
Sankt-Peterburq Dövlət Universiteti, xüsusilə kitabxanası ilə məşhurdur. Lakin başqa bir tanınmış universitet, qısqanclıq səbəbindən SPbDU-ya kitab qurdları göndərdi. İndi baş kitabxanaçı Vasya, zərərin miqdarını təcili olaraq müəyyən etməlidir.
Kitabxanadakı bütün N kitablar uzun bir rəfdə saxlanılır. Vasya, kitabın cildinə baxaraq, ona toxunmadan kitabın nömrəsini müəyyən edə bilir. Kitablar soldan sağa doğru, birinci nömrədən başlayaraq nömrələnib. Heç bir kitab tərs çevrilməyib.
Vasya kitabxanada M qurd aşkar etdi. O, hər bir qurdun haradan başladığını və harada bitirdiyini müəyyən etdi. Bütün qurdlar düz xətt üzrə soldan sağa və ya sağdan sola hərəkət edirdi. Zərəri düzgün hesablamaq üçün Vasya, dəqiq olaraq k qurd tərəfindən yeyilən səhifələrin sayını hesablayan bir proqram yazmaq istəyir. Ona bu işdə kömək edin.
Giriş verilənləri
Giriş faylının birinci sətirində boşluqla ayrılmış iki ədəd N və M (1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000) verilib. İkinci sətir N müsbət tam ədəd p_i - i-ci kitabdakı səhifələrin sayını (p_i ≤ 10000) ehtiva edir. Növbəti M sətirdə yolların təsviri verilib. Yolun təsviri dörd müsbət tam ədəddən ibarətdir - qurdun yolunun başlanğıc kitabının və səhifəsinin nömrəsi, həmçinin yolun bitiş kitabının və səhifəsinin nömrəsi.
Çıxış verilənləri
Çıxış faylı (M+1) sətir ehtiva etməlidir. k-cı sətirdə dəqiq olaraq (k-1) qurd tərəfindən yeyilən səhifələrin sayını yazın.